Thesis Information
Title: Understanding the Limits of Computational Models and Learning Algorithms
Adviser: Mark Braverman
Institution: Princeton University
Graduation Date: June 2020
Contact Information
Email Candidate
Candidate Website
SIGACT Membership No.: 6721778
Candidate Bio:
Sumegha Garg is a graduate student in Computer Science at Princeton University, where she is advised by Professor Mark Braverman. Before coming to Princeton, she received her Bachelor’s degree in Computer Science and Engineering from Indian Institute of Technology, Delhi. She is broadly interested in theoretical computer science, with a focus on complexity theory and algorithmic fairness. The primary aim of her research has been studying the computation limits of and the role of randomness in space-bounded computational models. Another aim of her research has been understanding the sources of unfairness in machine learning algorithms.
Paper 1:
Extractor-based time-space lower bounds for learning, Sumegha Garg and Ran Raz and Avishay Tal, STOC, 2018
Link to PDFPaper 2:
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs, Mark Braverman and Gil Cohen and Sumegha Garg, STOC, 2018
Link to PDFPaper 3:
Tracking and Improving Information in the Service of Fairness, Sumegha Garg and Michael Kim and Omer Reingold, EC, 2019
Link to PDFKeywords: Computational complexity, algorithmic fairness, space-bounded computation, randomness in computing