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_c_ Equivalences and Algorithms.pdf">Minimum Weight Cycles and Triangles: Equivalences and Algorithms

Randomness buys depth for approximate counting.pdf">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

 

 

Lawrence Blume, David Easley, Jon Kleinberg,  Robert Kleinberg, Eva Tardos

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, Ravi Kumar, Prabhakar Raghavan

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 Sudan

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,  Rafael Pass

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 Sudan

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