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 Almost-Linear 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 Oveis-Gharan 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:20-4:00) MohammadTaghi Hajiaghayi Pursuing the Dependence on Treewidth in Parameterized Algorithms (4:05-4:45) Marek Cygan Polynomial Bounds for the Grid Minor Theorem (4:50-5:30) Julia Chuzhoy Workshop 2: Zeros of Polynomials and their Applications to Theory The Solution of the Kadison-Singer Problem. Daniel Spielman (3:20-4:20) Phase Transitions, Zeros of Polynomials and the Computational Complexity of Problems in Statistical Physics Piyush Srivastava (4:30-5:30) Workshop 3: New Techniques for Flow and Cut Problems Electrical Flows, Interior-Point Methods, and the Maximum Flow Problem Aleksander Madry (3:20-4: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:30-5: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 Avigdor-Elgrabli 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	Constant-Round Concurrent Zero Knowledge From P-Certificates
		Ashish Chiplunkar and Sundar Vishwanathan	Kai-Min Chung, Huijia Lin and Rafael Pass
9:35	- 9:55	Approximating Bin Packing within O(log OPT * log log OPT) bins	Simultaneous Resettability from One-Way Functions
		Thomas Rothvoss	Kai-Min Chung, Rafail Ostrovsky, Rafael Pass and Ivan Visconti
10:00	- 10:20	Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free 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 Min-Entropy	Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors
		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, Shang-Hua 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 Li-Yang Tan
2:50	- 3:10	Non-positive 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	All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs	Estimating the distance from testable affine-invariant properties
		Ken-ichi Kawarabayashi and Yusuke Kobayashi	Hamed Hatami and Shachar Lovett
3:40	- 4:00	The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable	Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once 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 Andrei Broder, Moses Charikar, and Piotr Indyk
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 circuit-SAT with sublinear query complexity
		Vida Dujmović, Pat Morin and David R. Wood	Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir and Henning Stichtenoth
9:35	- 9:55	Element Distinctness, Frequency Moments, and Sliding Windows	Strong LTCs with inverse poly-log 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 low-degree 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 k-colorability threshold	Playing Non-linear Games with Linear Oracles
		Amin Coja-Oghlan 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 Moser-Tardos Framework with Partial Resampling
		John C. Duchi, Michael I. Jordan, and Martin J. Wainwright	David G. Harris and Aravind Srinivasan
2:25	- 2:45	Coupled-Worlds 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	Knowledge-Preserving Interactive Coding	Strong Backdoors to Bounded Treewidth SAT
		Kai-Min 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 5-Approximation 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 3-dimensional 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 All-Pairs 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 Average-Case Lower Bounds for DeMorgan Formula Size
		Manoj Gupta, and Richard Peng	Ilan Komargodski, Ran Raz and Avishay Tal
9:35	- 9:55	Online Node-weighted 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 Log-rank 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 exists-equal problems
		Vittorio Bilò, Michele Flammini and Luca Moscardelli	Mert Sağlam and Gábor Tardos
12:05	- 12:25	Rational Protocol Design: Cryptography Against Incentive-driven 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 Lee-Ad Gottlieb	Andrew Drucker
2:25	- 2:45	A forward-backward single-source 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 3-SAT is QMA1-complete
		Sariel Har-Peled and Nirman Kumar	David Gosset and Daniel Nagaj
3:15	- 3:35	The Parity of Directed Hamiltonian Cycles	Three-player entangled XOR games are NP-hard to approximate
		Andreas Björklund and Thore Husfeldt	Thomas Vidick