\(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
From MaRDI portal
Publication:1671999
DOI10.1016/j.jcss.2018.04.006zbMath1398.68159OpenAlexW2805951067MaRDI QIDQ1671999
Ning Xie, Mahdi Cheraghchi, Karl Wimmer, Elena Grigorescu, Brendan Juba
Publication date: 7 September 2018
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2018.04.006
Related Items (2)
Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Approximate Degree in Classical and Quantum Computing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom bits for constant depth circuits
- Reducing the seed length in the Nisan-Wigderson generator
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Approximate inclusion-exclusion
- Hardness vs randomness
- On the degree of Boolean functions as real polynomials
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Threshold circuits of bounded depth
- Efficient learning algorithms yield circuit lower bounds
- Certifying polynomials for AC^0(parity) circuits, with applications
- Constant depth circuits, Fourier transform, and learnability
- On Graph Complexity
- Simple extractors for all min-entropies and a new pseudorandom generator
- Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
- On Learning, Lower Bounds and (un)Keeping Promises
- Hardness Amplification Proofs Require Majority
- Pseudo-random generators for all hardnesses
This page was built for publication: \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
