Editing Communication complexity (section)

== Lifting ==

Lifting is a general technique in [[computational complexity theory|complexity theory]] in which a lower bound on a simple measure of complexity is "lifted" to a lower bound on a more difficult measure.

This technique was pioneered in the context of communication complexity by Raz and McKenzie,<ref>{{cite journal |last1=Raz |first1=Ran |author-link1=Ran Raz |last2=McKenzie |first2=Pierre |title=Separation of the Monotone NC Hierarchy |journal=Combinatorica |volume=19 |pages=403–435 |year=1999 |issue=3 |doi=10.1007/s004930050062}}</ref> who proved the first query-to-communication lifting theorem, and used the result to separate the [[Circuit_complexity#Monotone_circuits|monotone]] [[NC (complexity)|NC]] hierarchy.

Given a function <math>f\colon \{0,1\}^n \to \{0,1\}</math> and a gadget <math>g\colon \{0,1\}^a \times \{0,1\}^b \to \{0,1\}</math>, their composition <math>f \circ g\colon \{0,1\}^{na} \times \{0,1\}^{nb} \to \{0,1\}</math> is defined as follows:

:<math>
(f \circ g)(x,y) = f(g(x_{1,1} \cdots x_{1,a}, y_{1,1} \cdots y_{1,b}), \dots, g(x_{n,1} \cdots x_{n,a}, y_{n,1} \cdots y_{n,b})).
</math>

In words, <math>x</math> is partitioned into <math>n</math> blocks of length <math>a</math>, and <math>y</math> is partitioned into <math>n</math> blocks of length <math>b</math>. The gadget is applied <math>n</math> times on the blocks, and the outputs are fed into <math>f</math>. Diagrammatically:

[[File:Lifting-1.svg|center]]

In this diagram, each of the inputs <math>\mathbf{x}_1,\dots,\mathbf{x}_n</math> is {{mvar|a}} bits long, and each of the inputs <math>\mathbf{y}_1,\dots,\mathbf{y}_n</math> is {{mvar|b}} bits long.

A [[Decision tree model|decision tree]] of depth <math>\Delta</math> for <math>f</math> can be translated to a communication protocol whose cost is <math>\Delta \cdot D(g)</math>: each time the tree queries a bit, the corresponding value of <math>g</math> is computed using an optimal protocol for <math>g</math>. Raz and McKenzie showed that this is optimal up to a constant factor when <math>g</math> is the so-called "indexing gadget", in which <math>x</math> has length <math>c \log n</math> (for a large enough constant {{mvar|c}}), <math>y</math> has length <math>n^c</math>, and <math>g(x,y)</math> is the <math>x</math>-th bit of <math>y</math>.

The proof of the Raz–McKenzie lifting theorem uses the method of simulation, in which a protocol for the composed function <math>f \circ g</math> is used to generate a decision tree for <math>f</math>. Göös, Pitassi and Watson<ref>{{cite journal |last1=Göös |first1=Mika |last2=Pitassi |first2=Toniann |author-link2=Toniann Pitassi |last3=Watson |first3=Thomas |title=Deterministic communication vs. partition number |url=https://eccc.weizmann.ac.il/report/2015/050/ |journal=SIAM Journal on Computing |volume=74 |issue=6 |year=2018 |pages=2435–2450 |doi=10.1137/16M1059369}}</ref> gave an exposition of the original proof. Since then, several works have proved similar theorems with different gadgets, such as inner product.<ref>{{cite journal |first1=Arkadev |last1=Chattopadhyay |first2=Michal |last2=Koucký |first3=Bruno |last3=Loff |first4=Sagnik |last4=Mukhopadhyay |title=Simulation theorems via pseudo-random properties |journal=Computational Complexity |volume=28 |issue=4 |pages=617–659 |year=2019 |doi=10.1007/s00037-019-00190-7|doi-access=free |arxiv=1704.06807 }}</ref> The smallest gadget which can be handled is the indexing gadget with <math>c=1+\epsilon</math>.<ref>{{cite conference |first1=Shachar |last1=Lovett |first2=Raghu |last2=Meka |first3=Ian |last3=Mertz |first4=Toniann |last4=Pitassi |author-link4=Toniann Pitassi |first5=Jiapeng |last5=Zhang |title=Lifting with Sunflowers |book-title=13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |publisher=Leibniz International Proceedings in Informatics (LIPIcs) |volume=215 |pages=104:1–104:24 |year=200 |doi=10.4230/LIPIcs.ITCS.2022.104 |doi-access=free |url=https://www.cs.toronto.edu/~mertz/papers/lmmpz20.lifting_with_sunflowers.pdf}}</ref>
Göös, Pitassi and Watson extended the Raz–McKenzie technique to randomized protocols.<ref>{{cite conference |title=Query-to-Communication Lifting for BPP |last1=Göös |first1=Mika |last2=Pitassi |first2=Toniann |author-link2=Toniann Pitassi |last3=Watson |first3=Thomas |book-title=2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) |publisher=IEEE |location=Berkeley, CA |year=2017 |doi=10.1109/FOCS.2017.21 |arxiv=1703.07666 }}</ref>

A simple modification of the Raz–McKenzie lifting theorem gives a lower bound of <math>\Delta \cdot D(g)</math> on the logarithm of the size of a protocol tree for computing <math>f \circ g</math>, where <math>\Delta</math> is the depth of the optimal decision tree for <math>f</math>. Garg, Göös, Kamath and Sokolov extended this to the [[Directed acyclic graph|DAG]]-like setting,<ref>{{cite journal |last1=Garg |first1=Ankit |last2=Göös |first2=Mika |last3=Kamath |first3=Pritish |last4=Sokolov |first4=Dmitry |title=Monotone Circuit Lower Bounds from Resolution |journal=Theory of Computing |volume=16 |year=2020 |pages=13:1–13:30 |url=https://theoryofcomputing.org/articles/v016a013/ |doi=10.4086/toc.2020.v016a013|doi-access=free }}</ref> and used their result to obtain monotone [[Circuit complexity|circuit]] lower bounds. The same technique has also yielded applications to [[proof complexity]].<ref>{{cite conference |title=Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity |last1=de Rezende |first1=Susanna |last2=Meir |first2=Or |last3=Nordström |first3=Jakob |last4=Pitassi |first4=Toniann |author-link4=Toniann Pitassi |last5=Robere |first5=Robere |last6=Vinyals |first6=Marc |book-title=2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |year=2020 |publisher=IEEE |location=Virtual conference |pages=24–30 |doi=10.1109/FOCS46700.2020.00011 |arxiv=2001.02144 }}</ref>

A different type of lifting is exemplified by Sherstov's pattern matrix method,<ref>{{cite journal |last=Sherstov |first=Alexander |title=The pattern matrix method |journal=SIAM Journal on Computing |volume=40 |issue=6 |pages=1969–2000 |year=2011 |doi=10.1137/080733644|arxiv=0906.4291 }}</ref> which gives a lower bound on the quantum communication complexity of <math>f \circ g</math>, where {{mvar|g}} is a modified indexing gadget, in terms of the approximate degree of {{mvar|f}}. The approximate degree of a Boolean function is the minimal degree of a polynomial which approximates the function on all Boolean points up to an additive error of 1/3.

In contrast to the Raz–McKenzie proof which uses the method of simulation, Sherstov's proof takes a ''dual witness'' to the approximate degree of {{mvar|f}} and gives a lower bound on the quantum query complexity of <math>f \circ g</math> using the ''generalized discrepancy method''. The dual witness for the approximate degree of {{mvar|f}} is a lower bound witness for the approximate degree obtained via [[Dual linear program|LP duality]]. This dual witness is massaged into other objects constituting data for the generalized discrepancy method.

Another example of this approach is the work of Pitassi and Robere,<ref>{{cite conference |title=Strongly Exponential Lower Bounds for Monotone Computation |last1=Pitassi |first1=Toniann |author-link1=Toniann Pitassi |last2=Robere |first2=Robert |book-title=STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |year=2017 |publisher=ACM |location=Montreal |pages=1246–1255 |doi=10.1145/3055399.3055478 |url=https://www.cs.utoronto.ca/~toni/Papers/rp-stoc17.pdf}}</ref> in which an ''algebraic gap'' is lifted to a lower bound on [[Alexander Razborov|Razborov]]'s ''rank measure''. The result is a strongly exponential lower bound on the monotone circuit complexity of an explicit function, obtained via the Karchmer–Wigderson characterization<ref>{{cite journal |last1=Karchmer |first1=Mauricio |last2=Wigderson |first2=Avi |author-link2=Avi Wigderson |title=Monotone circuits for connectivity require super-logarithmic depth |journal=SIAM Journal on Discrete Mathematics |volume=3 |issue=2 |pages=255–265 |year=1990 |url=https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/KW90/KW90.pdf |doi=10.1137/0403021}}</ref> of monotone circuit size in terms of communication complexity.