Additive Combinatorics Approach to Log-Rank Conjecture in Communication Complexity

This research explores an additive combinatorics approach to the log-rank conjecture in communication complexity, addressing the maximum total bits sent on worst-case inputs and known bounds. It discusses the Polynomial Freiman-Ruzsa Conjecture and Approximate Duality, highlighting technical contributions and improved bounds. The study provides insights into communication complexity upper bounds, methodology, and implications of the research findings.

• Combinatorics
• Communication Complexity
• Log-Rank Conjecture
• Polynomial Freiman-Ruzsa
• Approximate Duality

mah_for Follow

Uploaded on Sep 12, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. An additive combinatorics approach to the log-rank conjecture in communication complexity Noga Zewi Technion Israel Institute of Technology Joint work with: Eli Ben-Sasson (Technion and MSR New England) Shachar Lovett (IAS, Princeton)

2. Communication Complexity X : { 0,1} f Y y Y x X Protocol P CC(P) = Max total # of bits sent on worst case inputs. CC(f) = ( ) P M i n C C P

3. Log-rank Conjecture {0,1}X Y M X : { 0,1} f Y = ( , ) f x y M , x y ( ) CC f ( ) CC M ( ) (R ( )) Rank M ank M F 2 Fact. log ( ) ( ) ( ) rank M CC M ran k M Log-rank conjecture. [Lov sz, Saks, FOCS 88] = (1) O ( ) lo g ( ) CC M rank M

4. Known Bounds Lower bounds: = tra ( ) (log ( [Nisan, Wigderson 95] [Kushilevitz 95] )) CC t = t = M nk M log log 23 36 1.585 1.631 Upper bounds: [Kotlov, Lov sz 96] M ( ) ( ) / 2 CC rank M [Kotlov 97] ( ) log(4/3) 0. 5 41 ( ) ) CC M rank nk M ( ra M Main result. Assuming the polynomial Freiman-Ruzsa conjecture, ( ) ( rank M O CC M = ) ( )/log ( ) rank M

5. Polynomial Freiman-Ruzsa Conjecture + = + n 2, { '| , ' a a a } A F A A a A |A+A|=|A| A is a subspace |span(A)|=|A| Question: |A+A|/|A| is small => |span(A)|/|A| is small? Thm. [Ruzsa 99] 4 A A + 2 K | | | | | ( )| 2 | | K A span A K A Thm. [Even-Zohar 11] + 2 k | | | | | ( )| 2 /(2 ) | | A A K A sp an A k A Polynomial Freiman-Ruzsa (PFR) Conjecture. integer r: + r r | | | | ' , | '| | |, | ( ')| n A | '| A A K A A A A K A spa K A Thm. [Sanders 10] = 3 (lo g ) r O K

6. Proof Overview Main tool: Approximte duality [Ben-Sasson, Z. 11, construction of two-source extractors] PFR Conjecture Second part of talk Main technical contribution Improved bounds on approximate duality Uses methodology Suggested by Nisan,Wigderson 95 First part of talk Communication complexity upper bounds

7. Approximate Duality = = n n F , F , 0 A A x a x a A 2 2 Duality measure: = = = ( , ) A B Pr , 1 Pr , 0 D a b a b a A b B a A b B , , A = + ( , ) 1 D A B B B x A ( , ) 0.99 D A B = ' , ' , D A B B ( ', ' ) 1 A A B (Assuming PFR) Thm. [Ben-Sasson, Z. 11] 1 2 n : ( , ) D A B ) 1 = n n ' , ' , | '| 2 | |,| '| 2 | |, ( ', D A B ' A A B B A A B B Main technical lemma. (Assuming PFR) n ( , ) D A B 2 = /log /log cn n cn n ' , ' , | '| 2 | |,| '| 2 | |, ( ', ') D A B 1 A A B B A A B B

8. From Approximate Duality to CC Upper Bounds Discrepancy of a 0-1 matrix M: => M is monochromatic. => M is balanced. ( ) 0 M = submatrix of , ' M |Pr [ = = 1] Pr [ = ( ) 0 ]| M M M , , , , i j i j i j i j ) 1 = Nisan-Wigderson Conjecture. [NW95] ( M ( ) rank M r (1)| O ') 1. = log rM M | '| 2 |, ( M M Thm 1. [NW95] Nisan-Wigderson Conj. Log-rank Conj. = (1) O ( ) lo g ( ) CC M rank M Thm 2. [NW95, spectral methods] submatrix of , ' M ( ) rank M r 3/2 3/2 | '| | |, ( ') . M r M M r M We show: Approximate duality => submatrix of , => '' M ' M | M matrix , . / ( ) cr C C M = M = /log cr r ' '| 2 | ' , | ( '' ) 1 M M l o g r

9. From Approximate Duality to CC upper bounds Goal: submatrix of , '' M 3/2, ( ') ( ') ( ) M r rank M rank M r = /log cr r | ' '| 2 | ' , | ( '' ) 1 M M M ' M Observation 1. Enough to assume and work over ! 2( F ') ( ') ( ) rank M rank M ra nk M r 2( F ') rank M r 2 F Observation 2. 2( F { = ') rank M r = r , , , mod 2) }, { , v v , , } F . . A u u u B v st 1 u 2 v 1 2 2 k = ' , ( M , i j i j Conclusion: => (approximate duality) 3/2 = ( , ) D A B ( ') M r => = /log /log cr r cr r ' , ' , | '| 2 | |, | '| 2 | |, ( ', ') D A 1 A A B B is a submatrix of , A A B B B = T '' ( ') A ' M B = /log cr r | ' '| 2 | ' , | ( '' ) 1 M M M ' M