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 Revisions: 1 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: 2 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 Revisions: 1 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

Revisions: 1

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

TR20-132 | 7th September 2020

#### Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $\Theta(n)$. This improves upon the ... more >>>

TR21-006 | 18th January 2021
Susanna de Rezende, Jakob Nordström, Marc Vinyals

#### How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large ... more >>>

TR21-066 | 5th May 2021
Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

#### Dimension-free Bounds and Structural Results in Communication Complexity

The purpose of this article is to initiate a systematic study of dimension-free relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to ... more >>>

TR22-019 | 17th February 2022
Guangxu Yang, Jiapeng Zhang

#### Simulation Methods in Communication Lower Bounds, Revisited

The notion of lifting theorems is a generic method to lift hardness of one-party functions to two-party lower bounds in communication model. It has many applications in different areas such as proof complexity, game theory, combinatorial optimization. Among many lifting results, a central idea is called Raz-McKenize simulation (FOCS 1997). ... more >>>

TR22-046 | 4th April 2022
Dmitry Itsykson, Artur Riazanov

#### Automating OBDD proofs is NP-hard

We prove that the proof system OBDD(and, weakening) is not automatable unless P = NP. The proof is based upon the celebrated result of Atserias and Muller [FOCS 2019] about the hardness of automatability for resolution. The heart of the proof is lifting with a multi-output indexing gadget from resolution ... more >>>

ISSN 1433-8092 | Imprint