Senior Research Fellow
Theoretical Computer Science Group
The Institute of Mathematical Sciences, Chennai
Brief Bio
I am a PhD student in the TCS group at The Institute of Mathematical Sciences. I am fortunate to be advised by Meena Mahajan. I am broadly interested in Theoretical Computer Science, and my current research interests are Query Complexity, Communication Complexity, and Sketching and Sampling Algorithms for problems in big data.
Previously, I obtained a Master's degree in Computer Science from IIT Kanpur advised by Prof. Surender Baswana and a Bachelor's degree in ECE from IIT BHU.
News & Activities
- Presented our paper on Query Complexity of Search Problems at MFCS 23, Aug 2023.
- A paper accepted in MFCS 23 on Query Complexity of Search Problems. We study pseudo-deterministic query and size complexity in various decision tree models.
- A paper accepted in STOC 23 on Randomized versus Deterministic Decision Tree Size. We derandomize the size measure in the query model adding to the classical result of Nisan's, which derandomized the query measure. As a consequence, we obtain that randomness gives little advantage in the AND query and the AND-OR query models.
- Visiting Prof. Arkadev Chattopadhyay, Jan-April 2023, TIFR, Mumbia.
- Talk on Time and Space complexity of Query Algorithms at IMSc60 event celebrating the 60th foundation year of the Institute of Mathematical Science, Jan 2023.
- Visited Prof. Arkadev Chattopadhyay, Sep 2022, TIFR, Mumbia.
- Talk on Decision tree rank at TCS seminar IMSc, Nov 2021.
- A paper accepted in FSTTCS 21 on the decision tree rank. We study the rank of decision trees for Boolean functions and relate it to other measures like depth, size, sparsity, and certificate complexity. We also proved a decision tree size composition theorem.
- A paper accepted in ICML 21 on Fixed-Parameter Approximation Algorithms for PCA in the presence of outliers.
- Talk on Sketching for Numerical Linear Algebra at the summer school on
Algorithmic Tractability via Sparsifiers, Leh, India, 2019. - Attended Workshop on Kernelization (Worker) 2019 at University of Bergen, Norway
- Visited Prof. Saket Saurabh, from 05/19 to 07/19, University of Bergen, Norway.
Preprints
New lower bounds for Polynomial Calculus over non-Boolean bases
With Meena Mahajan and Sasank Mouli.
ECCC Report
Publications
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
Contact
Email: yogeshdahiya (at) imsc (dot) res (dot) in
Office: NL-02 Library Building