Home Page of Venkatesan Guruswami (original) (raw)

Research
Research Publications Interests: Several topics in Theoretical Computer Science, including the theory of error-correcting codes, approximation algorithms & non-approximability, pseudorandomness, probabilistically checkable proofs, algebraic algorithms. Brief description of my current research interests. Below is some further information about my two main research focuses: Error-correcting codes Survey talk on ``List and local decoding": Slides, Video. Survey talk on recent body of work on optimal rate list decoding by evading subspaces. Video of talk. Video of short talk Non-Malleable Coding. A older survey appearing in CACM Mar'09 (in html format) An NSF highlight on our work on list decoding with optimal redundancy. An NSF news article about our work on list decoding Reed-Solomon codes. Article in Science Magazine on list (and local) decoding. Approximate solutions to NP-hard problems Slides from a tutorial on Approximability of CSPs. Slides from 2011 survey talk "PCPs in the last decade" My research over the years has been generously supported by: National Science Foundation, via grants such as CAREER award, CDI.David and Lucile Packard Fellowship (2005)Sloan Research Fellowship (2005)
Students
Current PhD advisees: Omar Alrabiah Louis Golowich Meghal Gupta Shilun Li Xuandi Ren Mihir Singhal (co-advised with Jelani Nelson) Postdocs Joshua Brakensiek, Aug 2024-.Hsin-Po Wang, Oct 2022-May 2024.Sai Sandeep, Sep 2022-May 2023.Ray Li, Aug 2022-Aug 2023.Joao Ribeiro, August 2021-Jan 2023.Jonathan Mosheiff, Oct 2019-Mar 2022.Ankit Singh Rawat, Sep 2015-Aug 2016.Mary Wootters, Sept 2014-July 2016.Mahdi Cheraghchi, Sep. 2011-June 2013.Krzysztof Onak, Simons postdoctoral fellow, 2010-12. Rishi Saket, Sep'09-Aug'10. Parikshit Gopalan, Mar'07-Jun'08. Undergraduate/M.S: Omar Alrabiah Joshua Brakensiek Winner of the 2018 CRA Outstanding Undergraduate Researcher award. Ray Li. Honor's thesis (2017): New developments in coding against insertions and deletions Zhen Zhou Patrick Lin Patrick Xia (M.S., 2013) Graduated Ph.D. Atri Rudra, Ph.D., 2007. Atri's award winning dissertation. Prasad Raghavendra, Ph.D., 2009. Prasad's defense of his award winning thesis. Ali Kemal Sinop, Ph.D., 2012. Ali's dissertation on SDP hierarchies in approximate optimization. Yuan Zhou, Ph.D., 2014. (co-advised with R. O'Donnell) Dissertation: New Directions in Approximation Algorithms and Hardness of Approximation Carol Wang, Ph.D., 2015. Dissertation: Beyond unique decoding: topics in error-correcting codes Ameya Velingker, Ph.D., 2016. Dissertation: New Directions in Coding Theory: Capacity and Limitations Euiwoong Lee, Ph.D., 2017. Dissertation: Optimal approximabilities beyond CSPs; Inaugural winner of Edmund M. Clarke Doctoral Dissertation Award Vijay Bhattiprolu, Ph.D., 2019 Dissertation: On the Approximability of Injective Tensor Norm Nicolas Resch, Ph.D., 2020 Dissertation: List-Decodable Codes: (Randomized) Constructions and Applications Andrii Riazanov, Ph.D., 2022 Dissertation: Polar Codes with Near-Optimal Convergence to Channel Capacity Sai Sandeep, Ph.D., 2022 Dissertation: New Directions in Inapproximability: Promise Constraint Satisfaction Problems and Beyond Peter Manohar, Ph.D., 2024 Dissertation: New Spectral Techniques in Algorithms, Combinatorics, and Coding Theory: The Kikuchi Matrix Method

You are visitor number several to this page.