Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Parity Decision Trees:
TR14-115 | 27th August 2014
Roei Tell

Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees

Revisions: 1

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication ... more >>>

TR20-119 | 1st August 2020
Nikhil Mande, Swagato Sanyal

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 \to \{-1, 1\}$ be a Boolean function with Fourier support ... more >>>

ISSN 1433-8092 | Imprint