Report

Information Complexity: an Overview Rotem Oshman, Princeton CCI Based on work by Braverman, Barak, Chen, Rao, and others Charles River Science of Information Day 2014 Classical Information Theory • Shannon ‘48, A Mathematical Theory of Communication: Motivation: Communication Complexity , = ? Yao ‘79, “Some complexity questions related to distributive computing” Motivation: Communication Complexity More generally: solve some task (, ) Yao ‘79, “Some complexity questions related to distributive computing” Motivation: Communication Complexity • Applications: – Circuit complexity – Streaming algorithms – Data structures – Distributed computing – Property testing –… Example: Streaming Lower Bounds • Streaming algorithm: How much space is required to approximate f(data)? algorithm data • Reduction from communication complexity [AMS’97] Example: Streaming Lower Bounds • Streaming algorithm: State of the algorithm algorithm data • Reduction from communication complexity [Alon, Matias, Szegedy ’99] Advances in Communication Complexity • Very successful in proving unconditional lower bounds, e.g., – Ω for set disjointness [KS’92, Razborov ‘92] – Ω for gap hamming distance [Chakrabarti, Regev ‘10] • But stuck on some hard questions – Multi-party communication complexity – Karchmer-Wigderson games • [Chakrabarty, Shi, Wirth, Yao ’01], [Bar-Yossef, Kumar, Jayram, Srivakumar ‘04]: use tools from information theory Extending Information Theory to Interactive Computation • One-way communication: – Task: send across the channel – Cost: bits • Shannon: in the limit over many instances • Huffman: + 1 bits for one instance • Interactive computation: – Task: e.g., compute , – Cost? Information Cost • Reminder: mutual information ; = − = − • Conditional mutual information: ; = − , = ; = • Basic properties: – ; ≥ 0 – ; ≤ and ; ≤ – Chain rule: ; = ; + ; Information Cost • Fix a protocol Π • Notation abuse: let Π also denote the transcript of the protocol • Two ways to measure information cost: – External information cost: Π; – Internal information cost: Π; + Π; – Cost of a task: infimum over all protocols – Which cost is “the right one”? Information Cost: Basic Properties External information: Π; Internal information: Π; + Π; • Internal ≤ external • Can be much smaller, e.g.: – = uniform over 0,1 – Π: Alice sends to Bob • But equal if , inependent Information Cost: Basic Properties External information: Π; Internal information: Π; + Π; • External information ≤ communication: Π; ≤ Π ≤ Π . Information Cost: Basic Properties • Internal information ≤ communication cost: Π; + (Π; |) ≤ Π . • By induction: let Π = Π1 … Π . • ∀ ≤ : Π≤ ; + Π≤ ; ≤ . Π≤ ; + Π≤ ; what we know after r rounds = Π< ; + Π< ; what we knew after r-1 rounds I.H. ≤ − 1 + Π ; Y X, Π< + Π ; X Y, Π< what we learn in round r, given what we already know Information vs. Communication • Want: Π ; Y X, Π< + Π ; X Y, Π< ≤ 1. • Suppose Π is sent by Alice. • What does Alice learn? – Π is a function of Π< and , so Π ; Y X, Π< = 0. • What does Bob learn? – Π ; Y X, Π< ≤ Π = 1. Information vs. Communication • We have: Internal information ≤ communication External information ≤ communication Internal information ≤ external information Information vs. Communication • “Information cost = communication cost”? – In the limit: internal information! [Braverman, Rao ‘10] – For one instance: external information! [Braverman, Barak, Rao, Chen ‘10] Big question: can protocols be compressed down to their internal information cost? – [Ganor, Kol, Raz ’14]: no! – There is a task with internal IC=, CC=2 . … but: remains open for functions, small output. Information vs. Amortized Communication • Theorem [Braverman, Rao ‘10]: • • • • ( , , ) lim = , , . →∞ The “≤” direction: compression The “≥” direction: direct sum We know: , , ≥ , , We can show: , , = ⋅ , , Direct Sum Theorem [BR‘10] , , = ⋅ , , : • Let Π be a protocol for on -copy inputs , • Construct Π′ for as follows: – Alice and Bob get inputs , – Choose a random coordinate ∈ , set = , = – Bad idea: publicly sample − , − Direct Sum Theorem [BR‘10] , , = ⋅ , , : • Let Π be a protocol for on -copy inputs , • Construct Π′ for as follows: – Alice and Bob get inputs , – Choose a random coordinate ∈ , set = , = – Bad idea: publicly sample − , − Suppose in Π, Alice sends 1 ⊕ ⋯ ⊕ . In Π, Bob learns one bit ⇒ in Π ′ he should learn 1/ bit But if − is public Bob learns 1 bit about ! Direct Sum Theorem [BR‘10] , , = ⋅ , , : • Let Π be a protocol for on -copy inputs , • Construct Π′ for as follows: – Alice and Bob get inputs , – Choose a random coordinate ∈ , set = , = Publicly sample 1 , … , −1 Privately sample (+1) , … , Privately sample 1 , … , −1 Publicly sample +1 , … , Compression • What we know: a protocol with communication , internal info and external info can be compressed to – ⋅ polylog [BBCR’10] – ⋅ ⋅ polylog [BBCR’10] – 2 [Braverman’10] • Major open question: can we compress to ⋅ polylog ? [GKR, partial answer: no] Using Information Complexity to Prove Communication Lower Bounds • Internal/external info ≤ communication • Essentially the most powerful technique known [Kerenidis,Laplante,Lerays,Roland,Xiao’12]: most lower bound techniques imply IC lower bounds • Disadvantage: hard to show incompressibility! – Must exhibit problem with low IC, high CC – But proving high CC usually proves high IC… Extending IC to Multiple Players • Recent interest in multi-player number-inhand communication complexity • Motivated by “big data”: – Streaming and sketching, e.g., [Woodruff, Zhang ‘11,’12,’13] – Distributed learning, e.g., [Awasthi, Balcan, Long ‘14] Extending IC to Multiple Players • Multi-player computation traditionally hard to analyze • [Braverman,Ellen,O.,Pitassi,Vaikuntanathan]: Ω for Set Disjointness with elements, players, private channels, NIH input Information Complexity on Private Channels • First obstacle: secure multi-party computation • [Goldreich,Micali,Wigderson’87]: any function can be computed with perfect information-theoretic security against < /2 players – Solution: redefine information cost, measure both • Information a player learns, and • Information a player leaks to all the others. Extending IC to Multiple Players • Set disjointness: – Input: 1 , … , – Output: 1 ∩ ⋯ ∩ = ∅? • Open problem: can we extend to gap set disjointness? – First step: “purely info-theoretic” 2-party analysis Extending IC to Multiple Players • In [Braverman,Ellen,O.,Pitassi,Vaikuntanathan] we show direct sum for multi-party – Solving instances = ⋅ solving one instance • Does direct sum hold “across players”? – Solving with players = Ω ⋅ solving with 2 players? – Not always • Does compression work for multi-party? Conclusion • Information complexity extends classical information theory to the interactive setting • Picture is much less well-understood • Powerful tool for lower bounds • Fascinating open problems: – Compression – Information complexity for multi-player computation, quantum communication, …