FOCS 2013 Schedule 


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 
Simultaneous Resettability from OneWay Functions 


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


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 
Iterative Row Sampling 


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 
A Polynomial Time
Algorithm for Lossy Population Recovery 
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 
Faster Canonical Forms
for Strongly Regular Graphs 
Bandits with Knapsacks 


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 
Learning Sums of
Independent Integer Random Variables 


Chandra Chekuri and Anastasios Sidiropoulos 
Constantinos Daskalakis, Ilias
Diakonikolas, Ryan O'Donnell, Rocco A. Servedio and LiYang Tan 
2:50 
 3:10 
Nonpositive curvature
and the planar embedding conjecture 
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 
Quasipolynomialtime Identity Testing of NonCommutative and ReadOnce
Oblivious Algebraic Branching Programs 


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 
Nearly Maximum Flows
in Nearly Linear Time 



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 
Towards a better
approximation for Sparsest Cut? 
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 
On Clustering Induced Voronoi Diagrams 


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 
The Complexity of
Approximating Vertex Expansion 
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 
Independent Set,
Induced Matching, and Pricing: Connections and Tight (Subexponential
Time) Approximation Hardnesses 
Klee's Measure Problem
Made Easy 


Parinya Chalermsook, Bundit
Laekhanukit, and Danupon Nanongkai 
Timothy M. Chan 
12:05 
 12:25 
Chasing the kcolorability threshold 
Playing Nonlinear
Games with Linear Oracles 


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



Session 7A. 
Session 7B. 
2:00 
 2:20 
Local Privacy and
Statistical Minimax Rates 
The MoserTardos Framework with Partial Resampling 


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 
KnowledgePreserving Interactive Coding 
Strong Backdoors to
Bounded Treewidth SAT 


KaiMin Chung, Rafael
Pass and Sidharth Telang 
Serge Gaspers and
Stefan Szeider 
3:15 
 3:35 
Adaptive Seeding in
Social Networks 
An O(c^k) n 5Approximation Algorithm for Treewidth 


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 
Dynamic Approximate
AllPairs Shortest Paths: Breaking the $ \tilde O(mn)
$ Barrier and Derandomization 
Arithmetic circuits: A
chasm at depth three 


Monika Henzinger, Sebastian Krinninger
and Danupon Nanongkai 
Ankit Gupta, Pritish Kamath, Neeraj Kayal
and Ramprasad Saptharishi 
9:10 
 9:30 
Fully Dynamic
$(1+\epsilon)$Approximate Matchings 
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 
Average Case Lower
Bounds for Monotone Switching Networks 


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 
Explicit Subspace
Designs 


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 
The Simple Economics
of Approximately Optimal Auctions 
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 
Common information and
unique disjointness 


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 
A linear time approximation
scheme for Euclidean TSP 
Nondeterministic
Direct Product Reductions and the Success Probability of SAT Solvers 


Yair Bartal and LeeAd Gottlieb 
Andrew Drucker 
2:25 
 2:45 
A forwardbackward
singlesource shortest paths algorithm 
Direct products in
communication complexity 


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 
Quantum 3SAT is
QMA1complete 


Sariel HarPeled and Nirman
Kumar 
David Gosset and Daniel Nagaj 
3:15 
 3:35 
The Parity of Directed
Hamiltonian Cycles 
Threeplayer entangled
XOR games are NPhard to approximate 


Andreas Björklund and Thore Husfeldt 
Thomas Vidick 