Is linear sketching over F2 optimal for one-way XOR communication?

The simplest sketch of a Boolean input is a handful of random parities of its bits. If Alice holds $x$, Bob holds $y$, and Bob must compute $f(x \oplus y)$ after one message, sending such parities of $x$ is a natural protocol. The conjecture says that, up to logarithmic factors, no one-way protocol does better.

Problem

For $S \subseteq [n]$ let $\chi_S(x) = \sum_{i \in S} x_i \bmod 2$. Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$.

• The randomized linear sketch complexity $R^{\mathrm{lin}}_\delta(f)$ is the smallest $k$ for which there are a distribution over $k$-tuples of sets $S_1, \dots, S_k \subseteq [n]$ and a function $g$ such that for every $x$,

$$\Pr_{S_1,\dots,S_k}\big[\, g(\chi_{S_1}(x), \dots, \chi_{S_k}(x)) = f(x) \,\big] \ge 1-\delta .$$

• The XOR function of $f$ is $f^+(x,y) = f(x \oplus y)$. Its randomized one-way communication complexity $R^{\to}_\delta(f^+)$ is the fewest bits Alice must send to Bob, using shared public randomness, so that Bob outputs $f^+(x,y)$ with error at most $\delta$ for every $x, y$.

Sending the $k$ parities of $x$ lets Bob compute those of $x \oplus y$, so $R^{\to}_\delta(f^+) \le R^{\mathrm{lin}}_\delta(f)$.

Conjecture (Kannan, Mossel, Sanyal and Yaroslavtsev). For every $f$ and every $0 < \delta < 1/2$,

$$R^{\to}_\delta(f^+) = \tilde\Theta\big(R^{\mathrm{lin}}_\delta(f)\big),$$

where $\tilde\Theta$ hides polylogarithmic factors. Prove or disprove it.

Background

Linear sketches over $\mathbb{F}_2$ are random non-adaptive parity decision trees, and they give small-space streaming and distributed algorithms for inputs updated by bit flips. The conjecture was stated in the paper that started their systematic study [1] and posed by Grigory Yaroslavtsev at a 2017 workshop in Banff. Its deterministic analogue holds exactly, which is the main reason to expect it: Montanaro and Osborne observed that deterministic one-way complexity of $f^+$ equals the Fourier dimension of $f$, which is also its deterministic sketch complexity [2]. A proof would mean, for example, that one-way lower bounds for XOR functions only need to be proved against parity sketches.

What is known

• Deterministic case. $D^{\to}(f^+) = \dim(f) = D^{\mathrm{lin}}(f)$, where $\dim(f)$ is the dimension of the smallest subspace containing the Fourier support of $f$ [2].
• Uniform inputs. For inputs drawn uniformly at random, one-way complexity and sketch complexity agree up to constant factors and a change of error parameter, both being governed by an approximate Fourier dimension of $f$ [1].
• Classes where it holds [1]: low-degree $\mathbb{F}_2$-polynomials, functions with sparse Fourier spectrum, most symmetric functions (those not too close to a constant or to parity), and recursive majority.
• Streaming. Streaming algorithms over updates modulo 2 can be converted into linear sketches with little loss: [1] shows this for streams of $\tilde O(n)$ uniformly random updates, and Hosseini, Lovett and Yaroslavtsev (2019) for algorithms that must handle $\Omega(n^2)$ updates [3]. Li, Nguyen and Woodruff proved an analogue over the integers, but only for triply exponentially long streams [5].
• Partial functions. For partial functions even the deterministic identity fails, with gaps as large as exponential (Podolskii and Sluch, 2024) [4]; the conjecture concerns total functions.

What would count as progress

• A proof of the conjecture for a new natural class, for example all symmetric functions or all monotone functions, or with a polynomial instead of polylogarithmic loss in general.
• A total function $f$ whose one-way protocol for $f^+$ is provably cheaper than every parity sketch of $f$ by more than polylogarithmic factors, which would refute the conjecture.

References

1. S. Kannan, E. Mossel, S. Sanyal and G. Yaroslavtsev, Linear sketching over $\mathbb{F}_2$, CCC 2018, LIPIcs 102, 8. doi:10.4230/LIPIcs.CCC.2018.8
2. A. Montanaro and T. Osborne, On the communication complexity of XOR functions, 2009. arXiv:0909.3392
3. K. Hosseini, S. Lovett and G. Yaroslavtsev, Optimality of linear sketching under modular updates, CCC 2019, LIPIcs 137, 13. doi:10.4230/LIPIcs.CCC.2019.13
4. V. V. Podolskii and D. Sluch, One-way communication complexity of partial XOR functions, ICALP 2024, LIPIcs 297, 116. doi:10.4230/LIPIcs.ICALP.2024.116
5. Y. Li, H. L. Nguyen and D. P. Woodruff, Turnstile streaming algorithms might as well be linear sketches, STOC 2014, 174–183. doi:10.1145/2591796.2591812

Source

Imported from Sublinear.info, Problem 78, curated by Sublinear.info editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.