References

[Bra17] Mark Braverman. Interactive Information Complexity. SIAM Review, 59(4):803-846, 2017. 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. DOI

[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). DOI

[BR11] Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In STOC, pages 159-166, 2011. DOI

[BW16] Mark Braverman and Omri Weinstein. A Discrepancy Lower Bound for Information Complexity. Algorithmica, 76(3):846-864, 2016. DOI

[CP10] Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness. SIGACT News, 41(3):59-85, 2010. DOI

[CKLM17] Arkadev Chattopadhyay, Michal Koucký, Bruno Loff and Sagnik Mukhopadhyay. Simulation Theorems via Pseudorandom Properties. CoRR.abs/1704.06807, 2017. ArXiv

[DHS96] Martin Dietzfelbinger, Juraj Hromkovic, and Georg Schnitger. A Comparison of Two Lower-Bound Methods for Communication Complexity. Theor. Comput. Sci., 168(1):39-51, 1996. DOI

[GPW15] Mika Göös, Toniann Pitassi and Thomas Watson. Deterministic Communication vs. Partition Number. Proceedings of 56th FOCS, 1077-1088, 2015. DOI

[GW16] Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities. Theory of Computing, 12(1):1-23, 2016. DOI

[HN12] Trinh Huynh and Jakob Nordström. On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. Proceedings of the 44th STOC, 233-248, 2012. DOI

[HW07] Johan Håstad and Avi Wigderson. The Randomized Communication Complexity of Set Disjointness. Theory of Computing, 3(1):211-219, 2007. 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. DOI

[Juk11] Stasys Jukna. Extremal Combinatorics - With Applications in Computer Science. Springer, 2011. DOI

[Juk12] Stasys Jukna. Boolean Function Complexity - Advances and Frontiers. Springer, 2012. DOI

[KN97] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. DOI

[MNWS98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra and Avi Wigderson On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci., 57(1): 37-49, 1998. DOI

[RY18] Anup Rao and Amir Yehudayoff. Communication Complexity (Early Draft). URL

Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Post-doctoral Researcher

My research interests include complexity theory and distributed graph algorithms.