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