Workshops

Fall 2015

Connections Between Algorithm Design and Complexity Theory

Sep 28, 2015 to Oct 1, 2015

Return to event »

Click on the titles of individual talks for abstract, slides and archived video.

All events take place in the Calvin Lab Auditorium.

Monday, September 28th, 2015
9:00 am–9:20 am		Coffee and Check-In
9:20 am–9:30 am		Opening Remarks
9:30 am–10:15 am		Human Computation Manuel Blum, Carnegie Mellon University
10:15 am–10:45 am		Break
10:45 am–11:30 am		Explicit Two-Source Extractors and Resilient Functions David Zuckerman, UT Austin
11:30 am–11:45 am		Break
11:45 am–12:30 pm		On the Power of Gradually Increasing Independence Parikshit Gopalan, Microsoft Research
12:30 pm–2:45 pm		Lunch
2:45 pm–3:00 pm		Anti-Concentration for Polynomials of Independent Random Variables Raghu Meka, UCLA
3:00 pm–3:15 pm		Lower Bounds by Birkhoff Interpolation Pascal Koiran, Ecole Normale Supérieure de Lyon
3:15 pm–3:30 pm		Sublinear Space Complexity Osamu Watanabe, Tokyo Institute of Technology
3:30 pm–4:30 pm		Reception

Tuesday, September 29th, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:15 am		Chasing Lower Bounds Avi Wigderson, Institute for Advanced Study, Princeton
10:15 am–10:45 am		Break
10:45 am–11:30 am		Local Reductions Emanuele Viola, Northeastern University
11:30 am–11:45 am		Break
11:45 am–12:00 pm		Getting Harder All the Time? Omer Reingold, Samsung Research America
12:00 pm–12:15 pm		Derandomization via Robust Algebraic Circuit Lower Bounds Michael Forbes, Princeton University
12:15 pm–12:30 pm		Graph Automorphism and Circuit Size Eric Allender, Rutgers University
12:30 pm–2:45 pm		Lunch
2:45 pm–3:30 pm		Open Problems Discussion Session
3:30 pm–3:45 pm		Break
3:45 pm–4:30 pm		Open Problems Discussion Session

Wednesday, September 30th, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:15 am		On the Existence of Optimal Algorithms Boaz Barak, Microsoft Research and Harvard University
10:15 am–10:45 am		Break
10:45 am–11:30 am		A Compression Algorithm for AC^0[p] Circuits Using Certifying Polynomials Srikanth Srinivasan, Indian Institute of Technology Bombay
11:30 am–11:45 am		Break
11:45 am–12:30 pm		Approaches to Bounding the Exponent of Matrix Multiplication Chris Umans, California Institute of Technology
12:30 pm–2:45 pm		Lunch
2:45 pm–3:30 pm		Panel (Interactive Discussion)
3:30 pm–3:45 pm		Break
3:45 pm–4:30 pm		Panel (Interactive Discussion)

Thursday, October 1st, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:15 am		QBF Satisfiability Algorithms and Connections with Circuit Lower Bounds Rahul Santhanam, University of Edinburgh
10:15 am–10:45 am		Break
10:45 am–11:30 am		Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates Suguru Tamaki, Kyoto University
11:30 am–11:45 am		Break
11:45 am–12:30 pm		Probabilistic Polynomials and Hamming Nearest Neighbors Joshua Alman, Stanford University
12:30 pm–2:45 pm		Lunch
2:45 pm–3:00 pm		Generalizations of the Gate Elimination Method Alexander Kulikov, St. Petersburg Department of Steklov Institute of Mathematics
3:00 pm–3:15 pm		Addition is Exponentially Harder than Counting for Shallow Monotone Circuits Igor Oliveira, Columbia University
3:15 pm–3:30 pm		Satisfiability Algorithms Based on Concentrated Shrinkage Ruiwen Chen, University of Edinburgh