Under the auspices of the Computational Complexity Foundation (CCF)

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 >>>

TR22-108 | 18th July 2022
Shuichi Hirahara, Nobutaka Shimizu

#### Hardness Self-Amplification from Feasible Hard-Core Sets

We consider the question of hardness self-amplification: Given a Boolean function $f$ that is hard to compute on a $o(1)$-fraction of inputs drawn from some distribution, can we prove that $f$ is hard to compute on a $(\frac{1}{2} - o(1))$-fraction of inputs drawn from the same distribution? We prove hardness ... more >>>

ISSN 1433-8092 | Imprint