Skip to main content

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 PDF

Paper 2:

Separation Between Deterministic and Randomized Query Complexity; Sagnik Mukhopadhyay, Jaikumar Radhakrishnan and Swagato Sanyal; Siam. J. Comp.; 2018

Link to PDF

Paper 3:

Lifting theorems for Equality; Bruno Loff and Sagnik Mukhopadhyay, STACS 2019

Link to PDF

Keywords: Communication complexity, Query complexity, Simulation theorem, Distributed algorithm

All Job Candidates