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)
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm

Course Announcement

TIFR Course Calendar (subscribe (ical)) / IMSc Course Calendar (subcribe (ical))

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
    (TIFR: 7 Sep/Jaikumar+Prahladh, IMSc: 16 Sep/Prahladh)
    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
    (TIFR: 9 Sep/Prahladh, IMSc: 20 Sep/Prahladh)
    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
    (TIFR: 30 Sep/Prahladh, IMSc: 14 Oct/Prahladh)
    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
    (TIFR: 5 Oct/Prahladh, IMSc: 17 Oct/Prahladh)
    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
    (TIFR: 7 Oct/Prahladh, IMSc: 18 Oct/Prahladh)
    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
    (TIFR: 12 Oct/Prahladh, IMSc: 21 Oct/Prahladh)
    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
    (TIFR: 9 Nov/Prahladh, IMSc: 14 Nov/Prahladh)
    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
    (TIFR: 11 Nov/Prahladh, IMSc: 15 Nov/Prahladh)
    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

Requirements

Students taking the course for credit will be expected to:

References

This list of references was generated using bibtex2html 1.96.

[AB09] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. [ bib ]
[AJP10] Alexandr Andoni, T. S. Jayram, and Mihai Patrascu. Lower bounds for edit distance and product metrics via Poincaré-type inequalities. In Proc. 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 184-192, 2010. [ bib | .pdf ]
[AMS99] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Computer and System Sciences, 58(1):137-147, 1999. (Preliminary Version in 28th STOC, 1996). [ bib | DOI ]
[BBCR10] Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Proc. 42nd ACM Symp. on Theory of Computing (STOC), pages 67-76, 2010. [ bib | DOI ]
[BFS86] László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). In Proc. 27th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 337-347, 1986. [ bib | DOI | .pdf ]
[BJKS04] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Computer and System Sciences, 68(4):702-732, June 2004. (Preliminary Version in 43rd FOCS, 2002). [ bib | DOI ]
[BJR07] Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms. In Proc. 39th ACM Symp. on Theory of Computing (STOC), pages 689-698, 2007. [ bib | DOI ]
[BN07] Liad Blumrosen and Noam Nisan. Combinatorial auctions. In Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors, Algorithmic Game Theory, chapter 11, pages 267-300. Cambridge University Press, 2007. [ bib | .pdf ]
[BR11a] Mark Braverman and Anup Rao. Information equals amortized communication, 2011. [ bib | arXiv ]
[BR11b] Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In Proc. 43rd ACM Symp. on Theory of Computing (STOC), pages 159-166, 2011. [ bib | DOI ]
[CCM08] Amit Chakrabarti, Graham Cormode, and Andrew McGregor. Robust lower bounds for communication and stream computation. In Proc. 40th ACM Symp. on Theory of Computing (STOC), pages 641-650, 2008. [ bib | DOI ]
[CCM10] Amit Chakrabarti, Graham Cormode, and Andrew McGregor. A near-optimal algorithm for estimating the entropy of a stream. ACM Transactions on Algorithms, 6(3), 2010. (Preliminary version in 18th SODA, 2007). [ bib | DOI ]
[CK11] Amit Chakrabarti and Ranganath Kondapally. Everywhere-tight information cost tradeoffs for augmented index. In Leslie Ann Goldberg, Klaus Jansen, R. Ravi, and José D. P. Rolim, editors, Proc. 15th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), volume 6845 of LNCS, pages 448-459. Springer, 2011. [ bib | DOI ]
[CP10] Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness. SIGACT News, 41(3):59-85, 2010. [ bib | DOI ]
[CR11] Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of gap-Hamming-distance. In Proc. 43rd ACM Symp. on Theory of Computing (STOC), pages 51-60, 2011. [ bib | DOI | arXiv ]
[DJS98] Carsten Damm, Stasys Jukna, and Jiri Sgall. Some bounds on multiparty communication complexity of pointer jumping. Comput. Complexity, 7(2):109-127, 1998. (Preliminary Version in 13th STACS, 1996). [ bib | DOI ]
[GS10] Dmitry Gavinsky and Alexander A. Sherstov. A separation of NP and coNP in multiparty communication complexity. Theory of Computing, 6(1):227-245, 2010. [ bib | DOI ]
[Ind07] Piotr Indyk. 6.895: Sketching, Streaming and Sub-linear space algorithms, 2007. A course offered at MIT (Fall 2007). [ bib | .html ]
[JK10] Rahul Jain and Hartmut Klauck. The partition bound for classical communication complexity and query complexity. In Proc. 25th IEEE Conference on Computational Complexity, pages 247-258, 2010. [ bib | DOI | arXiv ]
[JKR09] T. S. Jayram, Swastik Kopparty, and Prasad Raghavendra. On the communication complexity of read-once AC0 formulae. In Proc. 24th IEEE Conference on Computational Complexity, pages 329-340, 2009. [ bib | DOI ]
[JKS03] T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In Proc. 35th ACM Symp. on Theory of Computing (STOC), pages 673-682, 2003. [ bib | DOI ]
[JKS08] T. S. Jayram, Ravi Kumar, and D. Sivakumar. The one-way communication complexity of Hamming distance. Theory of Computing, 4(1):129-135, 2008. [ bib | DOI ]
[JKZ10] Rahul Jain, Hartmut Klauck, and Shengyu Zhang. Depth-independent lower bounds on the communication complexity of read-once boolean formulas. In My T. Thai and Sartaj Sahni, editors, Proc. of 16th Annual International Conference on Computing and Combinatorics (COCOON), volume 6196 of LNCS, pages 54-59. Springer, 2010. [ bib | DOI | arXiv ]
[KN97] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. [ bib | DOI ]
[Lee10] Troy Lee. 16:198:671 Communication Complexity, 2010. A course offered at Rutgers University (Spring 2010). [ bib | .html ]
[LS09] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263-398, 2009. [ bib | DOI | .pdf ]
[LZ10] Troy Lee and Shengyu Zhang. Composition theorems in communication complexity. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Proc. 37th International Colloquium of Automata, Languages and Programming (ICALP), Part I, volume 6198 of LNCS, pages 475-489. Springer, 2010. [ bib | DOI | arXiv ]
[Pat11] Mihai Patrascu. Unifying the landscape of cell-probe lower bounds. SIAM J. Computing, 40(3):827-847, 2011. (Preliminary version in 49th FOCS, 2008). [ bib | DOI | arXiv ]
[PD04] Mihai Patrascu and Erik D. Demaine. Tight bounds for the partial-sums problem. In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 20-29, 2004. [ bib | DOI ]
[PD06] Mihai Patrascu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM J. Computing, 35(4):932-963, 2006. (Preliminary version in 36th STOC, 2004 and 15th SODA, 2004). [ bib | DOI | arXiv ]
[PRV01] Stephen Ponzio, Jaikumar Radhakrishnan, and Srinivasan Venkatesh. The communication complexity of pointer chasing. J. Computer and System Sciences, 62(2):323-355, 2001. (Preliminary Version in 31st STOC, 1999). [ bib | DOI ]
[Sen03] Pranab Sen. Lower bounds for predecessor searching in the cell probe model. In Proc. 18th IEEE Conference on Computational Complexity, pages 73-83, 2003. [ bib | DOI ]
[She08] Alexander A. Sherstov. Communication lower bounds using dual polynomials. Bulletin of the EATCS, 95:59-93, 2008. [ bib | arXiv | .pdf ]
[She10] Alexander A. Sherstov. Communication complexity under product and nonproduct distributions. Comput. Complexity, 19(1):135-150, 2010. (Preliminary version in 23rd IEEE Conference on Comput. Complexity, 2008). [ bib | DOI ]
[She11a] Alexander A. Sherstov. The communication complexity of gap Hamming distance. Technical Report TR11-063, Electronic Colloquium on Computational Complexity (ECCC), 2011. [ bib | http ]
[She11b] Alexander A. Sherstov. The multiparty communication complexity of set disjointness. Technical Report TR11-145, Electronic Colloquium on Computational Complexity (ECCC), 2011. [ bib | http ]
[SS02] Michael E. Saks and Xiaodong Sun. Space lower bounds for distance approximation in the data stream model. In Proc. 34th ACM Symp. on Theory of Computing (STOC), pages 360-369, 2002. [ bib | DOI | .pdf ]
[SV08] Pranab Sen and Srinivasan Venkatesh. Lower bounds for predecessor searching in the cell probe model. J. Computer and System Sciences, 74(3):364-385, 2008. (Preliminary version in in 28th ICALP, 2001 and 18th IEEE Conference on Computational Complexity, 2003). [ bib | DOI | arXiv ]
[Woo04] David P. Woodruff. Optimal space lower bounds for all frequency moments. In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 167-175, 2004. [ bib | DOI ]
[Yan91] Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. J. Computer and System Sciences, 43(3):441-466, 1991. (Preliminary Version in 20th STOC, 1988). [ bib | DOI | .pdf ]

This page has been accessed at least Counter times since 1 July, 2011.

Prahladh Harsha
Valid HTML 4.01! Valid CSS!