On the parity complexity measures of Boolean functions

DOI10.1016/j.tcs.2010.03.027zbMath1207.68170OpenAlexW1609754208MaRDI QIDQ974756

Yaoyun Shi, Zhi-Qiang Zhang

Publication date: 7 June 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.03.027

zbMATH Keywords

computational complexitycommunication complexitylog-rank conjectureparity decision tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (13)

On the Decision Tree Complexity of Threshold Functions ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Structure of Protocols for XOR Functions ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ Property testing lower bounds via a generalization of randomized parity decision trees ⋮ On the structure of Boolean functions with small spectral norm ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Counting the number of perfect matchings, and generalized decision trees ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Unnamed Item ⋮ On the decision tree complexity of threshold functions

Cites Work

• Complexity measures and decision tree complexity: a survey.
• CREW PRAM<scp>s</scp> and Decision Trees
• Communication Complexity
• Quantum lower bounds by polynomials
• Unnamed Item
• Unnamed Item

This page was built for publication: On the parity complexity measures of Boolean functions