Under the auspices of the Computational Complexity Foundation (CCF)

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

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