On the modulo degree complexity of Boolean functions
From MaRDI portal
Publication:5918108
DOI10.1016/j.tcs.2018.04.049zbMath1433.68175OpenAlexW3022683369MaRDI QIDQ5918108
Publication date: 7 April 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.04.049
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Boolean functions (06E30)
Cites Work
- Constructing Ramsey graphs from Boolean function representations
- An improved lower bound on the sensitivity complexity of graph properties
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- The complexity of Boolean functions in different characteristics
- NP is as easy as detecting unique solutions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The expressive power of voting polynomials
- On the degree of Boolean functions as real polynomials
- Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
- Complexity measures and decision tree complexity: a survey.
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols
- Constant depth circuits, Fourier transform, and learnability
- Learning juntas
- Query-efficient algorithms for polynomial interpolation over composites
- Learning Decision Trees Using the Fourier Spectrum
- Constructing set systems with prescribed intersection sizes
- 3-Query Locally Decodable Codes of Subexponential Length
- Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
- Tighter Relations between Sensitivity and Other Complexity Measures
- Automata, Languages and Programming
