Circuit depth reductions

DOI10.4230/LIPICS.ITCS.2021.24MaRDI QIDQ7229310zbMATH OpenFDO

Authors Alexander Golovnev, Alexander S. Kulikov, Ryan Williams

Publication date 15 April 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2021.24

zbMATH Keywords

circuit complexityformula complexitymatrix rigiditypseudorandomness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A better-than-3n lower bound for the circuit complexity of an explicit function
• A family of graphs with expensive depth-reduction
• A method for obtaining more than quadratic effective lower estimates of complexity of schemes
• A note on matrix rigidity
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• An improved exponential-time algorithm for k -SAT
• Complexity Lower Bounds using Linear Algebra
• Complexity of Boolean functions over bases with unbounded fan-in gates
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Fighting Perebor: new and improved algorithms for formula and QBF satisfiability
• Fourier concentration from shrinkage
• scientific article; zbMATH DE number 3121508 (Why is no real title available?)
• scientific article; zbMATH DE number 37868 (Why is no real title available?)
• scientific article; zbMATH DE number 3532851 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1559525 (Why is no real title available?)
• scientific article; zbMATH DE number 7250146 (Why is no real title available?)
• Improved average-case lower bounds for DeMorgan formula size
• Making polynomials robust to noise
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Norms, XOR lemmas, and lower bounds for polynomials and protocols
• On the limits of gate elimination
• On the limits of sparsification
• On the power of small-depth computation
• Probabilistic polynomials and Hamming nearest neighbors
• Reflections for quantum query algorithms
• Shallow grates
• Shrinkage of De Morgan formulae by spectral techniques
• Shrinkage of de Morgan formulae under restriction
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• The average sensitivity of bounded-depth circuits
• The complexity of depth-3 circuits computing symmetric Boolean functions
• The effect of random restrictions on formula size
• The Hilbert function, algebraic extractors, and recursive Fourier sampling
• The Shrinkage Exponent of de Morgan Formulas is 2
• Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Two structural results for low degree polynomials and applications
• Weight Distribution and List-Decoding Size of Reed–Muller Codes
• Which problems have strongly exponential complexity?

Cited in

(1)

• Low-degree polynomials are good extractors

This page was built for publication: Circuit depth reductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7229310)