Abstract: Data-driven algorithms have seen great success in a wide range of domains, from product recommendations to cyber-security and healthcare. The ever-expanding use of these algorithms brings in new efficiency and ethical concerns. Firstly, when analyzing massive amounts of data, memory is increasingly becoming a bottleneck computational resource. Secondly, as data-driven decision-making systems are being used to make important decisions about humans, they raise a host of fairness concerns and fears for potential discrimination.
In this talk, I'll give an overview of my efforts to understand these concerns using modern mathematical tools from computational complexity theory and information theory. I'll then dig deeper into two results that illustrate the efficacy of information-theoretic techniques in quantifying memory usage as well as characterizing challenges in algorithmic fairness. First, I'll introduce the coin problem – given independent coin tosses, detect which way a coin is biased – and show that this problem is at the heart of hardness results for many data streaming problems. I’ll go on to describe new techniques we developed to determine the memory needed for solving the coin problem. Second, I'll show how informativeness of predictions on a subpopulation plays a key role in connecting various conflicting approaches to algorithmic fairness.
Bio: Sumegha Garg is a Michael O. Rabin postdoctoral fellow in theoretical computer science at Harvard University. She received her Ph.D. in Computer Science from Princeton University in 2020, advised by Mark Braverman. She uses her background in computational complexity theory to answer fundamental questions in applied areas such as learning, data streaming, and cryptography. In particular, she is interested in determining the limits of space-efficient computing and establishing the foundations of responsible computing. Her awards include Siebel Scholarship (2019-20), Microsoft Dissertation Grant (2019) and Rising Star in EECS (2019).
