| Autor: | Zeev Dvir, Andrej Bogdanov, Amir Yehudayoff, Elad Verbin |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
Pseudorandom number generator Polynomial medicine.medical_treatment Pseudorandomness Upper and lower bounds Theoretical Computer Science Combinatorics Branching (linguistics) Harmonic analysis Computational Theory and Mathematics medicine Pseudorandom generators for polynomials Mathematics |
| Zdroj: | Theory of Computing. 9:283-293 |
| ISSN: | 1557-2862 |
| DOI: | 10.4086/toc.2013.v009a007 |
| Popis: | Recently Bogdanov and Viola (FOCS 2007) and Lovett (ECCC-07) constructed pseudorandom generators that fool degree k polynomials over F2 for an arbitrary constant k. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read k bits of inputs at a time. This model generalizes polynomials of degree k over F2 and includes some other interesting classes of functions, for instance k-DNF. The constructions of Bogdanov and Viola and Lovett consist of adding a constant number of independent copies of a generator that fools linear functions (an -biased set). It is natural to ask, in light of our first result, whether such generators can fool branching programs of width larger than 2. Our second result is a lower bound showing |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|