Yogesh Dahiya


Postdoctoral Researcher
School of Technology and Computer Science
Tata Institute of Fundamental Research, Mumbai

Brief Bio

I am currently a postdoctoral researcher in the STCS group at the Tata Institute of Fundamental Research, Mumbai, hosted by Arkadev Chattopadhyay. I completed my Ph.D. in theoretical computer science at the Institute of Mathematical Sciences, Chennai, under the guidance of Prof. Meena Mahajan.
Previously, 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 a broad interest in theoretical computer science, with current research focuses on query complexity, communication complexity, proof complexity, and sketching and sampling algorithms for big data problems.

News & Activities


New lower bounds for Polynomial Calculus over non-Boolean bases
With Meena Mahajan and Sasank Mouli.
To appear in Proceedings of the 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 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)
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

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 to appear in Theoretical Computer Science.
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


Email: yogeshdahiya (at) imsc (dot) res (dot) in
Office: NL-02 Library Building