Uniform derandomization from pathetic lower bounds
From MaRDI portal
Publication:2941601
DOI10.1098/rsta.2011.0318zbMath1328.68079OpenAlexW1995642625WikidataQ51353333 ScholiaQ51353333MaRDI QIDQ2941601
Rahul Santhanam, Fengming Wang, V. Arvind, Eric W. Allender
Publication date: 21 August 2015
Published in: Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1098/rsta.2011.0318
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
The foundations of computation, physics and mentality: the Turing legacy ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity
Cites Work
- Unnamed Item
- Lower bounds and separations for constant depth multilinear circuits
- Pseudorandom bits for constant depth circuits
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Nondeterministic \(NC^1\) computation
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- Lower bounds on arithmetic circuits via partial derivatives
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- The complexity of constructing pseudorandom generators from hard functions
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Amplifying lower bounds by means of self-reducibility
- Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- The Parallel Complexity of Abelian Permutation Group Problems
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Computing Algebraic Formulas Using a Constant Number of Registers
- Size--Depth Tradeoffs for Threshold Circuits
- The Shrinkage Exponent of de Morgan Formulas is 2
- The Monte Carlo Method
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudo-random generators for all hardnesses
- Depth-3 arithmetic circuits over fields of characteristic zero
