Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > XOR FUNCTIONS:
Reports tagged with XOR functions:
TR11-011 | 1st February 2011
Ming Lam Leung, Yang Li, Shengyu Zhang

Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models

We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin ... more >>>


TR16-044 | 21st March 2016
Kaave Hosseini, Shachar Lovett

Structure of protocols for XOR functions

Revisions: 1

Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.
We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.
This relies on a novel technique ... more >>>


TR22-041 | 23rd March 2022
Tsun-Ming 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 >>>


TR23-157 | 31st October 2023
Vladimir Podolskii, Dmitrii Sluch

One-Way Communication Complexity of Partial XOR Functions

Boolean function $F(x,y)$ for $x,y \in \{0,1\}^n$ is an XOR function if $F(x,y) = f(x\oplus y)$ for some function $f$ on $n$ input bits, where $\oplus$ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known ... more >>>


TR23-203 | 15th December 2023
Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni

Refuting approaches to the log-rank conjecture for XOR functions

The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on potential approaches for establishing the conjecture in the special case of XOR functions, where the communication matrix is lifted from a boolean function, and the rank of ... more >>>




ISSN 1433-8092 | Imprint