Wednesday, February 19, 2014, 10:00am
School of Mathematics at the Institute for Advanced Study
"Efficient Algorithms Via Complexity Theory"
Abstract: A major goal of computational complexity theory has been proving unconditional lower bounds and derandomization results for various well-studied classes of functions. These classes include DNFs, halfspaces, polynomial threshold functions etc. which have been studied in many disciplines other than complexity theory. A theme which has emerged from this work is that the complexity-theoretic study of these classes has led to insights into their structure, which in turn enable more efficient algorithms dealing with these functions in a variety of settings such as social choice theory, learning theory, and stochastic optimization. Another recurring theme is the unexpected appearance --- and surprising efficacy --- of ideas and themes from well-developed branches of mathematics such as Fourier analysis, probability theory and stochastic calculus in the study of these functions.
In this talk, I will discuss three vignettes from my own research where work in complexity theory will end up yielding interesting results for learning theory, social choice theory and stochastic optimization. We will see how the complexity theoretic approach as well as tools from probability, Fourier analysis, Gaussian geometry and stochastic calculus end up playing indispensable roles in solutions to these problems.
Bio: Dr. Anindya De is currently a postdoc in the School of Mathematics at the Institute for Advanced Study. Prior to this, he was a Simons research fellow at the Simons Institute, UC Berkeley. He completed his Ph.D. from UC Berkeley (2013) advised by Luca Trevisan. Prior to Berkeley, he finished his Bachelor of Technology (2008) from the Indian Institute of Technology, Kanpur. His research interests include computational complexity theory, learning theory, discrete analysis and applied probability and applications of these to all aspects of theoretical computer science.
Hosted by: EECS