Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with lifting theorems:
TR17-010 | 18th January 2017
Xiaodi Wu, Penghui Yao, Henry Yuen

Raz-McKenzie simulation with the inner product gadget

Revisions: 1

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 >>>

TR17-054 | 22nd March 2017
Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

Lifting randomized query complexity to randomized communication complexity

Revisions: 4

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 >>>

TR19-043 | 12th March 2019
Toniann Pitassi, Morgan Shirley, Thomas Watson

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

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 >>>

TR19-103 | 7th August 2019
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Revisions: 1

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 >>>

TR19-186 | 31st December 2019
Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Revisions: 4

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 >>>

TR20-048 | 16th April 2020
Shachar Lovett, Raghu Meka, Jiapeng Zhang

Improved lifting theorems via robust sunflowers

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 >>>

TR20-099 | 6th July 2020
Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

KRW Composition Theorems via Lifting

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 >>>

TR20-111 | 24th July 2020
Ian Mertz, Toniann Pitassi

Lifting: As Easy As 1,2,3

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 >>>

ISSN 1433-8092 | Imprint