Polylogarithmic independence fools AC 0 circuits
From MaRDI portal
Publication:3579633
DOI10.1145/1754399.1754401zbMath1327.68108OpenAlexW2036447017MaRDI QIDQ3579633
Publication date: 9 August 2010
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1754399.1754401
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distribution theory (60E99)
Related Items
Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)], Cryptographic hardness of random local functions. Survey, DNF sparsification and a faster deterministic counting algorithm, Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields], Pseudorandom generators for combinatorial checkerboards, Unnamed Item, On the probabilistic degree of OR over the reals, Paradigms for Unconditional Pseudorandom Generators, Unnamed Item, Unnamed Item, The work of Mark Braverman, Counting Solutions to Polynomial Systems via Reductions, On polynomial approximations to AC, Bounded Independence Plus Noise Fools Products, Small-bias is not enough to hit read-once CNF, Bounded-depth circuits cannot sample good codes, Fourier concentration from shrinkage, Unnamed Item, Unnamed Item, Explicit list-decodable codes with optimal rate for computationally bounded channels, On the Probabilistic Degrees of Symmetric Boolean Functions, Unnamed Item, Fine-Grained Cryptography, Bounded Indistinguishability and the Complexity of Recovering Secrets, Explicit two-source extractors and resilient functions, Unnamed Item, Interactive proofs for social graphs, Mining circuit lower bound proofs for meta-algorithms
