Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FI NE-GRAINED COMPLEXITY:
Reports tagged with fi ne-grained complexity:
TR16-053 | 6th April 2016
Jiawei Gao, Russell Impagliazzo

Orthogonal Vectors is hard for first-order properties on sparse graphs

Revisions: 3

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until ... more >>>




ISSN 1433-8092 | Imprint