Computational complexity, Probability, Design and analysis of algorithm
1. [Bra17]Mark Braverman. Interactive Information Complexity. SIAM Review, 59(4):803-846, 2017.
2. [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.
3. [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).
4. [BR11]Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In STOC, pages 159-166, 2011.
5. [BW16]Mark Braverman and Omri Weinstein. A Discrepancy Lower Bound for Information Complexity. Algorithmica, 76(3):846-864, 2016.
6. [CP10]Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness. SIGACT News, 41(3):59-85, 2010.
7. [CKLM17]Arkadev Chattopadhyay, Michal Koucký, Bruno Loff and Sagnik Mukhopadhyay. Simulation Theorems via Pseudorandom Properties. CoRR.abs/1704.06807, 2017. [ ArXiv ]
8. [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.
9. [GPW15] Mika Göös, Toniann Pitassi and Thomas Watson. Deterministic Communication vs. Partition Number. Proceedings of 56th FOCS, 1077-1088, 2015.
10. [GW16] Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities. Theory of Computing, 12(1):1-23, 2016.
11. [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.
12. [HW07] Johan Håstad and Avi Wigderson. The Randomized Communication Complexity of Set Disjointness. Theory of Computing, 3(1):211-219, 2007.
13. [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 ]
14. [Juk11] Stasys Jukna. Extremal Combinatorics - With Applications in Computer Science. Springer, 2011.
15. [Juk12] Stasys Jukna. Boolean Function Complexity - Advances and Frontiers. Springer, 2012.
16. [KN97] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.
17. [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.
18. [RY18] Anup Rao and Amir Yehudayoff. Communication Complexity (Early Draft).