STOC 2014: 46th Annual Symposium on the Theory of Computing

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