FOCS 2013 Program 


Saturday, October 26 


9:50 
 10:50 
Workshop 1: Bidimensional Structures: Algorithms and
Combinatorics History of Bidimensionality and Basic Bidimensionality Erik Demaine Workshop 2: Zeros of Polynomials and their Applications
to Theory Tutorial I: An
Introduction to Stability and Strongly Rayleigh Measures Nisheeth Vishnoi Workshop 3: New Techniques for Flow and Cut Problems Bridging the Numerical
and the Combinatorial: Emerging Tools, Techniques, and Design Principles for
Graph Algorithms Jonathan Kelner 

11:00 
 12:00 
Workshop 1: Bidimensional Structures: Algorithms and
Combinatorics The Square Root
Phenomenon in Planar Graphs Daniel Marx Workshop 2: Zeros of Polynomials and their Applications
to Theory Tutorial II: Hyperbolicity and Interlacing Adam Marcus Workshop 3: New Techniques for Flow and Cut Problems Efficient Oblivious
Routing: Computing Crude Approximations for Flow and Cut Problems in
AlmostLinear Time Aaron Sidford 

12:00 
 2:00 
Lunch (On your own) 

2:00 
 3:00 
Workshop 1: Bidimensional Structures: Algorithms and
Combinatorics Advanced Bidimensionality and Its Applications Fedor Fomin Workshop 2: Zeros of Polynomials and their Applications
to Theory The Traveling Salesman
Problem and Strongly Rayleigh Measures Shayan OveisGharan Workshop 3: New Techniques for Flow and Cut Problems Smooth Convex Optimization
and its Applications to Graph Algorithms Yin Tat Lee 

3:00 
 3:20 
Break 

3:20 
 5:30 
Workshop 1: Bidimensional Structures: Algorithms and
Combinatorics Bidimensionality and Graph Decomposition (3:204:00) MohammadTaghi Hajiaghayi Pursuing the
Dependence on Treewidth in Parameterized Algorithms
(4:054:45) Marek Cygan Polynomial Bounds for
the Grid Minor Theorem (4:505:30) Julia Chuzhoy Workshop 2: Zeros of Polynomials and their Applications
to Theory The Solution of the KadisonSinger Problem. Daniel Spielman (3:204:20) Phase Transitions,
Zeros of Polynomials and the Computational Complexity of Problems in
Statistical Physics Piyush Srivastava (4:305:30) Workshop 3: New Techniques for Flow and Cut Problems Electrical Flows,
InteriorPoint Methods, and the Maximum Flow Problem Aleksander Madry (3:204:20) Iterative Methods and Regularization
in the Design of Graph Algorithms: a Unified Framework for Optimization and
Online Learning Beyond Multiplicative Weight Updates Lorenzo Orecchia (4:305:30) 

6:00 
 9:00 
Reception 

Sunday, October 27 


8:00 
 8:45 
Continental Breakfast. 



Session 1A. 
Session 1B. 
8:45 
 9:05 
An
Optimal Randomized Online Algorithm for Reordering Buffer Management 
Candidate
Indistinguishability Obfuscation and Functional
Encryption for all circuits 


Noa AvigdorElgrabli and Yuval Rabani 
Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters 
9:10 
 9:30 
On
Randomized Memoryless Algorithms for the Weighted
$k$server Problem 
ConstantRound
Concurrent Zero Knowledge From PCertificates 


Ashish Chiplunkar
and Sundar Vishwanathan 
KaiMin Chung, Huijia Lin and Rafael Pass 
9:35 
 9:55 
Approximating
Bin Packing within O(log OPT * log log OPT) bins 



Thomas Rothvoss 
KaiMin Chung, Rafail Ostrovsky,
Rafael Pass and Ivan Visconti 
10:00 
 10:20 
Approximating
MinimumCost kNode Connected Subgraphs via
IndependenceFree Graphs 



Joseph Cheriyan and
Laszlo A. Vegh 
Ran Canetti, Huijia Lin and Rafael Pass 
10:20 
10:50 
Coffee Break. 



Session 2A. 
Session 2B. 
10:50 
 11:10 
How
to Approximate A Set Without Knowing Its Size In Advance 
OSNAP:
Faster numerical linear algebra algorithms via sparser subspace embeddings 


Rasmus Pagh, Gil Segev
and Udi Wieder 
Jelani Nelson and Huy L. Nguyen 
11:15 
 11:35 
Simple
Tabulation, Fast Expanders, Double Tabulation, and High Independence 



Mikkel Thorup 
Mu Li, Gary L. Miller,
and Richard Peng 
11:40 
 12:00 
Extractors
for a Constant Number of Independent Sources with Polylogarithmic
MinEntropy 
Algebraic
Algorithms for bMatching, Shortest Undirected Paths, and fFactors 


Xin Li 
Harold N. Gabow and Piotr Sankowski 
12:05 
 12:25 
Efficient
Accelerated Coordinate Descent Methods and Faster Algorithms for Solving
Linear Systems 



Ankur Moitra and
Michael Saks 
Yin Tat Lee and Aaron Sidford 
12:30 
 1:45 
Lunch. 



Session 3A. 
Session 3B. 
2:00 
 2:20 



László Babai, Xi Chen, Xiaorui
Sun, ShangHua Teng and
John Wilmes 
Ashwinkumar Badanidiyuru, Robert Kleinberg and Aleksandrs Slivkins 
2:25 
 2:45 
Approximation
algorithms for Euler genus and related problems 



Chandra Chekuri and Anastasios Sidiropoulos 
Constantinos Daskalakis, Ilias
Diakonikolas, Ryan O'Donnell, Rocco A. Servedio and LiYang Tan 
2:50 
 3:10 
Optimal
Bounds on Approximation of Submodular and XOS
Functions by Juntas 



Anastasios Sidiropoulos 
Vitaly Feldman and Jan Vondrak 
3:15 
 3:35 
Allornothing
multicommodity flow problem with bounded fractionality in planar graphs 
Estimating
the distance from testable affineinvariant properties 


Kenichi Kawarabayashi
and Yusuke Kobayashi 
Hamed Hatami and Shachar
Lovett 
3:40 
 4:00 
The
planar directed kVertexDisjoint Paths problem is fixedparameter tractable 



Marek Cygan, Dániel
Marx, Marcin Pilipczuk and
Michał Pilipczuk 
Michael A. Forbes and
Amir Shpilka 
4:00 
 4:30 
Coffee Break. Foyer. 



Session 4. 

4:30 
 4:50 
Navigating
Central Path with Electrical Flows: from Flows to Matchings,
and Back 



Aleksander Madry 

4:55 
 5:15 



Jonah Sherman 

5:20 
 6:20 
Invited talk: Moses S. Charikar
on the occasion of the 2012 Paris Kanellakis
Theory and Practice award, awarded to 





7:30 
 9:00 
Drinks, hors d'oeuvres, and concert by the
Positive Eigenvalues! 

9:00 
Business Meeting. 

Monday, October 28 


8:00 
 8:45 
Continental Breakfast. 



Session 5A. 
Session 5B. 
8:45 
 9:05 
Polar
Codes: Speed of polarization and polynomial gap to capacity 



Sanjeev Arora, Rong
Ge and Ali Kemal Sinop 
Venkatesan Guruswami and Patrick Xia 
9:10 
 9:30 
Layered
Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive
Coloring 
Constant
rate PCPs for circuitSAT with sublinear query
complexity 


Vida Dujmović, Pat Morin and David R. Wood 
Eli BenSasson, Yohay Kaplan,
Swastik Kopparty, Or Meir and Henning Stichtenoth 
9:35 
 9:55 
Element
Distinctness, Frequency Moments, and Sliding Windows 
Strong
LTCs with inverse polylog rate and constant soundness 


Paul Beame, Raphael
Clifford and Widad Machmouchi 
Michael Viderman 
10:00 
 10:20 
Spatial
mixing and approximation algorithms for graphs with bounded connective
constant 
PCPs
via lowdegree long code and hardness for constrained hypergraph
coloring 


Alistair Sinclair, Piyush
Srivastava, and Yitong Yin 
Irit Dinur and Venkatesan
Guruswami 
10:20 
10:50 
Coffee Break. 



Session 6A. 
Session 6B. 
10:50 
 11:10 
Approximate
Constraint Satisfaction Requires Large LP Relaxations 



Siu On Chan, James R.
Lee, Prasad Raghavendra and David Steurer 
Danny Z. Chen, Ziyun Huang, Yangwei Liu, and Jinhui Xu 
11:15 
 11:35 
Approximation
Schemes for Maximum Weight Independent Set of Rectangles 



Anand Louis, Prasad Raghavendra and Santosh Vempala 
Anna Adamaszek and Andreas Wiese 
11:40 
 12:00 



Parinya Chalermsook, Bundit
Laekhanukit, and Danupon Nanongkai 
Timothy M. Chan 
12:05 
 12:25 



Amin CojaOghlan and Dan Vilenchik 
Dan Garber, and Elad Hazan 
12:30 
 1:45 
Lunch. 



Session 7A. 
Session 7B. 
2:00 
 2:20 



John C. Duchi, Michael
I. Jordan, and Martin J. Wainwright 
David G. Harris and Aravind Srinivasan 
2:25 
 2:45 
CoupledWorlds
Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy 
A
Satisfiability Algorithm for Sparse Depth Two
Threshold Circuits 


Raef Bassily, Adam Groce,
Jonathan Katz and Adam Smith 
Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider 
2:50 
 3:10 



KaiMin Chung, Rafael
Pass and Sidharth Telang 
Serge Gaspers and
Stefan Szeider 
3:15 
 3:35 



Lior Seeman and Yaron
Singer 
Hans L. Bodlaender, Paal G. Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov and Michal Pulipczuk 
3:40 
 4:00 

Improved
approximation for 3dimensional matching via bounded pathwidth
local search 



Marek Cygan 
4:00 
 4:30 
Coffee Break. 



Session 8. 

4:30 
 4:50 
On
Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed
Motions 



Natan Rubin 

4:55 
 5:15 
Interlacing
Families I: Bipartite Ramanujan Graphs of All
Degrees 



Adam Marcus, Daniel A.
Spielman and Nikhil Srivastava 

Tuesday, October 29 


8:00 
 8:45 
Continental Breakfast. 



Session 9A. 
Session 9B. 
8:45 
 9:05 



Monika Henzinger, Sebastian Krinninger
and Danupon Nanongkai 
Ankit Gupta, Pritish Kamath,
Neeraj Kayal and Ramprasad Saptharishi 
9:10 
 9:30 
Improved
AverageCase Lower Bounds for DeMorgan Formula
Size 



Manoj Gupta, and Richard Peng 
Ilan Komargodski, Ran
Raz and Avishay Tal 
9:35 
 9:55 
Online
Nodeweighted Steiner Forest and Extensions via Disk Paintings 



Mohammad Taghi Hajiaghayi, Vahid Liaghat and Debmalya Panigrahi 
Yuval Filmus, Toniann Pitassi, Robert Robere and
Stephen A. Cook 
10:00 
 10:20 
An
LMP O(log n)Approximation Algorithm for Node Weighted Prize Collecting
Steiner Tree 


Jochen Koenemann, Sina
Sadeghian and Laura Sanitŕ 
Venkatesan Guruswami and Swastik
Kopparty 

10:20 
10:50 
Coffee Break. 



Session 10A. 
Session 10B. 
10:50 
 11:10 
Understanding
Incentives: Mechanism Design becomes Algorithm Design 
Fourier
sparsity, spectral norm, and the Logrank
conjecture 


Yang Cai, Constantinos Daskalakis and S. Matthew Weinberg 
Hing Yin Tsang, Chung Hoi Wong, Ning Xie and Shengyu Zhang 
11:15 
 11:35 
Tight
Bounds for Set Disjointness in the Message Passing
Model 



Saeed Alaei, Hu Fu, Nima
Haghpanah and Jason Hartline 
Mark Braverman, Faith Ellen, Rotem Oshman, Toni Pitassi and Vinod
Vaikuntanathan 
11:40 
 12:00 
The
Price of Stability for Undirected Broadcast Network Design with Fair Cost
Allocation is Constant 
On
the communication complexity of sparse set disjointness
and existsequal problems 


Vittorio Bilň, Michele
Flammini and Luca Moscardelli 
Mert Sağlam and Gábor
Tardos 
12:05 
 12:25 
Rational
Protocol Design: Cryptography Against Incentivedriven Adversaries 



Juan Garay , Jonathan Katz, Ueli
Maurer, Bjoern Tackmann
and Vassilis Zikas 
Gábor Braun and Sebastian Pokutta 
12:30 
 1:45 
Lunch. 



Session 11A. 
Session 11B. 
2:00 
 2:20 
Nondeterministic
Direct Product Reductions and the Success Probability of SAT Solvers 



Yair Bartal and LeeAd Gottlieb 
Andrew Drucker 
2:25 
 2:45 



David Wilson and Uri Zwick 
Mark Braverman, Anup Rao, Omri Weinstein and Amir Yehudayoff 
2:50 
 3:10 
Approximating
Minimization Diagrams and Generalized Proximity Search 



Sariel HarPeled and Nirman
Kumar 
David Gosset and Daniel Nagaj 
3:15 
 3:35 



Andreas Björklund and Thore Husfeldt 
Thomas Vidick 