Thesis Information
Title: Communication complexity amplification by function composition.
Adviser: Arkadev Chattopadhyay
Institution: Tata Institute of Fundamental Research, India
Graduation Date: August 2017
Contact Information
Email Candidate
Candidate Website
Candidate Bio:
Ph.D. from TIFR, India in 2017. Currently a post-doc with Danupon Nanongkai at KTH Sweden working on distributed graph algorithms. Interested in communication complexity and various applications of it.
Research Summary:
My research area is primarily complexity theory, more specifically communication complexity and query complexity. In recent times, I am also interested in distributed algorithms and their connection to communication complexity. Among them, I am interested in distributed graph algorithms.
Teaching Aims:
Instructor for Communication complexity course at KTH, and co-instructor for Complexity theory @ KTH and TIFR. Pedagogical approach that I adhere to is active learning methodology. I prefer student interaction than traditional methods of learnings.
Paper 1:
Simulation beats richness: new data-structure lower bounds; Arkadev Chattopadhyay, Michal Koucky, Bruno Loff and Sagnik Mukhopadhyay; STOC 2018
Link to PDFPaper 2:
Separation Between Deterministic and Randomized Query Complexity; Sagnik Mukhopadhyay, Jaikumar Radhakrishnan and Swagato Sanyal; Siam. J. Comp.; 2018
Link to PDFKeywords: Communication complexity, Query complexity, Simulation theorem, Distributed algorithm