|
|
|||
|
|
|
|
|
|
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 |
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 |
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öt;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 |
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 |
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 |
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 |