Conference Program
Saturday May 31, 2014
Workshops (at Columbia University)  
9:455: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:009: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:559:15  Fingerprinting Codes and the Price of Approximate Differential Privacy Mark Bun, Jonathan Ullman, Salil Vadhan 
Rounding SumofSquares Relaxations Boaz Barak, Jonathan A. Kelner, David Steurer 
9:209:40  Analyze Gauss: Optimal Bounds for PrivacyPreserving 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:4510: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:0510:30  Coffee Break  
Session 2A Chair: Gregory Valiant Location: Grand Ballroom 
Session 2B Chair: Chris Umans Location: Crystal Ballroom  
10:3010:50  Polynomial Bounds for the GridMinor Theorem Chandra Chekuri, Julia Chuzhoy 
Pseudorandom generators with optimal seed length for nonboolean polysize circuits Sergei Artemenko, Ronen Shaltiel 
10:5511:15  An Excluded HalfIntegral Grid Theorem for Digraphs and the Directed Disjoint Paths Problem Kenichi Kawarabayashi, Yusuke Kobayashi, Stephan Kreutzer 
On Derandomizing Algorithms that Err Extremely Rarely Oded Goldreich, Avi Wigderson 
11:2011:40  Cops, Robbers, and Threatening Skeletons: Padded Decomposition for MinorFree Graphs Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar 
Superpolynomial lower bounds for depth4 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:4512:05  Deciding firstorder 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 fanin Mrinal Kumar, Shubhangi Saraf 
A superpolynomial lower bound for regular arithmetic formulas Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi 

12:051:25  Lunch (on your own)  
Session 3A Chair: Ronitt Rubinfeld Location: Grand Ballroom 
Session 3B Chair: Adam Smith Location: Crystal Ballroom  
1:301:50  A Characterization of Locally Testable AffineInvariant Properties via Decomposition Theorems Yuichi Yoshida 
New algorithms and lower bounds for circuits with linear threshold gates Ryan Williams 
1:552:15  L_{p}Testing Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev 
Formulas vs. Circuits for Small Distance Connectivity Benjamin Rossman 
2:202: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:453:05  Linear time construction of compressed text indexes in compact space Djamal Belazzougui 
Breaking the MinskyPapert Barrier for ConstantDepth Circuits Alexander A. Sherstov 
3:053:30  Coffee Break  
Session 4A Chair: Brendan Lucier Location: Grand Ballroom 
Session 4B Chair: Thomas Vidick Location: Crystal Ballroom  
3:303:50  Economic Efficiency Requires Interaction Shahar Dobzinski, Noam Nisan, Sigal Oren 
Homological product codes Sergey Bravyi, Matthew Hastings 
3:554: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:204: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:555:15  The matching polytope has exponential extension complexity Thomas Rothvoss 

5:307: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:559:15  Primal Beats Dual on Online Packing LPs in the RandomOrder Model Thomas Kesselheim, Klaus Radke, Andreas Toennis, Berthold Voecking 
An Efficient Parallel Solver for SDD Linear Systems Richard Peng, Daniel A. Spielman 
9:209:40  Competitive Algorithms from Competitive Equilibria: NonClairvoyant Scheduling under Polyhedral Constraints Sungjin Im, Janardhan Kulkarni, Kamesh Munagala 
Solving SDD Linear Systems in Nearly mlog^{1/2}n Time Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup Rao, Shen Chen Xu 
9:4510: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:0510:30  Coffee Break  
Session 6A Chair: Boris Aronov Location: Grand Ballroom 
Session 6B Chair: Vinod Vaikuntanathan Location: Crystal Ballroom  
10:3010:50  From Hierarchical Partitions to Hierarchical Covers: Optimal FaultTolerant Spanners for Doubling Metrics Shay Solomon 
Coin Flipping of Any Constant Bias Implies OneWay Itay Berman, Iftach Haitner, Aris Tentes 
10:5511:15  Shortest Paths on Polyhedral Surfaces and Terrains SiuWing Cheng, Jiongxin Jin 
An Almost OptimallyFair ThreeParty CoinFlipping Protocol Iftach Haitner, Eliad Tsfadia 
11:2011:40  Embedding and Canonizing Graphs of Bounded Genus in Logspace Michael Elberfeld, Kenichi Kawarabayashi 
Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices Carl A. Miller, Yaoyun Shi 
11:4512:05  Testing surface area with arbitrary accuracy Joe Neeman 
Infinite Randomness Expansion with a Constant Number of Devices Matthew Coudron, Henry Yuen 
12:051:45  Lunch (provided at the conference)  
Session 7A Chair: Nikhil Bansal Location: Grand Ballroom 
Session 7B Chair: Adam Smith Location: Crystal Ballroom  
1:452: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:102:30  From average case complexity to improper learning complexity Amit Daniely, Nati Linial, Shai ShalevShwartz 
How to Delegate Computations: The Power of NoSignaling Proofs Yael Tauman Kalai, Ran Raz, Ron D. Rothblum 
2:352: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:003:20  Bandits with Switching Costs: T^{2/3} Regret Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres 
On the Existence of Extractable OneWay Functions Nir Bitansky, Ran Canetti, Omer Paneth, Alon Rosen 
3:253:45  Online learning of local structure via semidefinite programming Paul F. Christiano 
BlackBox NonBlackBox Zero Knowledge Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti 
3:454:15  Coffee Break  
Session 8A Chair: Brendan Lucier Location: Grand Ballroom 
Session 8B Chair: Mikkel Thorup Location: Crystal Ballroom  
4:154:35  Dichotomies in Equilibrium Computation, and Complementary Pivot Algorithms for a New Class of NonSeparable Utility Jugal Garg, Ruta Mehta, Vijay V. Vazirani 
Approximation Algorithms for Bipartite Matching with Metric and Geometric Costs Pankaj K. Agarwal, R. Sharathkumar 
4:405:00  Query Complexity of Approximate Nash Equilibria Yakov Babichenko 
Distributed Approximation Algorithms for Weighted Shortest Paths Danupon Nanongkai 
5:055:25  Constant Rank Bimatrix Games are PPADHard Ruta Mehta 
Parallel Algorithms for Geometric Graph Problems Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev 
8:3010: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:559:15  Fourier PCA and Robust Tensor Decomposition Navin Goyal, Santosh Vempala, Ying Xiao 
Superpolylogarithmic hypergraph coloring hardness via lowdegree long codes Venkatesan Guruswami, Prahladh Harsha, Johan Hastad, Srikanth Srinivasan, Girish Varma 
9:209:40  Smoothed Analysis of Tensor Decompositions Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan 
Analytical Approach to Parallel Repetition Irit Dinur, David Steurer 
9:4510: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:0510:30  Coffee Break  
Session 10A Chair: Ola Svensson Location: Grand Ballroom 
Session 10B Chair: Mikkel Thorup Location: Crystal Ballroom  
10:3010:50  A strongly polynomial algorithm for generalized flow maximization Laszlo A. Vegh 
Zigzag Sort: A Simple Deterministic DataOblivious Sorting Algorithm Running in O(n log n) Time Michael T. Goodrich 
10:5511:15  Approximate Distance Oracles with Constant Query Time Shiri Chechik 
Community detection thresholds and the weak Ramanujan property Laurent Massoulie 
11:2011:40  Faster allpairs shortest paths via circuit complexity Ryan Williams 
Distributed Computability in Byzantine Asynchronous Systems Hammurabi Mendes, Christine Tasson, Maurice Herlihy 
11:4512:05  SublinearTime Decremental Algorithms for SingleSource Reachability and Shortest Paths on Directed Graphs Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai 
Are LockFree Concurrent Algorithms Practically WaitFree? Dan Alistarh, Keren CensorHillel, Nir Shavit 
12:051:45  Lunch (on your own)  
Session 11A Chair: Nikhil Bansal Location: Grand Ballroom 
Session 11B Chair: Mark Braverman Location: Crystal Ballroom  
1:452:05  Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds Ankit Sharma, Jan Vondrak 
Every listdecodable code for high noise has abundant nearoptimal rate puncturings Atri Rudra, Mary Wootters 
2:102:30  Cluster Before You Hallucinate: Approximating NodeCapacitated Network Design and Energy Efficient Routing Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein 
Nonmalleable Codes from Additive Combinatorics Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett 
2:352:55  Approximation Algorithms for RegretBounded Vehicle Routing and Applications to DistanceConstrained Vehicle Routing Zachary Friggstad, Chaitanya Swamy 
Breaking the quadratic barrier for 3 LCC's over the Reals Zeev Dvir, Shubhangi Saraf, Avi Wigderson 
3:003:20  Improved Approximation Algorithms for Degreebounded 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:203:50  Coffee Break  
Session 12A Chair: David Shmoys Location: Grand Ballroom 
Session 12B Chair: Mark Braverman Location: Crystal Ballroom  
3:504:10  The asymptotic kSAT threshold Amin CojaOghlan 
Communication is bounded by root of rank Shachar Lovett 
4:154:35  Satisfiability threshold for random regular NAESAT Jian Ding, Allan Sly, Nike Sun 
Communication Lower Bounds via Critical Block Sensitivity Mika Goos, Toniann Pitassi 
4:405:00  Inapproximability for Antiferromagnetic Spin Systems in the Tree NonUniqueness Region Andreas Galanis, Daniel Stefankovic, Eric Vigoda 
Computing with a full memory Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman 
5:055:25  Efficient deterministic approximate counting for lowdegree polynomial threshold functions Anindya De, Rocco A. Servedio 
Hitting Sets for Multilinear ReadOnce Algebraic Branching Programs, in any Order Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka 