FOCS 2012 Program

 

 

 

 

 

Saturday, October 20, 2012

 

9:00am

- 6:00pm

Workshops - Regency A/B/C: see Workshops page

6:00

-9:00pm

Welcome Reception - Garden State Ballroom

 

 

 

 

Sunday, October 21, 2012

 

7:30

- 8:45

Continental Breakfast

 

 

Session 1A - Regency ABC

Session 1B - Garden State Ballroom

8:45

- 9:05

Learning Topic Models --- Going beyond SVD

How to Compute in the Presence of Leakage

 

 

Sanjeev Arora and Rong Ge and Ankur Moitra

Shafi Goldwasser and Guy Rothblum

9:10

- 9:30

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas

Positive Results for Concurrently Secure Computation in the Plain Model

 

 

Gregory Valiant

Vipul Goyal

9:35

- 9:55

Active Property Testing

Constructing Non-Malleable Commitments: A Black-Box Approach

 

 

Maria-Florina Balcan and Eric Blais and Avrim Blum and Liu Yang

Vipul Goyal and Chen-Kuei Lee and Rafail Ostrovsky and Ivan Visconti

9:55

-10:25

Coffee Break

 

 

Session 2A - Regency ABC

Session 2B - Garden State Ballroom

10:25

- 10:45

Constructive Discrepancy Minimization by Walking on The Edges

A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions

 

 

Shachar Lovett and Raghu Meka

Daniel M. Kane

10:50

- 11:10

Combinatorial coloring of 3-colorable graphs

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits

 

 

Ken-ichi Kawarabayashi and Mikkel Thorup

Chris Beck and Russell Impagliazzo and Shachar Lovett

11:15

- 11:35

A Permanent Approach to the Traveling Salesman Problem

Pseudorandomness from Shrinkage

 

 

Nisheeth K. Vishnoi

Russell Impagliazzo and Raghu Meka and David Zuckerman

11:40

- 12:00

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs

Better Pseudorandom Generators from Milder Pseudorandom Restrictions

 

 

Costas Busch and Chinmoy Dutta and Jaikumar Radhakrishnan and
Rajmohan Rajaraman and Srivathsan Srinivasagopalan

Parikshit Gopalan and Raghu Meka and Omer Reingold and Luca Trevisan and Salil Vadhan

12:00

- 1:30

Lunch - Brunswick Ballroom

 

 

Session 3A - Regency ABC

Session 3B - Garden State Ballroom

1:30

- 1:50

Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization

Efficient Interactive Coding Against Adversarial Noise

 

 

Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg

Zvika Brakerski and Yael Tauman Kalai

1:55

- 2:15

The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal

A direct product theorem for the two-party bounded-round public-coin communication complexity

 

 

Zhiyi Huang and Sampath Kannan

Rahul Jain and Attila Pereszlenyi and Penghui Yao

2:20

- 2:40

Concave Generalized Flows with Applications to Market Equilibria

An additive combinatorics approach relating rank to communication complexity

 

 

Laszlo A. Vegh

Eli Ben-Sasson and Shachar Lovett and Noga Ron-Zewi

2:40

- 3:10

Coffee Break

 

 

Session 4A - Regency ABC

Session 4B - Garden State Ballroom

3:10

- 3:30

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering

Learning-graph-based Quantum Algorithm for k-distinctness

 

 

Shayan Oveis Gharan and Luca Trevisan

Aleksandrs Belovs

3:35

- 3:55

Faster SDP hierarchy solvers for local rounding algorithms

A PTAS for Computing the Supremum of Gaussian Processes

 

 

Venkatesan Guruswami and Ali Kemal Sinop

Raghu Meka

 

 

Session 5 - Regency ABC

4:15

- 4:35

From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique

 

 

Nir Bitansky and Omer Paneth

 

4:40

- 5:00

A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

 

 

Julia Chuzhoy and Shi Li

 

5:05

- 5:25

MIP* contains NEXP

 

 

Tsuyoshi Ito and Thomas Vidick

 

 

 

Special Session - Regency ABC

8:00

- 9:00pm

The Work of Mihai Pătraşcu

 

 

Mikkel Thorup

 

9:00

-11:00pm

Business Meeting - Regency ABC

 

 

 

 

Monday, October 22, 2012

 

7:30

- 8:45

Continental Breakfast

 

 

Session 6A - Regency ABC

Session 6B - Garden State Ballroom

8:45

- 9:05

Beck's three permutations conjecture: A counterexample and
some consequences

On-line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List

 

 

Alantha Newman and Ofer Neiman and Aleksandar Nikolov

Tsvi Kopelowitz

9:10

- 9:30

Iterative rounding approximation algorithms for degree-bounded node-connectivity network design

Higher Cell Probe Lower Bounds for Evaluating Polynomials

 

 

Takuro Fukunaga and R. Ravi

Kasper Green Larsen

9:35

- 9:55

LP Rounding for k-Centers with Non-uniform Hard Capacities

The tile assembly model is intrinsically universal

 

 

Marek Cygan and MohammadTaghi Hajiaghayi and Samir Khuller

 

David Doty and Jack H. Lutz and Matthew J. Patitz and Robert T. Schweller and Scott M. Summers and Damien Woods

9:55

-10:25

Coffee Break

 

 

Session 7A - Regency ABC

Session 7B - Garden State Ballroom

10:25

- 10:45

The Dynamics of Influence Systems

On the complexity of finding narrow proofs

 

 

Bernard Chazelle

Christoph Berkholz

10:50

- 11:10

The Locality of Distributed Symmetry Breaking

The computational hardness of counting in two-spin models on d-regular graphs

 

 

Leonid Barenboim and Michael Elkin and Seth Pettie and Johannes Schneider

Allan Sly and Nike Sun

11:15

- 11:55

How to Allocate Tasks Asynchronously

Making the Long Code Shorter

 

 

Dan Alistarh and Michael A. Bender and Seth Gilbert and Rachid Guerraoui

Boaz Barak and Parikshit Gopalan and Johan Hastad and Raghu Meka and Prasad Raghavendra and David Steurer

11:40

- 12:00

Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies

Hardness of Finding Independent Sets in Almost q-Colorable Graphs

 

 

Thomas Sauerwald and He Sun

Subhash Khot and Rishi Saket

12:00

- 1:30

Lunch - Brunswick Ballroom 

 

 

Session 8A - Regency ABC

Session 8B - Garden State Ballroom

1:30

- 1:50

Population Recovery and Partial Identification

On Range Searching with Semialgebraic Sets II

 

 

Avi Wigderson and Amir Yehudayoff

Pankaj K. Agarwal and Jiri Matousek and Micha Sharir

1:55

- 2:15

The Privacy of the Analyst and The Power of the State

Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space

 

 

Cynthia Dwork and Moni Naor and Salil Vadhan

Sariel Har-Peled and Nirman Kumar

2:20

- 2:40

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

On the homotopy test on surfaces

 

 

Jeremiah Blocki and Avrim Blum and Anupam Datta and Or Sheffet

Francis Lazarus and Julien Rivaud

2:40

- 3:10

Coffee Break

 

 

Session 9A - Regency ABC

Session 9B - Garden State Ballroom

3:10

- 3:30

Representative sets and irrelevant vertices: New tools for kernelization

Approximation Limits of Linear Programs (Beyond Hierarchies)

 

 

Stefan Kratsch and Magnus Wahlström

Gábor Braun and Samuel Fiorini and Sebastian Pokutta and David Steurer

3:35

- 3:55

Designing FPT algorithms for cut problems using randomized contractions

Formulas Resilient to Short-Circuit Errors

 

 

Rajesh Chitnis and Marek Cygan and MohammadTaghi Hajiaghayi and
Marcin Pilipczuk and Michał Pilipczuk

Yael Kalai and Allison Lewko and Anup Rao

 

4:00

- 4:20

Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms

Lower bounds on Information Complexity via zero-communication protocols and applications

 

 

Fedor Fomin and Daniel Lokshtanov and Neeldhara Misra and Saket Saurabh

Iordanis Kerenidis and Sophie Laplante and Virginie Lerays and Jeremie Roland and David Xiao

 

 

Session 10 - Regency ABC

4:40

- 5:45

Knuth Prize Lecture - Turing's Password: What Internet Cannot Leak

 

 

Leonid Levin

 

8:30

-10:30pm

Poster Session - Atrium

Tuesday, October 23, 2012

 

7:30

- 8:45

Continental Breakfast

 

 

Session 11A - Regency ABC

Session 11B - Garden State Ballroom

8:45

- 9:05

Faster Algorithms for Rectangular Matrix Multiplication

Almost Optimal Canonical Property Testers for Satisfiability

 

 

Francois Le Gall

Christian Sohler

9:10

- 9:30

Quasi-optimal multiplication of linear differential operators

Partially Symmetric Functions are Efficiently Isomorphism-Testable

 

 

Alexandre Benoit and Alin Bostan and Joris van der Hoeven

Eric Blais and Amit Weinstein and Yuichi Yoshida

9:35

- 9:55

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings

Sparse affine-invariant linear codes are locally testable

 

 

Marek Cygan and Harold N. Gabow and Piotr Sankowski

 

Eli Ben-Sasson and Noga Ron-Zewi and Madhu Sudan

9:55

-10:25

Coffee Break

 

 

Session 12A - Regency ABC

Session 12B - Garden State Ballroom

10:25

- 10:45

The Cutting Plane Method is Polynomial for Perfect Matchings

New Limits to Classical and Quantum Instance Compression

 

 

Karthekeyan Chandrasekaran and Laszlo A. Vegh and Santosh S. Vempala

Andrew Drucker

10:50

- 11:10

A weight-scaling algorithm for min-cost imperfect matchings in
bipartite graphs

Lower Bounds for Interactive Compression by Constant-Depth Circuits

 

 

Lyle Ramshaw and Robert E. Tarjan

Arkadev Chattopadhyay and Rahul Santhanam

11:15

- 11:55

A New Direction for Counting Perfect Matchings

Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's normalization lemma

 

 

Taisuke Izumi and Tadashi Wadayama

Ketan D. Mulmuley

11:40

- 12:00

Single Source - All Sinks Max Flows in Planar Digraphs

Computing Multiplicities of Lie Group Representations

 

 

 Jakub Lacki and Yahav Nussbaum and Piotr Sankowski
and Christian Wulff-Nilsen

Matthias Christandl and Brent Doran and Michael Walter

12:00

- 1:30

Lunch - Brunswick Ballroom

 

 

Session 13A - Regency ABC

Session 13B - Garden State Ballroom

1:30

- 1:50

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

How to Construct Quantum Random Functions

 

 

Niv Buchbinder and Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz

Mark Zhandry

1:55

- 2:15

A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint

Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification

 

 

Yuval Filmus and Justin Ward

Xin Li

2:20

- 2:40

The power of linear programming for valued CSPs

Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls

 

 

Johan Thapper and Stanislav Zivny

Thomas Holenstein and Makrand Sinha

2:40

- 3:00

Break

 

 

Session 14A - Regency ABC

Session 14B - Garden State Ballroom

3:00

- 3:20

Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis

A New Infinity of Distance Oracles for Sparse Graphs

 

 

Matthias Poloczek and Mario Szegedy

Mihai Pătraşcu and Liam Roditty and Mikkel Thorup

3:25

- 3:45

Matching with our Eyes Closed

Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths

 

 

Gagan Goel and Pushkar Tripathi

Fabrizio Grandoni and Virginia Vassilevska Williams

 

3:50

- 4:10

Online Matching with Stochastic Rewards

Everywhere-Sparse Spanners via Dense Subgraphs

 

 

Aranyak Mehta and Debmalya Panigrahi

Eden Chlamtac and Michael Dinitz and Robert Krauthgamer