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

DOI10.1007/978-3-642-22993-0_25MaRDI QIDQ3088045zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(13)

• Tight upper bound on splitting by linear combinations for pigeonhole principle
• 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
• On the limits of gate elimination
• Affine dispersers from subspace polynomials
• 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
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Lower bounds for the size of nondeterministic circuits

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)