Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
From MaRDI portal
Publication:5091770
DOI10.4230/LIPIcs.CCC.2019.19OpenAlexW2965628617MaRDI QIDQ5091770
Publication date: 27 July 2022
Full work available at URL: https://doi.org/10.4230/lipics.ccc.2019.19
Related Items (9)
Weights of exact threshold functions ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Unnamed Item ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Average-case rigidity lower bounds ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Majority gates vs. general weighted threshold gates
- Some simplified NP-complete graph problems
- Approximating threshold circuits by rational functions
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
- Threshold circuits of bounded depth
- Polynomial threshold functions and Boolean threshold circuits
- Theory of majority decision elements
- Natural Proofs versus Derandomization
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Linear-time encodable and decodable error-correcting codes
- Nonuniform ACC Circuit Lower Bounds
- Local Reductions
- Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
- On Threshold Circuits and Polynomial Computation
- Lower bounds on threshold and related circuits via communication complexity
- Bounds for the Computational Power and Learning Complexity of Analog Neural Nets
- Size--Depth Tradeoffs for Threshold Circuits
- New algorithms and lower bounds for circuits with linear threshold gates
- Towards NEXP versus BPP?
- Analysis of Boolean Functions
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Algorithmic polynomials
- Quantified derandomization of linear threshold circuits
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- The PCP theorem by gap amplification
- A note on the simulation of exponential threshold weights
This page was built for publication: Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
