## Communication Complexity - Monsoon Semester (2011-12)

Time: Wed 11-12:30 and Fri 14-15:30 (@ TIFR) and Tue-Fri 9:30-11 (@ IMSc)
Location: A-212 (@ TIFR) and Room 327(@ IMSc)
Instructors: & (TIFR) / & (IMSc)

#### Problem Sets

1. Problem Set 1 [pdf] (Due: 21 Sep, 2011 (TIFR) / 30 Sep, 2011 (IMSc))
2. Problem Set 2 [pdf] (Due: 28 Oct, 2011)
3. Seminar [pdf] (Potential topics: [BJR07, BR11a, BR11b, CCM08, CCM10, CK11, GS10, JKR09, JKS03, JKZ10, LZ10, Pat11, PD06, She10])
4. Problem Set 3 [pdf] (Due: 16 Dec, 2011 (TIFR) / 21 Dec, 2011 (IMSc))

#### Lectures

1. Introduction to communication complexity
(TIFR: 5 Aug/Jaikumar; IMSc: 26 Aug/Prahladh)
The two-party communication model (deterministic, randomized, public and private coins), Equality, Disjointness.
Ref: [KN97 (§ 1.1-1.3, 3.1)]
Lecture Notes (by Sajin Koroth): [pdf]
2. Monotone Depth lower bound for matching
(TIFR: 10 Aug/Jaikumar; IMSc: 29 Aug/Prahladh)
Fooling set argument; connections to formula depth (Karchmer-Wigderson games), Raz-Wigderson monotone depth lower bound for matching.
Ref: [KN97 (§ 10.1-10.3)]
Lecture Notes (by Nitin Saurabh): [pdf]
3. Non-deterministic communication complexity
(TIFR: 12 Aug/Jaikumar; IMSc: 30 Aug/Prahladh)
Non-deterministic communication complexity, relationship to deterministic case: D(f) <= O(N(f).N(f)), tight example (DISJk,n); rank argument.
Ref: [KN97 (§ 2.1, 2.3, 1.4, 2.5)]
Lecture Notes (by Abhishek Bhrushundi): [pdf (draft)]
4. Applications to VLSI design and time-space tradeoffs
(TIFR: 17 Aug/Jaikumar+Prahladh; IMSc: 6 Sep/Meena)
T√ A lower bound for VLSI, time-space tradeoffs for multi-tape Turing machines, time lower bound for 1-tape Turing machines.
Ref: [KN97 (§ 8.3, 12.1, 12.1)]
Lecture Notes (by Sagnik Mukhopadhyay): [pdf]
5. Applications to streaming
(TIFR: 19 Aug/Prahladh, IMSc: 9 Sep/Meena)
Streaming algorithms, frequency moments (Alon-Matias-Szegedy), lower bounds using disjointness; intro. to combinatorial auctions.
Ref: [AMS99, Lee10 (Lec. 7), Ind07 (Lec. 9), BN07 (§ 11.1, 11.2, 11.6)]
Lecture Notes (by Girish Varma): [pdf]
6. Applications to auctions
(TIFR: 2 Sep/Jaikumar, IMSc: 13 Sep/Prahladh)
Auctions: optimal allocation requires exponential many queries; expressing combinatorial optimization problems by LPs (Yannakakis).
Ref: [BN07 (§ 11.1, 11.2, 11.6), Yan91]
Lecture Notes (by Nikhil Balaji) : [pdf]
7. Applications to linear programming
(TIFR: 2 Sep/Jaikumar, IMSc: 13 Sep/Prahladh)
Expressing combinatorial optimization problems by LPs, monotone rank, connection to communication complexity (Yannakakis).
Ref: [Yan91]
Lecture Notes (and Yadu Vasudev): [pdf (draft)]
8. Distributional communication complexity
distributional communication complexity, characterization of public coins randomized complexity using minmax theorem, discrepancy, inner product.
Ref: [KN97 (§ 3.3-3.5)]
Lecture Notes (by Pranabendu Misra): [pdf]
9. Disjointness over product distributions
Corruption bound; Babai-Frankl-Simon result: lower bound for disjointness over product distribution and a near matching upper bound.
Ref: [BFS86, CP10]
Lecture Notes (by Gaurav Rattan): [pdf]
10. Index function
(TIFR: 14 Sep/Jaikumar, IMSc: 27 Sep/Meena)
primer on information theory; one-way communication complexity of index function; variant when Bob is allowed to send k bits.
Lecture Notes (by Fahad Panolan): [pdf]
11. Pointer chasing
(TIFR: 16 Sep/Jaikumar, IMSc: 30 Sep/Meena)
Pointer chasing problem: k rounds vs. k-1 rounds, upper bounds
Ref: [DJS98, PRV01]
Lecture Notes (by Sagnik Mukhopadhyay): [pdf (draft)]
12. Disjointness
(TIFR: 21 Sep/Jaikumar, IMSc: 4 Oct/Meena)
Pointer chasing (contd.) - matching lower bounds; disjointness lower bound using information theory.
Ref: [PRV01, BJKS04]
Lecture Notes (by Swagato Sanyal): [pdf (draft)]
13. Hellinger distance
(TIFR: 23 Sep/Prahladh, IMSc: 7 Oct/Meena)
Hellinger distance: definition and properties; disjointness lower bound, multi-party (NIH) disjointness lower bound.
Ref: [BJKS04]
Lecture Notes (by Girish Varma): [pdf]
14. Lower bound for norm estimation
(TIFR: 28 Sep/Prahladh, IMSc: 11 Oct/Meena)
Lower bound for approximating L norm, generalizing this result via Poincare inequalities.
Ref: [SS02, BJKS04, AJP10]
Lecture Notes (by Rakesh Venkat): [pdf]
15. Direct Sum (Part I) - introduction
Introduction to direct sum, message compression, protocol compression, direct sum over general distributions.
Ref: [KN97 (§ 4.1), BBCR10]
Lecture Notes (by Abhishek Dang): [pdf (draft)]
16. Direct Sum (Part II) - protocol compression
Protocol compression, direct sum over general distributions: Dμn(f(n)) > √n * Dμ(f).
Ref: [BBCR10]
Lecture Notes (by S. Raja): [pdf (draft)]
17. Direct Sum (Part III) - product distributions
Rejection sampling, direct sum over product distributions: Dμn(f(n)) > n * Dμ(f) for product μ.
Ref: [BBCR10]
Lecture Notes (by Karteek Sreenivasaiah): [pdf (draft)]
18. Direct Sum (Part IV) - conclusion
Near optimal protocol compression over product distributions.
Ref: [BBCR10]
Lecture Notes (by Sajin Koroth): [pdf (draft)]
19. Monotone depth lower bound for s-t connectivity
(TIFR: 14 Oct/Jaikumar, IMSc: 25 Oct/Meena)
Depth+(DSTConnn)=Ω(log2 n): FORK relation, FORK reduces to KWDSTConn, lower bound for FORK using round elimination and amplification.
Ref: [KN97 (§ 10.3, 5.3)]
Lecture Notes (by Nitin Saurabh): [pdf]
20. Predecessor searching problem (part I)
(TIFR: 19 Oct/Jaikumar, IMSc: 28 Oct/Meena)
Reduction to communication problem; (2t,a,b)-protocol for determining the rank and *parity* of the rank of u in S
Ref: [Sen03, SV08]
Lecture Notes (by Swagato Sanyal): [pdf]
21. Predecessor searching problem (part II)
(TIFR: 21 Oct/Jaikumar, IMSc: 1 Nov/Meena)
Randomized communication complexity lower bound using average encoding theorem and round elimination.
Ref: [Sen03, SV08]
Lecture Notes (by Pranabendu Misra): [pdf]
22. Lower bounds for partial sums
(TIFR: 28 Oct/Jaikumar, IMSc: 4 Nov/Meena)
Ref: [PD04]
Lecture Notes (by Fahad Panolan): [pdf]
23. The gap-Hamming problem (part I)
(TIFR: 2 Nov/Jaikumar, IMSc: 8 Nov/Meena)
Introduction to gap-Hamming problem, Sherstov's proof of Ω(n) lower bound due to Chakrabarti-Regev
Ref: [CR11, She11a]
Lecture Notes (by Abhishek Dang): [pdf]
24. The gap-Hamming problem (part II)
(TIFR: 4 Nov/Jaikumar, IMSc: 11 Nov/Meena)
Ω(n) lower bound, Connection to counting #distinct elements, Easier 1-way lower bound
Ref: [CR11, She11a, Woo04, JKS08]
Lecture Notes (by S. Raja): [pdf]
25. Degree/discrepancy method
Discrepancy bound, Bounding discrepancy via threshold degree, separating AC0 from depth 2 majority circuits.
Ref: [She08]
Lecture Notes (by Sajin Koroth): [pdf]
26. Pattern matrix method
Generalized discrepancy method, approximate degree, pattern matrix.
Ref: [She08]
Lecture Notes (by Nitin Saurabh): [pdf]
27. Multiparty communication - NOF model
(TIFR: 16 Nov/Jaikumar, IMSc: 18 Nov/Prahladh)
Number-on-forehead model, cylinder intersections, discrepany bounds, generalized inner product (GIP).
Ref: [KN97 (§ 6.1-6.4)]
Lecture Notes (by Fahad Panolan): [pdf]
28. Multiparty communication complexity of disjointness (part I)
(TIFR: 21 Nov/Jaikumar, IMSc: 25 Nov/Meena)
Reduction to corelation of cylinder intersections with parity of disjointness.
Ref: [She11b]
Lecture Notes (by Swagato Sanyal): [pdf (draft)]
29. Multiparty communication complexity of disjointness (part II)
(TIFR: 23 Nov/Jaikumar, IMSc: 29 Nov/Meena)
Corelation of cylinder intersections with parity of disjointness.
Ref: [She11b]
Lecture Notes (by Sagnik Mukhopadhyay): [pdf (draft)]
30. Other lower bound methods
(TIFR: 25 Nov/Prahladh, IMSc: 2 Dec/Meena)
Lower bounds methods using duality: norm-based approaches, partition bound. Wrap-up of course - what we did not cover!
Ref: [LS09, JK10]
Lecture Notes (by Meena Mahajan): [pdf (draft)]

(Tentative) Course Schedule with list of potential topics

1. Introduction and applications (9 lectures)
2. Information theoretic methods (9 lectures)
3. Data structures lower bounds (4 lectures)
4. The gap-Hamming problem (2 lectures)
5. Lower bounds using norms, pattern matrix methods, partition bound (6 lectures)

#### Student Presentations

• Swagato Sanyal (30 Nov @ TIFR): [BR11b]
• Sajin Koroth (2 Dec @ IMSc): [BR11a]
• Pranabendu Misra (2 Dec @ IMSc): [Pat11]
• Nitin Saurabh (5 Dec @ IMSc): [JKR09]
• S Raja (6 Dec @ IMSc): [JKS03]
• Fahad Panolan (6 Dec @ IMSc): [She10]
• Abhishek Dang (6 Dec @ IMSc): [BR11b]
• Sagnik Mukhopadhyay (10 Dec @ TIFR): [JKZ10]

#### Requirements

Students taking the course for credit will be expected to:

• Do problem sets (approx 1 pset every month)
• Present a paper at the end of the course.
• Scribe lectures notes in LATEX (approx 1 lecture per month) (sample: sample.tex).
Scribe Preferences : TIFR / IMSc