Direct sums for parity decision trees
From MaRDI portal
No records found.
Cites work
- A new minimax theorem for randomized algorithms
- A strong direct sum theorem for distributional query complexity
- A tight composition theorem for the randomized query complexity of partial functions (extended abstract)
- Amortized Communication Complexity
- Analysis of Boolean Functions
- Better boosting of communication oracles, or not
- Boolean functions with small approximate spectral norm
- Exponential separation between powers of regular and general resolution over parities
- Exponential separation of information and communication for Boolean functions
- Fourier growth of communication protocols for XOR functions
- Fourier growth of parity decision trees
- Fourier sparsity and dimension
- Fourier sparsity, spectral norm, and the log-rank conjecture
- How to compress interactive communication
- scientific article; zbMATH DE number 524134 (Why is no real title available?)
- scientific article; zbMATH DE number 2038719 (Why is no real title available?)
- scientific article; zbMATH DE number 6913819 (Why is no real title available?)
- scientific article; zbMATH DE number 7758330 (Why is no real title available?)
- scientific article; zbMATH DE number 7711600 (Why is no real title available?)
- scientific article; zbMATH DE number 7789151 (Why is no real title available?)
- Title not available (Why is no real title available?)
- Improved direct product theorems for randomized query complexity
- Information Equals Amortized Communication
- Information lower bounds via self-reducibility
- Learning Decision Trees Using the Fourier Spectrum
- Lifting dichotomies
- Lifting to parity decision trees via stifling
- On disperser/lifting properties of the index and inner-product functions
- On parity decision trees for Fourier-sparse Boolean functions
- On the parity complexity measures of Boolean functions
- On the structure of Boolean functions with small spectral norm
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Optimal separation and strong direct sum for randomized query complexity
- Proving unsatisfiability with hitting formulas
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Randomised composition and small-bias minimax
- Randomized query composition and product distributions
- Refuting approaches to the log-rank conjecture for XOR functions
- Resolution over linear equations modulo two
- Simplified separation of information and communication
- Structure of protocols for XOR functions
- Towards proving strong direct product theorems
This page was built for publication: Direct sums for parity decision trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296766)
