Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with hardness magnification:
TR18-139 | 10th August 2018
Igor Carboni Oliveira, Rahul Santhanam

Hardness Magnification for Natural Problems

We show that for several natural problems of interest, complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification". Our examples of hardness magnification include:

1. Let MCSP$[s]$ be the decision problem whose YES instances are ... more >>>

TR18-158 | 11th September 2018
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

Hardness magnification near state-of-the-art lower bounds

Revisions: 1

This work continues the development of hardness magnification. The latter proposes a strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.

We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs ... more >>>

TR19-075 | 25th May 2019
Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

A frontier open problem in circuit complexity is to prove P^NP is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P/poly. Previously, for several classes containing P^NP, including NP^NP, ZPP^NP, and ... more >>>

ISSN 1433-8092 | Imprint