Poly-logarithmic Independence Fools Bounded-Depth Boolean Circuits. - Braverman, Mark (Communications of the ACM, 2011)
The article discusses forms of mathematical randomness and their detection by algorithms, aspects of which reportedly underlie the modern theory of computer science. The authors present their progress on isolating random sequences that escape detection by algorithms. Aspects of bounded-depth circuits and low-degree multivariate polynomials also are discussed and a proof of a connection between the 2 is presented. Following the introduction, the article presents an overview of the proof and analytical and algebraic connections between low-depth circuits and polynomials.