Hardness magnification near state-of-the-art lower bounds
From MaRDI portal
Publication:5091779
DOI10.4230/LIPIcs.CCC.2019.27zbMath1496.68155OpenAlexW2965961151MaRDI QIDQ5091779
Igor C. Oliveira, Rahul Santhanam, Ján Pich
Publication date: 27 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2019.27
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items (13)
Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Unnamed Item ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Hardness of sparse sets and minimal circuit size problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Amplifying circuit lower bounds against polynomial time, with applications
- Circuit lower bounds in bounded arithmetics
- Boolean function complexity. Advances and frontiers.
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- On the approximability of clique and related maximization problems
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- On the weak pigeonhole principle
- Natural Proofs versus Derandomization
- Simple strategies for large zero-sum games with applications to complexity theory
- Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
- The Complexity of Complexity
- Expander codes
- Linear-time encodable and decodable error-correcting codes
- Nonuniform ACC Circuit Lower Bounds
- Circuit minimization problem
- Circuit Lower Bounds for Merlin–Arthur Classes
- Amplifying lower bounds by means of self-reducibility
- Randomness conservation inequalities; information and independence in mathematical theories
- Size--Depth Tradeoffs for Threshold Circuits
- The Shrinkage Exponent of de Morgan Formulas is 2
- Pseudorandom Generators in Propositional Proof Complexity
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- Quantified derandomization of linear threshold circuits
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Pseudorandomness from Shrinkage
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Learning algorithms from natural proofs
- Power from Random Strings
- Class of constructive asymptotically good algebraic codes
- Non-commutative circuits and the sum-of-squares problem
- Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs
- Computational Complexity
- Natural proofs
This page was built for publication: Hardness magnification near state-of-the-art lower bounds
