Conference Program
Saturday May 31, 2014
| Workshops (at Columbia University) | |||
| 9:45-5:30 |
Recent Advances on the Lovasz Local Lemma Organizers: David Harris, Aravind Srinivasan, Mario Szegedy, Gabor Tardos |
Efficient Distribution Estimation
Organizers: Ilias Diakonikolas, Gregory Valiant |
Overcoming the intractability bottleneck in unsupervised machine
learning Organizers: Sanjeev Arora, Rong Ge, Ankur Moitra |
| 7:00-9:00 | Welcome reception (at New Yorker Hotel) | ||
Sunday June 1, 2014
| Session 1A Chair: Katrina Ligett Location: Grand Ballroom |
Session 1B Chair: Ola Svensson Location: Crystal Ballroom | |
| 8:55-9:15 | Fingerprinting Codes and the Price of Approximate Differential Privacy Mark Bun, Jonathan Ullman, Salil Vadhan |
Rounding Sum-of-Squares Relaxations Boaz Barak, Jonathan A. Kelner, David Steurer |
| 9:20-9:40 | Analyze Gauss: Optimal Bounds for Privacy-Preserving PCA Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, Li Zhang |
Constant Factor Approximation for Balanced Cut in the PIE Model Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 9:45-10:05 | Private Matchings and Allocations Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, Zhiwei Steven Wu |
Entropy, Optimization and Counting Mohit Singh, Nisheeth K. Vishnoi |
| 10:05-10:30 | Coffee Break | |
| Session 2A Chair: Gregory Valiant Location: Grand Ballroom |
Session 2B Chair: Chris Umans Location: Crystal Ballroom | |
| 10:30-10:50 | Polynomial Bounds for the Grid-Minor Theorem Chandra Chekuri, Julia Chuzhoy |
Pseudorandom generators with optimal seed length for non-boolean poly-size circuits Sergei Artemenko, Ronen Shaltiel |
| 10:55-11:15 | An Excluded Half-Integral Grid Theorem for Digraphs and the Directed Disjoint Paths Problem Ken-ichi Kawarabayashi, Yusuke Kobayashi, Stephan Kreutzer |
On Derandomizing Algorithms that Err Extremely Rarely Oded Goldreich, Avi Wigderson |
| 11:20-11:40 | Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar |
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan |
| Lower bounds for depth 4 formulas computing iterated matrix multiplication Herve Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan |
||
| 11:45-12:05 | Deciding first-order properties of nowhere dense graphs Martin Grohe, Stephan Kreutzer, Sebastian Siebertz |
The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in Mrinal Kumar, Shubhangi Saraf |
|
A super-polynomial lower bound for regular arithmetic formulas Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi |
||
| 12:05-1:25 | Lunch (on your own) | |
| Session 3A Chair: Ronitt Rubinfeld Location: Grand Ballroom |
Session 3B Chair: Adam Smith Location: Crystal Ballroom | |
| 1:30-1:50 | A Characterization of Locally Testable Affine-Invariant Properties via Decomposition Theorems Yuichi Yoshida |
New algorithms and lower bounds for circuits with linear threshold gates Ryan Williams |
| 1:55-2:15 | Lp-Testing Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev |
Formulas vs. Circuits for Small Distance Connectivity Benjamin Rossman |
| 2:20-2:40 | Turnstile Streaming Algorithms Might as Well Be Linear Sketches Yi Li, Huy L. Nguyen, David P. Woodruff |
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson |
| 2:45-3:05 | Linear time construction of compressed text indexes in compact space Djamal Belazzougui |
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits Alexander A. Sherstov |
| 3:05-3:30 | Coffee Break | |
| Session 4A Chair: Brendan Lucier Location: Grand Ballroom |
Session 4B Chair: Thomas Vidick Location: Crystal Ballroom | |
| 3:30-3:50 | Economic Efficiency Requires Interaction Shahar Dobzinski, Noam Nisan, Sigal Oren |
Homological product codes Sergey Bravyi, Matthew Hastings |
| 3:55-4:15 | The Sample Complexity of Revenue Maximization Richard Cole, Tim Roughgarden |
Exponential improvement in precision for simulating sparse Hamiltonians Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma |
| 4:20-4:40 | Optimal Competitive Auctions Ning Chen, Nick Gravin, Pinyan Lu |
A quantum algorithm for computing the unit group of an arbitrary degree number field Kirsten Eisentrager, Sean Hallgren, Alexei Kitaev, Fang Song |
| Plenary Talks Chair: David Shmoys Location: Grand Ballroom | ||
| 4:55-5:15 | The matching polytope has exponential extension complexity Thomas Rothvoss |
|
| 5:30-7:30 | The Turing Award Lectures Shafi Goldwasser, Silvio Micali |
|
Monday June 2, 2014
| Session 5A Chair: Nikhil Bansal Location: Grand Ballroom |
Session 5B Chair: Katrina Ligett Location: Crystal Ballroom | |
| 8:55-9:15 | Primal Beats Dual on Online Packing LPs in the Random-Order Model Thomas Kesselheim, Klaus Radke, Andreas Toennis, Berthold Voecking |
An Efficient Parallel Solver for SDD Linear Systems Richard Peng, Daniel A. Spielman |
| 9:20-9:40 | Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints Sungjin Im, Janardhan Kulkarni, Kamesh Munagala |
Solving SDD Linear Systems in Nearly mlog1/2n Time Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup Rao, Shen Chen Xu |
| 9:45-10:05 | Minimum Bisection is Fixed Parameter Tractable Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
Optimal CUR Matrix Decompositions Christos Boutsidis, David P. Woodruff |
| 10:05-10:30 | Coffee Break | |
| Session 6A Chair: Boris Aronov Location: Grand Ballroom |
Session 6B Chair: Vinod Vaikuntanathan Location: Crystal Ballroom | |
| 10:30-10:50 | From Hierarchical Partitions to Hierarchical Covers: Optimal Fault-Tolerant Spanners for Doubling Metrics Shay Solomon |
Coin Flipping of Any Constant Bias Implies One-Way Itay Berman, Iftach Haitner, Aris Tentes |
| 10:55-11:15 | Shortest Paths on Polyhedral Surfaces and Terrains Siu-Wing Cheng, Jiongxin Jin |
An Almost Optimally-Fair Three-Party Coin-Flipping Protocol Iftach Haitner, Eliad Tsfadia |
| 11:20-11:40 | Embedding and Canonizing Graphs of Bounded Genus in Logspace Michael Elberfeld, Ken-ichi Kawarabayashi |
Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices Carl A. Miller, Yaoyun Shi |
| 11:45-12:05 | Testing surface area with arbitrary accuracy Joe Neeman |
Infinite Randomness Expansion with a Constant Number of Devices Matthew Coudron, Henry Yuen |
| 12:05-1:45 | Lunch (provided at the conference) | |
| Session 7A Chair: Nikhil Bansal Location: Grand Ballroom |
Session 7B Chair: Adam Smith Location: Crystal Ballroom | |
| 1:45-2:05 | The Average Sensitivity of an Intersection of Half Spaces Daniel M. Kane |
How to Use Indistinguishability Obfuscation: Deniable Encryption, and More Amit Sahai, Brent Waters |
| 2:10-2:30 | From average case complexity to improper learning complexity Amit Daniely, Nati Linial, Shai Shalev-Shwartz |
How to Delegate Computations: The Power of No-Signaling Proofs Yael Tauman Kalai, Ran Raz, Ron D. Rothblum |
| 2:35-2:55 | The Power of Localization for Efficiently Learning Linear Separators with Noise Pranjal Awasthi, Maria Florina Balcan, Philip M. Long |
Circuits Resilient to Additive Attacks with Applications to Secure Computation Daniel Genkin, Yuval Ishai, Manoj M. Prabhakaran, Amit Sahai, Eran Tromer |
| 3:00-3:20 | Bandits with Switching Costs: T2/3 Regret Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres |
On the Existence of Extractable One-Way Functions Nir Bitansky, Ran Canetti, Omer Paneth, Alon Rosen |
| 3:25-3:45 | Online learning of local structure via semidefinite programming Paul F. Christiano |
Black-Box Non-Black-Box Zero Knowledge Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti |
| 3:45-4:15 | Coffee Break | |
| Session 8A Chair: Brendan Lucier Location: Grand Ballroom |
Session 8B Chair: Mikkel Thorup Location: Crystal Ballroom | |
| 4:15-4:35 | Dichotomies in Equilibrium Computation, and Complementary Pivot Algorithms for a New Class of Non-Separable Utility Jugal Garg, Ruta Mehta, Vijay V. Vazirani |
Approximation Algorithms for Bipartite Matching with Metric and Geometric Costs Pankaj K. Agarwal, R. Sharathkumar |
| 4:40-5:00 | Query Complexity of Approximate Nash Equilibria Yakov Babichenko |
Distributed Approximation Algorithms for Weighted Shortest Paths Danupon Nanongkai |
| 5:05-5:25 | Constant Rank Bimatrix Games are PPAD-Hard Ruta Mehta |
Parallel Algorithms for Geometric Graph Problems Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev |
| 8:30-10:30 | Business meeting (Grand Ballroom) | |
Tuesday June 3, 2014
| Session 9A Chair: David Shmoys Location: Grand Ballroom |
Session 9B Chair: Thomas Vidick Location: Crystal Ballroom | |
| 8:55-9:15 | Fourier PCA and Robust Tensor Decomposition Navin Goyal, Santosh Vempala, Ying Xiao |
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes Venkatesan Guruswami, Prahladh Harsha, Johan Hastad, Srikanth Srinivasan, Girish Varma |
| 9:20-9:40 | Smoothed Analysis of Tensor Decompositions Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan |
Analytical Approach to Parallel Repetition Irit Dinur, David Steurer |
| 9:45-10:05 | Efficient Density Estimation via Piecewise Polynomial Approximation Siu On Chan, Ilias Diakonikolas, Rocco Servedio, Xiaorui Sun |
A Characterization of Strong Approximation Resistance Subhash Khot, Madhur Tulsiani, Pratik Worah |
| 10:05-10:30 | Coffee Break | |
| Session 10A Chair: Ola Svensson Location: Grand Ballroom |
Session 10B Chair: Mikkel Thorup Location: Crystal Ballroom | |
| 10:30-10:50 | A strongly polynomial algorithm for generalized flow maximization Laszlo A. Vegh |
Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time Michael T. Goodrich |
| 10:55-11:15 | Approximate Distance Oracles with Constant Query Time Shiri Chechik |
Community detection thresholds and the weak Ramanujan property Laurent Massoulie |
| 11:20-11:40 | Faster all-pairs shortest paths via circuit complexity Ryan Williams |
Distributed Computability in Byzantine Asynchronous Systems Hammurabi Mendes, Christine Tasson, Maurice Herlihy |
| 11:45-12:05 | Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
Are Lock-Free Concurrent Algorithms Practically Wait-Free? Dan Alistarh, Keren Censor-Hillel, Nir Shavit |
| 12:05-1:45 | Lunch (on your own) | |
| Session 11A Chair: Nikhil Bansal Location: Grand Ballroom |
Session 11B Chair: Mark Braverman Location: Crystal Ballroom | |
| 1:45-2:05 | Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds Ankit Sharma, Jan Vondrak |
Every list-decodable code for high noise has abundant near-optimal rate puncturings Atri Rudra, Mary Wootters |
| 2:10-2:30 | Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein |
Non-malleable Codes from Additive Combinatorics Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett |
| 2:35-2:55 | Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing Zachary Friggstad, Chaitanya Swamy |
Breaking the quadratic barrier for 3 LCC's over the Reals Zeev Dvir, Shubhangi Saraf, Avi Wigderson |
| 3:00-3:20 | Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements Alina Ene, Ali Vakilian |
Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan |
| 3:20-3:50 | Coffee Break | |
| Session 12A Chair: David Shmoys Location: Grand Ballroom |
Session 12B Chair: Mark Braverman Location: Crystal Ballroom | |
| 3:50-4:10 | The asymptotic k-SAT threshold Amin Coja-Oghlan |
Communication is bounded by root of rank Shachar Lovett |
| 4:15-4:35 | Satisfiability threshold for random regular NAE-SAT Jian Ding, Allan Sly, Nike Sun |
Communication Lower Bounds via Critical Block Sensitivity Mika Goos, Toniann Pitassi |
| 4:40-5:00 | Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region Andreas Galanis, Daniel Stefankovic, Eric Vigoda |
Computing with a full memory Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman |
| 5:05-5:25 | Efficient deterministic approximate counting for low-degree polynomial threshold functions Anindya De, Rocco A. Servedio |
Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka |