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
TIFR Course Calendar (subscribe (ical)) / IMSc Course Calendar (subcribe (ical))
(Tentative) Course Schedule with list of potential topics
Students taking the course for credit will be expected to:
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 AC^{0} 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 times since 1 July, 2011.
Prahladh Harsha |