Computer Science and Engineering

Faculty

Abhijit Das

Abir Das

Animesh Mukherjee

Aritra Hazra

Arobinda Gupta

Ayan Chaudhury

Bivas Mitra

Chittaranjan Mandal

Debasis Samanta

Debdeep Mukhopadhyay

Dipanwita Roy Chowdhury

Indranil Sengupta

Jayanta Mukhopadhyay

Krothapalli Sreenivasa Rao

Mainack Mondal

Niloy Ganguly

Pabitra Mitra

Palash Dey

Pallab Dasgupta

Partha Bhowmick

Partha Pratim Chakrabarti

Partha Pratim Das

Pawan Goyal

Pralay Mitra

Rajat Subhra Chakraborty

Rajib Mall

Sandip Chakraborty

Saptarshi Ghosh

Sarani Bhattacharya

Satrajit Ghosh

Shamik Sural

Somak Aditya

Somindu Chaya Ramanna

Soumya Kanti Ghosh

Soumyajit Dey

Sourangshu Bhattacharya

Sudebkumar Prasant Pal

Sudeshna Kolay

Sudeshna Sarkar

Sudip Misra

Swagato Sanyal

Swagato Sanyal

Assistant Professor Grade-I

Computer Science and Engineering

swagato@cse.iitkgp.ac.in

Awards and Accolades

Personal Webpage Bio Sketch

Research Areas

Theoretical Computer Science
Computational Complexity
Analysis of Boolean functions

I am interested in theoretical computer science in general, and computational complexity theory in particular. I have worked on analysis of Boolean functions, decision tree complexity and communication complexity.

All Publications

No Record Found.

Completed Projects

Principal Investigator

On Complexity Measures of Boolean Functions and their Inter-relationships

Ph. D. Students

Koustav De

Area of Research:

Journal

Optimal Composition Theorem for Randomized Query Complexity Sanyal S., Gavinsky D. , Lee T. , Santha M. By Theory of Computing - (Accepted/In-Press)
Quadratically Tight Relations for Randomized Query Complexity. Jain R., Klauck H. , Kundu S. , Lee T. , Santha M. , Sanyal S. , Vihrovs J. By Theory of Computing Systems 64 101-119 (2020)
Fourier Sparsity and Dimension Sanyal S. By Theory of Computing 15 1-13 (2019)
Separation between deterministic and randomized query complexity Mukhopadhyay S., Radhakrishnan J., Sanyal S. By SIAM Journal on Computing 47 1644-1666 (2018)

Conferences

Representation-based Individual Fairness in k-clustering Kar D., Kosan M. , Mandal D. , Medya S. , Silva A. , Dey P. , Sanyal S. By International Conference on Autonomous Agents and Multiagent Systems - (Accepted/In-Press)
Lifting to Parity Decision Trees via Stifling Sanyal S., Chattopadhyay A. , Mande N. , Sherif S. By Innovations in Theoretical Computer Science (ITCS) 2023 1-20 (2023)
Lifting to Parity Decision Trees via Stifling Chattopadhyay A., Mande N.S., Sanyal S., Sherif S. By Leibniz International Proceedings in Informatics, LIPIcs 251 - (2023)
Randomized versus Deterministic Decision Tree Size Sanyal S., Chattopadhyay A. , Dahiya Y. , Mande N. , Radhakrishnan J. By Symposium on Theory of Computing (STOC) 2023 - (2023)
Sampling-Based Winner Prediction in District-Based Elections Sanyal S., Dey P. , Kar D. By International Conference on Autonomous Agents and Multiagent Systems (AAMAS) 2023 - (2023)
One-Way Communication Complexity and Non-Adaptive Decision Trees Mande N.S., Sanyal S., Sherif S. By Leibniz International Proceedings in Informatics, LIPIcs 219 - (2022)
One-Way Communication Complexity and Non-Adaptive Decision Trees Sanyal S., Mande N. S., Sheriff S. By STACS 2022 - (2022)
Tight Chang s-Lemma-Type Bounds for Boolean Functions Chakraborty S., Mande N.S., Mittal R., Molli T., Paraashar M., Sanyal S. By Leibniz International Proceedings in Informatics, LIPIcs 213 - (2021)
Tight Chang's-Lemma-Type Bounds for Boolean Functions Sanyal S., Chakraborty S. , Mande N. S., Mittal R. , Molli T. , Paraashar M. By FSTTCS 2021 - (2021)
On parity decision trees for fourier-sparse boolean functions Mande N.S., Sanyal S. By Leibniz International Proceedings in Informatics, LIPIcs 182 - (2020)
On parity decision trees for Fourier-sparse Boolean functions. Mande N., Sanyal S. By Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) - (2020)
A composition theorem for randomized query complexity via max conflict complexity Gavinsky D., Lee T. , Santha M. , Sanyal S. By 46th International Colloquium on Automata, Languages, and Programming 1-13 (2019)
A composition theorem for randomized query complexity via max-conflict complexity Gavinsky D., Lee T., Santha M., Sanyal S. By Leibniz International Proceedings in Informatics, LIPIcs 132 - (2019)
Linear Sketching over F_2 Sanyal S., Kannan S. , Mossel E. , Yaroslavtsev G. By Computational Complexity Conference (CCC) - (2018)
Quadratically Tight Relations for Randomized Query Complexity. Sanyal S., Jain R. , Klauck H. , Kundu S. , Lee T. , Santha M. , Vihrovs J. By The 13th International Computer Science Symposium in Russia (CSR) 2018 - (2018)