Lower bounds beyond DNF of parities
From MaRDI portal
Cites work
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A second step toward the polynomial hierarchy
- A simple proof of Bazzi's theorem
- Affine extractors and AC0-parity
- An improved exponential-time algorithm for k -SAT
- Circuit depth reductions
- Depth-3 circuits for inner product
- Error-bounded probabilistic computations between MA and AM
- Exponential lower bounds for depth three Boolean circuits
- scientific article; zbMATH DE number 3938569 (Why is no real title available?)
- scientific article; zbMATH DE number 1452705 (Why is no real title available?)
- scientific article; zbMATH DE number 7829270 (Why is no real title available?)
- scientific article; zbMATH DE number 7829304 (Why is no real title available?)
- Improved bounds for the sunflower lemma
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Mathematical foundations of computer science 1977. Proceedings 6th symposium, Tatranska Lomnica, September 5--9, 1977
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- On Graph Complexity
- Parity helps to compute majority
- Parity, circuits, and the polynomial-time hierarchy
- Polylogarithmic independence can fool DNF formulas
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Random oracles and non-uniformity
- Rectangles are nonnegative juntas
- Relativized Arthur-Merlin versus Merlin-Arthur games
- Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
- Strong bounds for 3-progressions
- Symmetric alternation captures BPP
- The complexity of depth-3 circuits computing symmetric Boolean functions
- The complexity of DNF of parities
- Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)
- Top-down lower bounds for depth-four circuits
- Top-down lower bounds for depth-three circuits
- Which problems have strongly exponential complexity?
This page was built for publication: Lower bounds beyond DNF of parities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445644)