Xiaodi Wu, Penghui Yao, Henry Yuen

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>>

Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

We show that for any (partial) query function $f:\{0,1\}^n\rightarrow \{0,1\}$, the randomized communication complexity of $f$ composed with $\mathrm{Index}^n_m$ (with $m= \poly(n)$) is at least the randomized query complexity of $f$ times $\log n$. Here $\mathrm{Index}_m : [m] \times \{0,1\}^m \rightarrow \{0,1\}$ is defined as $\mathrm{Index}_m(x,y)= y_x$ (the $x$th bit ... more >>>

Toniann Pitassi, Morgan Shirley, Thomas Watson

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... more >>>

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open ... more >>>

Shachar Lovett, Raghu Meka, Jiapeng Zhang

Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are ... more >>>

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $f ... more >>>

Ian Mertz, Toniann Pitassi

Query-to-communication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the tree-like and dag-like settings). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with ... more >>>