On the parity complexity measures of Boolean functions

Abstract

The parity decision tree model extends the decision tree model by allowing the computation of a parity function in one step. We prove that the deterministic parity decision tree complexity of any Boolean function is polynomially related to the non-deterministic complexity of the function or its complement. We also show that they are polynomially related to an analogue of the block sensitivity. We further study parity decision trees in their relations with an intermediate variant of the decision trees, as well as with communication complexity.

submitted to TCS on 16-MAR-2009

References in corpus (1)

• Communication Lower Bounds Using Dual Polynomials

Cited by in corpus (13)

• The non-adaptive query complexity of testing k-parities
• Variations on the Sensitivity Conjecture
• Fourier sparsity, spectral norm, and the Log-rank conjecture
• Recent advances on the log-rank conjecture in communication complexity
• Parity Decision Tree Complexity is Greater Than Granularity
• Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps
• A composition theorem for parity kill number
• Truth Table Minimization of Computational Models
• Linear Sketching over ${\mathbb{F}}_2$
• Sensitivity, Affine Transforms and Quantum Communication Complexity
• A Generalization of a Theorem of Rothschild and van Lint
• The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries
• Approximate ${\mathbb{F}}_2$-Sketching of Valuation Functions