On parity decision trees for Fourier-sparse Boolean functions
Copyright policy )On parity decision trees for Fourier-sparse Boolean functions
We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows: Let \(f : \mathbb {F}_2^n \rightarrow \lbrace -1, 1\rbrace\) be a Boolean function with Fourier support 𝒮 and Fourier sparsity k .
- Schloss Dagstuhl – Leibniz Center for Informatics Germany
- University of Liverpool United Kingdom
- Indian Institute of Technology Kharagpur India
- GEORGETOWN UNIVERSITY
- Leibniz Association Germany
FOS: Computer and information sciences, Data structures, Parity decision trees, 68Q11, Communication complexity, information complexity, Computational Complexity (cs.CC), parity decision trees, 004, log-rank conjecture, Computer Science - Computational Complexity, communication complexity, analysis of Boolean functions, Boolean functions, F.1.1, ddc: ddc:004
FOS: Computer and information sciences, Data structures, Parity decision trees, 68Q11, Communication complexity, information complexity, Computational Complexity (cs.CC), parity decision trees, 004, log-rank conjecture, Computer Science - Computational Complexity, communication complexity, analysis of Boolean functions, Boolean functions, F.1.1, ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!