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 |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=59582554&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 59582554 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Apr2011 vid: 54 iid: 4 pid: 68 pub: Association for Computing Machinery artinfo: ui: 59582554 10.1145/1924421.1924446 ppf: 108 ppct: 8 formats: tig: atl: Poly-logarithmic Independence Fools Bounded-Depth Boolean Circuits. aug: au: Braverman, Mark affil: University of Toronto. su: Random numbers Algorithm research Mathematics research Logarithms Boolean algebra Computer science research sug: subj: Random numbers Algorithm research Mathematics research Logarithms Boolean algebra Computer science research ab: 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. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2011 holdings: @attributes: islocal: N |
|---|