Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
From MaRDI portal
Publication:5080481
DOI10.1137/20M1364886OpenAlexW3013398713MaRDI QIDQ5080481
Publication date: 31 May 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1364886
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- Cryptography in constant parallel time
- On approximate majority and probabilistic time
- Boolean function complexity. Advances and frontiers.
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- One way functions and pseudorandom generators
- Random oracles separate PSPACE from the polynomial-time hierarchy
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Majority gates vs. general weighted threshold gates
- Hardness vs randomness
- Exploring crypto dark matter: new simple PRF candidates and their applications
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Average-case rigidity lower bounds
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- An average-case lower bound against \(\mathsf{ACC}^0\)
- Threshold circuits of bounded depth
- Pseudorandomness and average-case complexity via uniform reductions
- Natural Proofs versus Derandomization
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Algebrization
- Linear-time encodable and decodable error-correcting codes
- Proof verification and the hardness of approximation problems
- Nonuniform ACC Circuit Lower Bounds
- Parity, circuits, and the polynomial-time hierarchy
- On the Power of Small-Depth Computation
- The Complexity of Local List Decoding
- Simple extractors for all min-entropies and a new pseudorandom generator
- Circuit Lower Bounds for Merlin–Arthur Classes
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- Probabilistic checking of proofs
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Computing Partitions with Applications to the Knapsack Problem
- Separating Nondeterministic Time Complexity Classes
- Algebraic methods for interactive proof systems
- IP = PSPACE
- New algorithms and lower bounds for circuits with linear threshold gates
- A polynomial restriction lemma with applications
- Garbled Circuits as Randomized Encodings of Functions: a Primer
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
- Short PCPs with Projection Queries
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Algorithmic polynomials
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Computational Complexity
- Hardness Amplification Proofs Require Majority
- Extractors and pseudorandom generators
- Cryptography in $NC^0$
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
- Computational Complexity
- Natural proofs
- Pseudorandom generators without the XOR lemma
- Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
This page was built for publication: Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
