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

ISSN 1433-8092 | Imprint