profile picture

Diptaksho Palit

Ph.D. Student @ Boston University

dpalit [at] bu [dot] edu · CV · Google Scholar

About

I am a Ph.D. student at the Department of Computer Science, Boston University, in the Theoretical Computer Science (TCS) research group, where I am advised by Prof. Sofya Raskhodnikova. I completed my undergraduate degree in mathematics and computer science at Chennai Mathematical Institute.

My research focuses on computational complexity and property testing. In property testing, I mostly work on query and time complexity lower bounds, though our insights sometimes lead to new upper bounds instead. I am interested in investigating gaps between information-theoretic (query complexity) upper bounds and computational (time complexity) lower bounds for both learning and testing problems. In complexity theory, I'm working on formalising relativisation to better understand it as a proof barrier and proof technique.

Properties tested 🧪
  • halfspaces
  • unate functions
  • k-submodular functions
  • parenthesis languages
  • connected graphs
  • k-edge-connected graphs

Publications

2026

Teaching

Teaching Fellow

CS332: Theory of Computation

Boston University | Spring 2024 | Mark Bun
Teaching Assistant

HU1101: English

Chennai Mathematical Institute | Fall 2022 | Usha Mahadevan

CU1101: Introduction to Programming (Haskell)

Chennai Mathematical Institute | Fall 2021, Fall 2022 | S P Suresh

CU1201: Advanced Programming

Chennai Mathematical Institute | Spring 2022 | Samir Datta

MU1203: Discrete Mathematics

Chennai Mathematical Institute | Spring 2022 | K V Subrahmanyam

Service

External reviewer for the following conferences.