Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PARITY DECISION TREES:
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 >>>


TR22-173 | 3rd December 2022
Paul Beame, Sajin Koroth

On Disperser/Lifting Properties of the Index and Inner-Product Functions

Revisions: 1

Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity ... more >>>


TR24-037 | 26th February 2024
Yaroslav Alekseev, Yuval Filmus, Alexander Smal

Lifting dichotomies

Revisions: 1

Lifting theorems are used for transferring lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure $A$ for some function $f$, we compose $f$ with a carefully chosen gadget function $g$ and get essentially the same lower bound on a complexity measure $B$ for the ... more >>>




ISSN 1433-8092 | Imprint