Poly-logarithmic Independence Fools Bounded-Depth Boolean Circuits.
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 circuit...
| Publicado en: | Communications of the ACM Vol. 54; no. 4; pp. 108 - 116 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Apr2011
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| Sumario: | 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. |
|---|