Name
Abstract | ||
|---|---|---|
We prove a new query-to-communication lifting for randomized protocols, with inner product as gadget. This allows us to use a much smaller gadget, leading to a more efficient lifting. Prior to this work, such a theorem was known only for deterministic protocols, due to Chattopadhyay et al. and Wu et al. The only query-to-communication lifting result for randomized protocols, due to Goos, Pitassi and Watson, used the much larger indexing gadget. proof also provides a unified treatment of randomized and deterministic lifting. Most existing proofs of deterministic lifting theorems use a measure of information known as thickness. In contrast, Goos, Pitassi and Watson used blockwise min-entropy as a measure of information. Our proof uses the blockwise min-entropy framework to prove lifting theorems in both settings in a unified way. |
Year | Venue | Field |
|---|---|---|
2019 | ICALP | Discrete mathematics,Gadget,Search engine indexing,Mathematical proof,Mathematics |
DocType | Citations | PageRank |
Journal | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arkadev Chattopadhyay | 1 | 150 | 19.93 |
| Yuval Filmus | 2 | 275 | 27.33 |
| sajin koroth | 3 | 1 | 3.06 |
| Or Meir | 4 | 66 | 10.47 |
| Toniann Pitassi | 5 | 2282 | 155.18 |