Hardness magnification near state-of-the-art lower bounds
From MaRDI portal
Publication:5091779
Recommendations
Cites work
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- Amplifying circuit lower bounds against polynomial time, with applications
- Amplifying lower bounds by means of self-reducibility
- Boolean function complexity. Advances and frontiers.
- Circuit lower bounds for Merlin-Arthur classes
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Circuit lower bounds in bounded arithmetics
- Circuit minimization problem
- Class of constructive asymptotically good algebraic codes
- Computational Complexity
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Expander codes
- Feasibly constructive proofs of succinct weak circuit lower bounds
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 1335875 (Why is no real title available?)
- scientific article; zbMATH DE number 1136103 (Why is no real title available?)
- scientific article; zbMATH DE number 1142303 (Why is no real title available?)
- scientific article; zbMATH DE number 2081089 (Why is no real title available?)
- scientific article; zbMATH DE number 1929951 (Why is no real title available?)
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- scientific article; zbMATH DE number 7250152 (Why is no real title available?)
- Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Learning algorithms from natural proofs
- Linear-time encodable and decodable error-correcting codes
- Natural proofs
- Non-commutative circuits and the sum-of-squares problem
- Nonuniform ACC circuit lower bounds
- On the approximability of clique and related maximization problems
- On the average-case complexity of MCSP and its variants
- On the weak pigeonhole principle
- Power from Random Strings
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Pseudorandom Generators in Propositional Proof Complexity
- Pseudorandomness from shrinkage
- Quantified derandomization of linear threshold circuits
- Randomness conservation inequalities; information and independence in mathematical theories
- Simple strategies for large zero-sum games with applications to complexity theory
- Size--Depth Tradeoffs for Threshold Circuits
- Small bias requires large formulas
- Substitution-permutation networks, pseudorandom functions, and natural proofs
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- The Complexity of Complexity
- The Shrinkage Exponent of de Morgan Formulas is 2
- Toward the KRW composition conjecture: cubic formula lower bounds via communication 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
Cited in
(22)- Feasibly constructive proofs of succinct weak circuit lower bounds
- Hardness of sparse sets and minimal circuit size problem
- Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
- Cryptographic hardness under projections for time-bounded Kolmogorov complexity
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- Hardness magnification near state-of-the-art lower bounds
- Relations and equivalences between circuit lower bounds and karp-lipton theorems
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- scientific article; zbMATH DE number 7561748 (Why is no real title available?)
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- Beyond natural proofs: hardness magnification and locality
- Beyond Natural Proofs: Hardness Magnification and Locality
- The non-hardness of approximating circuit size
- Algorithms and lower bounds for comparator circuits from shrinkage
- A duality between one-way functions and average-case symmetry of information
- Constructive separations and their consequences
- One-tape Turing machine and branching program lower bounds for MCSP
- Lower bounds for Levin-Kolmogorov complexity
- One-tape Turing machine and branching program lower bounds for MCSP
- An efficient coding theorem via probabilistic representations and its applications
This page was built for publication: Hardness magnification near state-of-the-art lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091779)
