**School of Mathematics at the Institute for Advanced St
udy**

**"Efficient Algorithms Via Complexity Theory"**

**Abstract:** A major goal of computational comple
xity theory has been proving unconditional lower bounds and derandomization
results for various well-studied classes of functions. These classes inclu
de DNFs, halfspaces, polynomial threshold functions etc. which have been st
udied in many disciplines other than complexity theory. A theme which has e
merged from this work is that the complexity-theoretic study of these class
es has led to insights into their structure, which in turn enable more effi
cient algorithms dealing with these functions in a variety of settings such
as social choice theory, learning theory, and stochastic optimization. Ano
ther recurring theme is the unexpected appearance --- and surprising effica
cy --- of ideas and themes from well-developed branches of mathematics such
as Fourier analysis, probability theory and stochastic calculus in the stu
dy of these functions.

**In this talk, I will discuss three vigne
ttes from my own research where work in complexity theory will end up yield
ing interesting results for learning theory, social choice theory and stoch
astic optimization. We will see how the complexity theoretic approach as we
ll as tools from probability, Fourier analysis, Gaussian geometry and stoch
astic calculus end up playing indispensable roles in solutions to these pro
blems.**

**Bio:**** Dr. Anindya De** is currently a postdoc in the S
chool of Mathematics at the Institute for Advanced Study. Prior to this, he
was a Simons research fellow at the Simons Institute, UC Berkeley. He comp
leted his Ph.D. from UC Berkeley (2013) advised by Luca Trevisan. Prior to
Berkeley, he finished his Bachelor of Technology (2008) from the Indian Ins
titute of Technology, Kanpur. His research interests include computational
complexity theory, learning theory, discrete analysis and applied probabili
ty and applications of these to all aspects of theoretical computer science
.

**Hosted by: EECS**