Parity Decision Trees of Depth O(4 d f 1) for Boolean Functions f of F 2-Degree d
cs.CC
Submitted: 2026-11-02
Updated: 2026-11-02
Terminology
Sources
- Parity Decision Tree Complexity is Greater Than Granularity
- Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers
- Refuting approaches to the log-rank conjecture for XOR functions
- On the communication complexity of XOR functions
- On parity decision trees for Fourier-sparse Boolean functions
- Schur complements for tensors and multilinear commutative rank
- A composition theorem for parity kill number
- Optimal Unambiguous DNFs and Alon-Saks-Seymour
- Matrix discrepancy and the log-rank conjecture
- Communication Complexities of XOR functions
- Fourier sparsity, spectral norm, and the Log-rank conjecture
- Efficient quantum protocols for XOR functions
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?