scientific article; zbMATH DE number 7471588
From MaRDI portal
Publication:5028364
DOI10.4086/toc.2021.v017a011zbMath1496.68156OpenAlexW3217149345MaRDI QIDQ5028364
Igor C. Oliveira, Rahul Santhanam, Ján Pich
Publication date: 9 February 2022
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2021.v017a011
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
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)
Cites Work
- 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}}\)
- Universal classes of hash functions
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- On the approximability of clique and related maximization problems
- Oracles and queries that are sufficient for exact learning
- 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
- Simple strategies for large zero-sum games with applications to complexity theory
- $$P\mathop{ =}\limits^{?}NP$$
- Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
- Expander codes
- Linear-time encodable and decodable error-correcting codes
- Nonuniform ACC Circuit Lower Bounds
- Circuit-size lower bounds and non-reducibility to sparse sets
- 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
- Hardness magnification near state-of-the-art lower bounds
- Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- 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
- 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:
