BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//jEvents 2.0 for Joomla//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/Chicago
BEGIN:STANDARD
DTSTART:20130218T100000
RDATE:20130310T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:America/Chicago CST
END:STANDARD
BEGIN:STANDARD
DTSTART:20131103T010000
RDATE:20140309T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:America/Chicago CST
END:STANDARD
BEGIN:STANDARD
DTSTART:20141102T010000
RDATE:20150308T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:America/Chicago CST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20130310T030000
RDATE:20131103T010000
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:America/Chicago CDT
END:DAYLIGHT
BEGIN:DAYLIGHT
DTSTART:20140309T030000
RDATE:20141102T010000
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:America/Chicago CDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:edf497061d8f4b61643c2f3617baf972
CATEGORIES:General EECS Event
SUMMARY:Dr. Anindya De, School of Mathematics at the Institute for Advanced Study, "Efficient Algorithms Via Complexity Theory"
LOCATION:Tech Room L324
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:\n\nDr. Anindya De\n\n\nSchool of Mathematics at the Institute for Advanced
Study\n\n\n"Efficient Algorithms Via Complexity Theory"\n\n\nAbstract: A m
ajor 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 compl
exity theory. A theme which has emerged from this work is that the complexi
ty-theoretic study of these classes has led to insights into their structur
e, which in turn enable more efficient algorithms dealing with these functi
ons in a variety of settings such as social choice theory, learning theory,
and stochastic optimization. Another recurring theme is the unexpected app
earance --- and surprising efficacy --- of ideas and themes from well-devel
oped branches of mathematics such as Fourier analysis, probability theory a
nd stochastic calculus in the study of these functions. \n\n\nIn this
talk, I will discuss three vignettes from my own research where work in com
plexity theory will end up yielding interesting results for learning theory
, social choice theory and stochastic optimization. We will see how the com
plexity theoretic approach as well as tools from probability, Fourier analy
sis, Gaussian geometry and stochastic calculus end up playing indispensable
roles in solutions to these problems.\n\n\nBio: Dr. Anindya De is currentl
y a postdoc in the School of Mathematics at the Institute for Advanced Stud
y. 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 in
clude computational complexity theory, learning theory, discrete analysis a
nd applied probability and applications of these to all aspects of theoreti
cal computer science.\n\n\nHosted by: EECS\n
CONTACT:Amanda Zarate at amandaz@eecs.northwestern.edu or 847-491-3451
DTSTAMP:20140902T135802Z
DTSTART;TZID=America/Chicago:20140219T100000
SEQUENCE:0
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR