An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers

DOI10.1007/978-3-642-22993-0_25zbMath1343.68092OpenAlexW1756918770MaRDI QIDQ3088045

Evgeny Demenkov, Alexander S. Kulikov

Publication date: 17 August 2011

Published in: Mathematical Foundations of Computer Science 2011 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22993-0_25

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

On various nonlinearity measures for Boolean functions ⋮ On the limits of gate elimination ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ Lower Bounds for the Size of Nondeterministic Circuits ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Tight Upper Bound on Splitting by Linear Combinations for Pigeonhole Principle ⋮ Resolution over linear equations modulo two ⋮ New lower bounds on circuit size of multi-output functions

This page was built for publication: An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers