|
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 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 |
|
|
|
|
|
|
|
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 |