Brief Bio
I am a postdoctoral researcher in the CSE department at UC San Diego, hosted by Shachar Lovett. Previously, I was a postdoctoral researcher in the STCS group at TIFR Mumbai, hosted by Arkadev Chattopadhyay and supported by the Professor R. Narasimhan Postdoctoral Fellowship. I completed my Ph.D. in theoretical computer science at the Institute of Mathematical Sciences, Chennai, advised by Meena Mahajan.
Before that, I obtained a Master's degree in Computer Science from IIT Kanpur, advised by Prof. Surender Baswana, and a Bachelor's degree in Electronics and Communication Engineering from IIT BHU.
I have broad interests in theoretical computer science. My current research focuses on query complexity, communication complexity, proof complexity, and sketching and sampling algorithms for big data problems.
News
- Visited Sasha Razborov at the University of Chicago in May 2026, and gave a talk at the Combinatorics and TCS Seminar.
- A paper accepted at CCC 2026 on Quantum–Classical Equivalence for AND-Functions. We resolve the question of quantum advantage for total Boolean functions for the class of AND-functions, showing that classical and quantum models are equivalent up to polynomial loss.
- Gave a talk on On Quantum–Classical Equivalence for AND Functions at SoCal Theory Day, February 2026.
- A paper accepted at STOC 2026 on Restriction Trees for Sparsity and Applications. We establish new connections between exact and approximate sparsity measures of total Boolean functions in the De Morgan basis, along with several applications.
- Gave a talk on On Quantum–Classical Equivalence in the Communication Model at the UCSD Theory Seminar, February 2026.
- Gave a talk on Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis at the STCS Annual Symposium, August 2025.
- Participated in the HDXs and Codes workshop at ICTS, May 2025.
- Participated in the Dagstuhl Seminar on Computational Complexity of Discrete Problems, March 2025.
- Participated in the Synergies of Combinatorics and Theoretical Computer Science summer school at the Bernoulli Center, EPFL, September 2024.
- Gave a talk on New Lower Bounds for Polynomial Calculus over Non-Boolean Bases at the STCS Annual Symposium, August 2024.
- Visited Meena at IMSc Chennai, June 2024.
- A paper accepted at SAT 2024 on lower bounds for Polynomial Calculus over non-Boolean bases. We present a lifting theorem for Polynomial Calculus over the {+1, -1} encoding and a new lower bound for Polynomial Calculus over finite fields with extension variables.
- Gave a talk on Randomness Gives Little Advantage for Decision Tree Size at the MIAO Seminar.
- Visited Nutan and Srikanth at the University of Copenhagen, Denmark, October 2023.
- Visited the University of Bergen, Norway, September–November 2023.
- Presented our paper on Query Complexity of Search Problems at MFCS 2023, August 2023.
- A paper accepted at MFCS 2023 on Query Complexity of Search Problems. We study pseudo-deterministic query and size complexity in various decision tree models.
- A paper accepted at STOC 2023 on Randomized versus Deterministic Decision Tree Size. We derandomize the size measure in the query model, extending the classical result of Nisan, which derandomized the query measure.
- Visited Arkadev Chattopadhyay at TIFR Mumbai, January–April 2023.
- Gave a talk on Time and Space Complexity of Query Algorithms at the IMSc60 event celebrating the 60th foundation year of the Institute of Mathematical Sciences, January 2023.
- Visited Arkadev Chattopadhyay at TIFR Mumbai, September 2022.
- Gave a talk on Decision Tree Rank at the TCS Seminar, IMSc, November 2021.
- A paper accepted at FSTTCS 2021 on decision tree rank.
- A paper accepted at ICML 2021 on fixed-parameter approximation algorithms for PCA in the presence of outliers.
- Gave a talk on Sketching for Numerical Linear Algebra at the summer school on Algorithmic Tractability via Sparsifiers, Leh, India, 2019.
Publications
Quantum–Classical Equivalence for AND-Functions.
With Sreejata K. Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay and Shachar Lovett.
Accepted to the 2026 Computational Complexity Conference (CCC 2026)
ECCC Report
Restriction Trees for Sparsity and Applications.
With Arkadev Chattopadhyay and Shachar Lovett.
Accepted to the 58th Annual ACM Symposium on Theory of Computing (STOC 2026)
ECCC Report
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis.
With Arkadev Chattopadhyay and Shachar Lovett
.
Subsumed by the paper above, with all results strengthened or extended, except one on monotone functions. (Manuscript 2025)
ECCC Report
New lower bounds for Polynomial Calculus over non-Boolean bases
With Meena Mahajan and Sasank Mouli.
Proceedings of the 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024).
ECCC Report
Linear threshold functions in decision lists, decision trees, and depth-2 circuits
With Vignesh K, Meena Mahajan, Karteek Sreenivasaiah.
Information Processing Letters, Vol. 183 (106418) (IPL 2024).
ECCC Report
Query Complexity of Search Problems
With Arkadev Chattopadhyay and Meena Mahajan.
Proceedings of 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Full version in Computational Complexity 2025.
ECCC Report
Randomized Versus Deterministic Decision Tree Size
With Arkadev Chattopadhyay, Nikhil Mande, Jaikumar Radhakrishnan, and Swagato Sanyal.
Proceedings of 55th ACM Symposium on Theory of Computing (STOC 2023)
ECCC Report
On (Simple) decision tree rank
With Meena Mahajan
Proceedings of 41st FSTTCS Conference (FSTTCS 2021)
Full version in Theoretical Computer Science 2023.
ECCC Report
Fixed-Parameter and Approximation Algorithms for PCA with Outliers
With Fedor Fomin, Fahad Panolan and Kirill Simonov
Proceedings of 38th International Conference on Machine Learning (ICML 2021) paper
An Empirical Evaluation of Sketching for Numerical Linear Algebra
With Dimitris Konomis and David Woodruff
SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2018) paper
Discovering Response-Eliciting Factors in
Social Question Answering
With Danish and Partha Talukdar
AAAI Conference on Web and Social Media (ICWSM-16) paper
Contact
Email: yogeshd2612 (at) gmail (dot) com
ydahiya (at) ucsd (dot) edu
Office: CSE 4128