Sreejata Kishor Bhattacharya

Welcome to my webpage!

I am a graduate student at School of Technology and Computer Science, Tata Institute of Fundamental Research working under the supervision of Arkadev Chattopadhyay. I am broadly interested in theoretical computer science. In particular, I like thinking about various aspects of complexity theory (proof complexity, communication complexity, etc) and quantum computing. I am supported by a Google PhD Fellowship.

Email: <first name> [dot] <last name> [at] tifr [dot] res [dot] in

CV: [link]

Education

Bachelors of Science at Chennai Mathematical Institute (Mathematics and Computer Science) Aug. 2016 - May 2019

Masters of Science at Chennai Mathematical Institute (Computer Science) Aug. 2019 - May 2021

PhD at School of Technology and Computer Science, Tata Institute of Fundamental Research Dec. 2021 - Present

Publications and Preprints

[dblp]

Quantum–Classical Equivalence for AND-Functions (CCC 2026)

Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

[eccc]

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth (STOC 2026)

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay

Note: This paper was merged with Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities by Farzan Byramji and Russell Impagliazzo in STOC proceedings. Title of the merged paper is Lower Bounds for Near-Quadratic-Depth Resolution over Parities.

[arXiv] [eccc]

Aaronson-Ambainis Conjecture Is True For Random Restrictions (ITCS 2025, best student paper)

Sreejata Kishor Bhattacharya

Title of conference version: Random Restrictions of Low Degree Bounded Polynomials are Juntas

[arXiv] [eccc]

Exponential Separation Between Powers of Regular and General Resolution Over Parities (CCC 2024)

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvořák

[arXiv] [eccc]