Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PARITY DECISION TREE COMPLEXITY:
Reports tagged with Parity decision tree complexity:
TR14-088 | 13th July 2014
Swagato Sanyal

#### Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

We prove that the Fourier dimension of any Boolean function with
Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof
method yields an improved bound of $\widetilde{O}(\sqrt{s})$
assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every
Boolean function of sparsity $s$ there is an affine subspace of
more >>>

TR18-175 | 23rd October 2018

#### Lifting Theorems for Equality

Revisions: 2

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ EQ_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ EQ_n$ ... more >>>

TR20-132 | 7th September 2020

#### Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $\Theta(n)$. This improves upon the ... more >>>

TR22-041 | 23rd March 2022
TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein

#### Boolean functions with small approximate spectral norm

The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of ... more >>>

ISSN 1433-8092 | Imprint