Improved bounds on the an-complexity of \(O(1)\)-linear functions

DOI10.1007/s00037-022-00224-7OpenAlexW4283319830MaRDI QIDQ2159467

Oded Goldreich

Publication date: 1 August 2022

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-022-00224-7

zbMATH Keywords

arithmetic circuitsmultilinear circuitsrestricted models of computation

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Boolean function complexity. Advances and frontiers.
• Lower bounds on arithmetic circuits via partial derivatives
• Matrix rigidity of random Toeplitz matrices
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• On ε‐biased generators in NC⁰
• Computational Complexity

This page was built for publication: Improved bounds on the an-complexity of \(O(1)\)-linear functions