AC0 Unpredictability
| Autor: | Emanuele Viola |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Combinatorics
Distribution (mathematics) Computational Theory and Mathematics 010201 computation theory & mathematics Entropy (information theory) Context (language use) 0102 computer and information sciences Function (mathematics) Binary logarithm 01 natural sciences Theoretical Computer Science Mathematics |
| Zdroj: | ACM Transactions on Computation Theory. 13:1-8 |
| ISSN: | 1942-3462 1942-3454 |
| DOI: | 10.1145/3442362 |
| Popis: | We prove that for every distribution D on n bits with Shannon entropy ≥ n − a , at most O (2 d a log d +1 g )/γ 5 of the bits D i can be predicted with advantage γ by an AC 0 circuit of size g and depth D that is a function of all of the bits of D except D i . This answers a question by Meir and Wigderson, who proved a corresponding result for decision trees. We also show that there are distributions D with entropy ≥ n − O (1) such that any subset of O ( n / log n ) bits of D on can be distinguished from uniform by a circuit of depth 2 and size poly( n ). This separates the notions of predictability and distinguishability in this context. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|