|
FOCS 2011 Schedule |
|||
|
|
|
|
|
|
Saturday,
October 22 |
|
||
|
11:00 |
-12:30 |
Tutorial 1: Cynthia Dwork. The Promise of
Differential Privacy. |
|
|
12:30 |
- 1:45 |
Lunch (your own) |
|
|
1:45 |
- 3:15 |
Tutorial 2: Kirk Pruhs. Green Computing Algorithmics. |
|
|
3:30 |
- 5:00 |
Tutorial 3: Vinod Vaikuntanathan. Computing Blindfolded:
New Developments in Fully Homomorphic
Encryption. |
|
|
7:00 |
- 9:00 |
Welcoming Reception. |
|
|
|
|
|
|
|
Sunday,
October 23 |
|
||
|
7:30 |
- 8:25 |
Continental Breakfast.
Foyer. |
|
|
|
|
Session 1A. |
Session 1B. |
|
8:25 |
- 8:45 |
Min-Max Graph Partitioning and Small-Set Expansion |
How
Bad is Forming Your Own Opinion? |
|
|
|
Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev,
Viswanath Nagarajan,
Joseph (Seffi) Naor, Roy
Schwartz |
David
Bindel,
Jon Kleinberg, Sigal Oren |
|
8:50 |
- 9:10 |
The
Graph Minor Algorithm with Parity Conditions |
The
Complexity of the Homotopy Method, Equilibrium
Selection, and Lemke-Howson Solutions |
|
|
|
Ken-ichi Kawarabayashi, Bruce Reed, Paul Wollan |
Paul
W. Goldberg, Christos H.
Papadimitriou, Rahul Savani |
|
9:15 |
- 9:35 |
Separator
Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications |
Welfare
and Profit Maximization with Production Costs |
|
|
|
Christian
Wulff-Nilsen |
Avrim Blum, Anupam Gupta, Yishay Mansour,
Ankit Sharma |
|
9:40 |
- 10.00 |
A constant
factor approximation algorithm for unsplittable
flow on paths |
Mechanism
Design with Set-Theoretic Beliefs |
|
|
|
Paul
Bonsm,
Jens Schulz, Andreas Wiese |
Jing
Chen, Silvio Micali |
|
10.00 |
-10:45 |
Coffee Break. Foyer. |
|
|
|
|
Session 2A. |
Session 2B. |
|
10:45 |
- 11:05 |
Efficient
Fully Homomorphic Encryption from (Standard) LWE |
Sharp
mixing time bounds for sampling random surfaces |
|
|
|
Zvika Brakerski, Vinod Vaikuntanathan |
Pietro Caputo, Fabio Martinelli, Fabio Lucio Toninelli |
|
11:10 |
- 11:30 |
Fully
Homomorphic Encryption without Squashing Using
Depth-3 Arithmetic Circuits |
Improved
Mixing Condition on the Grid for Counting and Sampling Independent Sets |
|
|
|
Craig
Gentry, Shai
Halevi |
Ricardo
Restrepo,
Jinwoo Shin, Prasad Tetali, Eric Vigoda, Linji Yang |
|
11:35 |
- 11:55 |
Coin
Flipping with Constant Bias Implies One-Way Functions |
Solving
connectivity problems parameterized by treewidth in
single exponential time |
|
|
|
Iftach Haitner, Eran Omri |
Marek Cygan, Jesper
Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Joham M. M. van Rooij, Jakub Onufry Wojtaszczyk |
|
12:00 |
- 12:20 |
How
to Garble Arithmetic Circuits |
The
minimum k-way cut of bounded size is fixed-parameter tractable |
|
|
|
Benny
Applebaum, Yuval Ishai, Eyal Kushilevitz |
Mikkel Thorup, Ken-ichi
Kawarabayashi |
|
12:30 |
- 1:45 |
Lunch. |
|
|
|
|
Session 3A. |
Session 3B. |
|
2:00 |
- 2:20 |
Multiple-Source
Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time |
Extractors
for circuit sources |
|
|
|
Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen |
Emanuele Viola |
|
2:25 |
- 2:45 |
Minimum
Weight Cycles and Triangles: Equivalences and Algorithms |
Randomness
buys depth for approximate counting |
|
|
|
Liam
Roditty, Virginia Vassilevska
Williams |
Emanuele Viola |
|
2:50 |
- 3:10 |
Graph
Connectivities, Network Coding, and Expander Graphs |
Pseudorandomness for read-once formulas |
|
|
|
Ho
Yee Cheung, Lap Chi Lau, Kai Man
Leung |
Andrej
Bogdanov,
Periklis Papakonstantinou, Andrew Wan |
|
3:15 |
- 3:35 |
Maximum
Edge-Disjoint Paths in Planar Graphs with Congestion 2 |
Dispersers
for affine sources with sub-polynomial entropy |
|
|
|
Loïc Séguin-Charbonneau, F. Bruce Shepherd |
Ronen
Shaltiel |
|
3:40 |
- 4:00 |
Online
Node-weighted Steiner Tree and Related Problems |
A
Small PRG for Polynomial Threshold Functions of Gaussians |
|
|
|
Joseph
(Seffi) Naor, Debmalya Panigrahi, Mohit Singh |
Daniel
M. Kane |
|
4:00 |
- 4:30 |
Coffee Break. Foyer. |
|
|
|
|
Session 4. |
|
|
4:30 |
- 4:50 |
A Polylogarithmic-Competitive Algorithm for the k-Server
Problem |
|
|
|
|
Nikhil
Bansal, Niv Buchbinde, Aleksander Madry, Joseph
(Seffi) Naor |
|
|
4:55 |
- 5:15 |
3-SAT
Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General |
|
|
|
|
Timon Hertli |
|
|
5:20 |
- 6:20 |
Piore Award Presentation to Shafi Goldwasser Michael R. Williams on behalf of IEEE Piore Award Lecture: Pseudo Deterministic Algorithms |
|
|
|
|
Shafi Goldwasser |
|
|
9:00 |
- |
Business Meeting. |
|
|
|
|
|
|
|
Monday,
October 24 |
|
||
|
7:30 |
- 8:25 |
Continental Breakfast.
Foyer. |
|
|
|
|
Session 5A. |
Session 5B. |
|
8:25 |
- 8:45 |
On
the Power of Adaptivity in Sparse Recovery |
The
1D Area Law and the Complexity of Quantum States: A combinatorial approach |
|
|
|
Piotr Indyk, Eric Price, David P. Woodruff |
Dorit Aharonov, Itai
Arad, Zeph
Landau, Umesh
Vazirani |
|
8:50 |
- 9:10 |
(1+eps)-Approximate Sparse Recovery |
On
the complexity of Commuting Local Hamiltonians, and tight conditions for
Topological Order in such systems |
|
|
|
Eric
Price, David P. Woodruff |
Dorit Aharonov, Lior Eldar |
|
9:15 |
- 9:35 |
Near-Optimal
Column-Based Matrix Reconstruction |
Quantum
query complexity of state conversion |
|
|
|
Christos
Boutsidis, Petros Drineas,
Malik Magdon-Ismail |
Troy
Lee, Rajat Mittal, Ben W. Reichardt,
Robert Spalek, Mario Szegedy |
|
9:40 |
- 10:00 |
Near
Linear Lower Bound for Dimension Reduction in L1 |
Optimal bounds for quantum bit
commitment |
|
|
|
Alexandr Andoni, Moses S. Charikar, Ofer
Neiman, Huy
L. Nguyen |
André
Chailloux, Iordanis Kerenidis |
|
10:00 |
-10:45 |
Coffee Break. Foyer. |
|
|
|
|
Session 6A. |
Session 6B. |
|
10:45 |
- 11:05 |
Streaming
Algorithms via Precision Sampling |
The
Power of Linear Estimators |
|
|
|
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
|
Gregory
Valiant, Paul Valiant |
|
11:10 |
- 11:30 |
Steiner
Shallow-Light Trees are Exponentially Lighter than Spanning Ones |
An algebraic proof of a robust social choice
impossibility theorem |
|
|
|
Michael
Elkin, Shay Solomon |
Dvir Falik, Ehud Friedgut
|
|
11:35 |
- 11:55 |
Fully
dynamic maximal matching in O(log n) update time |
Planar
Graphs: Random Walks and Bipartiteness Testing |
|
|
|
Surender Baswana, Manoj
Gupta, Sandeep
Sen |
Artur Czumaj, Morteza
Monemizadeh,
Krzysztof Onak, Christian Sohler |
|
12:00 |
- 12:20 |
Which
Networks Are Least Susceptible to Cascading Failures? |
Testing
and Reconstruction of Lipschitz Functions with
Applications to Data Privacy |
|
|
|
|
Madhav Jha, Sofya Raskhodnikova |
|
12:30 |
- 1:45 |
Lunch. |
|
|
|
|
Session 7A. |
Session 7B. |
|
2:00 |
- 2:20 |
How
to Play Unique Games Against a Semi-Random Adversary |
Markov
Layout |
|
|
|
Alexandra
Kolla, Konstantin Makarychev,
Yury Makarychev |
Flavio Chierichetti, |
|
2:25 |
- 2:45 |
The
Grothendieck constant is strictly smaller than Krivine's bound |
Limitations
of Randomized Mechanisms for Combinatorial Auctions |
|
|
|
Mark
Braverman, Konstantin Makarychev,
Yury Makarychev, Assaf Naor |
Shaddin Dughmi, Jan Vondrak |
|
2:50 |
- 3:10 |
A
Parallel Approximation Algorithm for Positive Semidefinite
Programming |
Bayesian
Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers |
|
|
|
Rahul
Jain, Penghui Yao |
Saeed Alaei |
|
3:15 |
- 3:35 |
Rounding
Semidefinite Programming Hierarchies via Global
Correlation |
Extreme-Value
Theorems for Optimal Multidimensional Pricing |
|
|
|
Boaz
Barak, Prasad Raghavendra, David Steurer |
Yang
Cai, Constantinos Daskalakis |
|
3:40 |
- 4:00 |
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for
Graph Partitioning and Quadratic Integer Programming with PSD Objectives |
Efficient
computation of approximate pure Nash equilibria in
congestion games |
|
|
|
Venkatesan Guruswami, Ali
Kemal Sinop |
Ioannis Caragiannis, Angelo Fanelli, Nick
Gravin,
Alexander Skopalik |
|
4:00 |
- 4:30 |
Coffee Break. Foyer. |
|
|
|
|
Session 8. |
|
|
4:30 |
- 4:50 |
On
Range Searching in the Group Model and Combinatorial Discrepancy |
|
|
|
|
Kasper
Green Larsen |
|
|
4:55 |
- 5:15 |
A Randomized Rounding Approach to the
Traveling Salesman Problem |
|
|
|
|
Shayan Oveis Gharan,
Amin Saberi,
Mohit Singh |
|
|
5:20 |
- 5:40 |
Approximating
Graphic TSP by Matchings |
|
|
|
|
Tobias
Moemke,
Ola Svensson |
|
|
|
|
|
|
|
Tuesday,
October 25 |
|
||
|
7:30 |
- 8:25 |
Continental Breakfast.
Foyer. |
|
|
|
|
Session 9A. |
Session 9B. |
|
8:25 |
- 8:45 |
A Unified
Continuous Greedy Algorithm for Submodular
Maximization |
Lexicographic
Products and the Power of Non-Linear Network Coding |
|
|
|
Moran
Feldman, Joseph (Seffi) Naor, Roy Schwartz |
Anna
Blasiak, Robert Kleinberg, Eyal Lubetzky |
|
8:50 |
- 9:10 |
Enumerative
Lattice Algorithms in any Norm via M-ellipsoid Coverings |
Quadratic
Goldreich-Levin Theorems |
|
|
|
Daniel
Dadush, Chris Peikert, Santosh Vempala |
Madhur Tulsiani, Julia Wolf |
|
9:15 |
- 9:35 |
A
nearly-mlogn time solver for SDD linear systems |
Optimal
testing of multivariate polynomials over small prime fields |
|
|
|
Ioannis Koutis, Gary L. Miller, Richard Peng |
Elad Haramaty, Amir Shpilka, Madhu |
|
9:40 |
- 10:00 |
Balls
and Bins: Smaller Hash Families and Faster Evaluation |
Tight
lower bounds for 2-query LCCs over finite fields |
|
|
|
L.
Elisa Celis, Omer Reingold,
Gil Segev, Udi Wieder |
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka |
|
10:00 |
-10:30 |
Coffee Break. Foyer. |
|
|
|
|
Session 10A. |
Session 10B. |
|
10:30 |
- 10:50 |
A
Two Prover One Round Game with Strong Soundness |
Medium
Access Using Queues |
|
|
|
Subhash Khot, Muli Safra |
Devavrat Shah, Jinwoo Shin, Prasad Tetali |
|
10:55 |
- 11:15 |
The
Randomness Complexity of Parallel Repetition |
Local
Distributed Decision |
|
|
|
Kai-Min
Chung, |
Pierre
Fraigniaud, Amos Korman,
David Peleg |
|
11:20 |
- 11:40 |
Privacy
Amplification and Non-Malleable Extractors Via Character Sums |
The
Complexity of Renaming |
|
|
|
Yevgeniy Dodis, Xin
Li, Trevor D. Wooley, David Zuckerman |
Dan
Alistarh, James Aspnes,
Seth Gilbert, Rachid Guerraoui |
|
11:45 |
- 12:05 |
Stateless
Cryptographic Protocols |
Mutual
Exclusion with O(log^2 log n) Amortized Work |
|
|
|
Vipul Goyal, Hemanta
K. Maji |
Michael
A. Bender, Seth Gilbert |
|
12.10 |
- 12:30 |
Storing Secrets on
Continually Leaky Devices |
Algorithms
for the Generalized Sorting Problem
|
|
|
|
Yevgeniy Dodis, Allison Lewko,
Brent Waters, Daniel Wichs |
Zhiyi Huang, Sampath Kannan, Sanjeev Khanna |
|
12:30 |
- 1:45 |
Lunch. |
|
|
|
|
Session 11A. |
Session 11B. |
|
2:00 |
- 2:20 |
Information
Equals Amortized Communication |
Maximizing
Expected Utility for Stochastic Combinatorial Optimization Problems |
|
|
|
Mark
Braverman, Anup Rao |
Jian Li, Amol Deshpande |
|
2:25 |
- 2:45 |
Delays and the Capacity of Continuous-time
Channels |
Approximation
Algorithms for Submodular Multiway
Partition |
|
|
|
Sanjeev Khanna, Madhu |
Chandra
Chekuri,
Alina Ene |
|
2:50 |
- 3:10 |
Efficient
and Explicit Coding for Interactive Communication |
An
FPTAS for #Knapsack and Related Counting Problems |
|
|
|
Ran
Gelles, Ankur Moitra, Amit Sahai |
Parikshit Gopalan, Adam Klivans,
Raghu Meka, Daniel Stefankovic,
Santosh Vempala, Eric Vigoda |
|
3:15 |
- 3:35 |
Efficient
Reconstruction of Random Multilinear Formulas |
Approximation
Algorithms for Correlated Knapsacks and Non-Martingale Bandits |
|
|
|
Ankit Gupta, Neeraj Kayal, Satya Lokam |
Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro,
R. Ravi |
|
3:40 |
- 4:00 |
New
extension of the Weil bound for character sums with applications to coding |
Evolution with
Recombination |
|
|
|
Tali Kaufman, Shachar Lovett |
Varun Kanade |