An elementary proof of a 3n - o(n) lower bound on the circuit complexity of affine dispersers

DOI10.1007/978-3-642-22993-0_25zbMATH Open1343.68092OpenAlexW1756918770MaRDI QIDQ3088045FDOQ3088045

Authors: 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

Recommendations

• Affine dispersers from subspace polynomials
• Affine dispersers from subspace polynomials
• Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
• The complexity of DNF of parities
• The effect of random restrictions on formula size

Mathematics Subject Classification ID

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

Cited In (13)

• New lower bounds on circuit size of multi-output functions
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• On various nonlinearity measures for Boolean functions
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• Affine dispersers from subspace polynomials
• On the limits of gate elimination
• Improving \(3N\) circuit complexity lower bounds
• Resolution over linear equations modulo two
• Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Lower bounds for the size of nondeterministic circuits
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Tight upper bound on splitting by linear combinations for pigeonhole principle

This page was built for publication: An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers

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