I am a fifth-year graduate student in the theory of computation group at Harvard University, advised by Boaz Barak. I will join IDEAL as postdoc starting in Fall 2023.

My research focuses on the computational complexity of statistical inference, lying at the intersection of theoretical computer science, statistics, probability and data science. Recently, I have been investigating the phenomenon of information-computation gaps in the context of discrepancy theory, random CSPs, estimating parameters of high-dimensional, heavy-tailed distributions, and differential privacy.

My graduate studies are supported by an NSF Graduate Fellowship.

Papers

• Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, Fred Zhang.
  Privately Estimating a Gaussian: Efficient, Robust and Optimal
  To appear in the Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), 2023. [arXiv:2212.08018]

• Prayaag Venkat.
  Efficient algorithms for certifying lower bounds on the discrepancy of random matrices
  The 14th Innovations in Theoretical Computer Science conference (ITCS 2023). [arXiv:2211.07503] and official version.

• Aaron Potechin, Paxton Turner, Prayaag Venkat, Alexander S. Wein.
  Near-optimal fitting of ellipsoids to random points
  In submission. [arXiv:2208.09493]

• Preetum Nakkiran, Prayaag Venkat, Sham Kakade, Tengyu Ma.
  Optimal Regularization Can Mitigate Double Descent
  The Ninth International Conference on Learning Representations (ICLR 2021). [arXiv:2003.01897]

• Zhixian Lei, Kyle Luh, Prayaag Venkat, Fred Zhang.
  A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates
  The 33rd Annual Conference on Learning Theory (COLT 2020) [arXiv:1908.04468]

• Samir Khuller, Jingling Li, Pascal Sturmfels, Kevin Sun, and Prayaag Venkat.
  Select and Permute: An Improved Online Framework for Scheduling to Minimize Weighted Completion Time
  The 13th Latin American Theoretical Informatics Symposium (LATIN 2018) [arXiv:1704.06677]

• Prayaag Venkat and David Mount.
  A Succinct, Dynamic Data Structure for Proximity Queries on Point Sets
  The 26th Canadian Conference on Computational Geometry (CCCG 2014) [link]

Contact

CV | GitHub | Email

My office is Room 3.334 of the Science and Engineering Complex.

Last updated: 12/21/2022