Loading...
Please wait, while we are loading the content...
Similar Documents
CMSC 858 F : Algorithmic Lower Bounds : Fun with Hardness Proofs Fall 2014 Cubic hardness and all-pair shortest paths
| Content Provider | Semantic Scholar |
|---|---|
| Author | Abinav, Karthik |
| Copyright Year | 2014 |
| Abstract | In the next two lectures, we look at lower bounds conjectured on two important and well-known problems. One is the All-Pairs-Shortest-Path(APSP) problem which is believed to be truly cubic(i.e. there is no exact algorithm for this problem which runs in time O(n ) for a constant > 0). The second problem considered is the 3−SUM problem which is conjectured to be truly quadratic(i.e. there is no exact algorithm that runs in time O(n ) for a constant > 0). This lecture will focus on the cubic hardness and the APSP problem. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.umd.edu/~hajiagha/ALB14/scribe-09-11-2014.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
