| The Fourier Entropy–Influence Conjecture for certain classes of Boolean functions — Ryan O'Donnell et al. |
FEI conjecture for symmetric functions
|
|
| Fourier Sparsity and Dimension — Swagato Sanyal |
Dimension of the Fourier spectrum
|
|
| Making Polynomials Robust to Noise — Alexander Sherstov |
Robustification
|
|
| Polynomials with two values - Zur Gathen and Roche |
Degree of symmetric Boolean functions
|
Ayushi |
| On Fractional Block Sensitivity — Avishay Tal, Raghav Kulkarni |
FBS and FC
|
|
| Low-Sensitivity Functions from Unambiguous Certificates — Ben-David, Hatami, Tal |
UC complexity measure
|
|
| Log-rank and lifting for AND-functions — Knop et al. |
Log-Rank Conjecture for AND gadget
|
|
| Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem — Aaronson et al. |
Degree vs approximate degree
|
Subir |
| Randomized versus Deterministic Decision Tree Size -- Chattopadhyay et al. |
Decision tree sizes
|
|
| Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities — Bun and Thaler |
Lower bounds on approximate degree
|
|
| Hardness Condensation by Restriction — Goos et al. |
Hardness condensation
|
|
| Lifting dichotomies — Alekseev et al. |
Lifting from query complexity
|
|
| Degree and Sensitivity: tails of two distributions -- Gopalan et al. |
Sensitivity conjecture
|
|
