Conference Program
Sunday June 14, 2015
Workshop and Tutorials  
9:005:30 
9:005:00 Location: E141142 Algorithmic Frontiers of Modern Massively Parallel Computation Organizers: Ashish Goel, Sergei Vassilvistskii, Grigory Yaroslavtsev 
11:205:30 Location: E143144 Tutorial: Hardness and Equivalences in P Organizers: Amir Abboud, Arturs Backurs, Piotr Indyk, Virginia V. Williams 
2:005:30 Location: D133D134 Tutorial: Sampling and Volume Computation in High Dimension Organizer: Santosh Vempala 
Note: Sunday meals are not part of STOC registration  
6:007:15  Turing Award Lecture: Michael Stonebraker (Hall A)  
7:309:30  Welcome Reception (Portland 251) 
Monday June 15, 2015
Continental Breakfast in lobby outside Portland 2523  
Session 1A Chair: Udi Wieder Location: Portland 252 
Session 1B Chair: Chris Umans Location: Portland 253  
8:359:00 
Approximate Distance Oracles with Improved Bounds
Shiri Chechik (TelAviv University) 
Proof of the Satisfiability Conjecture for Large k
Jian Ding (University of Chicago), Allan Sly (UC Berkeley and Australian National University), Nike Sun (Microsoft Research and MIT) 
9:009:25 
The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
Jakub Lacki (University of Warsaw), Jakub Ocwieja (University of Warsaw), Marcin Pilipczuk (University of Warwick and Unviersity of Warsaw), Piotr Sankowski (Univerisity of Warsaw), Anna Zych (University of Warsaw) 
Consistency Thresholds for the Planted Bisection Model
Elchanan Mossel (U.C. Berkeley and University of Pennsylvania) , Joe Neeman (U.T. Austin), Allan Sly (U.C. Berkeley and Australian National University) 
9:259:50 
Unifying and Strengthening Hardness for Dynamic Problems via the Online MatrixVector Multiplication Conjecture
Monika Henzinger (University of Vienna, Austria), Sebastian Krinninger (University of Vienna, Austria), Danupon Nanongkai (KTH Royal Institute of Technology), Thatchaphol Saranurak (KTH Royal Institute of Technology) 
On the Complexity of Random Satisfiability Problems with Planted Solutions
Vitaly Feldman (IBM Research  Almaden), Will Perkins (University of Birmingham), Santosh Vempala (Georgia Tech) 
9:5010:15 
Clustered Integer 3SUM via Additive Combinatorics
Timothy M. Chan (University of Waterloo), Moshe Lewenstein (BarIlan University) 
Sumofsquares Lower Bounds for Planted Clique
Raghu Meka (UCLA), Aaron Potechin (MIT), Avi Wigderson (IAS) 
10:1510:40 
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Amir Abboud (Stanford), Virginia Vassilevska Williams (Stanford), Huacheng Yu (Stanford) 
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak (Microsoft Research), Pravesh Kothari (University of Texas at Austin), Siu On Chan (Microsoft Research) 
10:4011:00 
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Arturs Backurs (MIT) and Piotr Indyk (MIT) 
Inapproximability of Combinatorial Problems via Small LPs and SDPs
Gábor Braun (Georgia Tech), Sebastian Pokutta (Georgia Tech), Daniel Zink (Georgia Tech) 
11:0011:20  Coffee Break  
11:2012:30  FCRC Keynote Session: Andrew Yao (Hall A)  
12:301:55  Lunch  
Session 2A Chair: Ilias Diakonikolas Location: Portland 252 
Session 2B Chair: Krzysztof Onak Location: Portland 253  
1:552:20 
Preserving Statistical Validity in Adaptive Data Analysis
Cynthia Dwork (Microsoft Research), Vitaly Feldman (IBM Research  Almaden), Moritz Hardt (IBM Research  Almaden), Toniann Pitassi (University of Toronto), Omer Reingold, Aaron Roth (University of Pennsylvania) 
Randomized Composable Coresets for Distributed Submodular Maximization
Vahab Mirrokni (Google Research New York), Morteza Zadimoghaddam (Google Research New York) 
2:202:45 
Local, Private, Efficient Protocols for Succinct Histograms
Raef Bassily (The Pennsylvania State University), Adam Smith (The Pennsylvania State University) 
Dimensionality Reduction for kMeans Clustering and Low Rank Approximation
Michael B. Cohen (MIT), Sam Elder (MIT), Cameron Musco (MIT), Christopher Musco (MIT), Madalina Persu (MIT) 
2:453:10 
Improved Noisy Population Recovery, and Reverse BonamiBeckner Inequality for Sparse Functions
Shachar Lovett (University of California, San Diego), Jiapeng Zhang (University of California, San Diego) 
Space and TimeEfficient Algorithm for Maintaining Dense Subgraphs on OnePass Dynamic Streams
Sayan Bhattacharya (The Institute of Mathematical Sciences, Chennai, India), Monika Henzinger (University of Vienna), Danupon Nanongkai (KTH Royal Institute of Technology), Charalampos E. Tsourakakis (Harvard University) 
3:103:30 
Dictionary Learning and Tensor Decomposition via the SumofSquares Method
Boaz Barak (Microsoft Research), Jonathan Kelner (MIT), David Steurer (Cornell University) 
L_{p} Row Sampling by Lewis Weights
Michael B. Cohen (MIT) and Richard Peng (MIT) 
3:304:00  Coffee Break  
Session 3A Chair: Sanjeev Khanna Location: Portland 252 
Session 3B Chair: Michael Forbes Location: Portland 253  
4:004:25 
On the Lovász Theta function for Independent Sets in Sparse Graphs
Nikhil Bansal (TU Eindhoven), Anupam Gupta (CMU), Guru Guruganesh (CMU) 
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract
Pravesh K. Kothari (The University of Texas at Austin), Raghu Meka (University of California Los Angeles) 
4:254:50 
The Complexity of the Simplex Method
John Fearnley (University of Liverpool), Rahul Savani (University of Liverpool) 
Rectangles Are Nonnegative Juntas
Mika Gö,ös (University of Toronto), Shachar Lovett (University of California, San Diego), Raghu Meka (University of California, Los Angeles), Thomas Watson (University of Toronto), David Zuckerman (University of Texas at Austin) 
4:505:15 
An Improved Version of the RandomFacet Pivoting Rule for the Simplex Algorithm
Thomas Dueholm Hansen (Stanford University), Uri Zwick (Tel Aviv University) 
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
Irit Dinur (Weizman Institute), Prahladh Harsha (TIFR), Guy Kindler (Hebrew University) 
5:155:40 
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete kpartite Graphs
Shuchi Chawla (University of WisconsinMadison), Konstantin Makarychev (Microsoft Research), Tselil Schramm (UC Berkeley), Grigory Yaroslavtsev (University of Pennsylvania) 
The List Decoding Radius of ReedMuller Codes over Small Fields
Abhishek Bhowmick (University of Texas at Austin) and Shachar Lovett (University of California, San Diego) 
5:406:05 
NearlyLinear Time Positive LP Solver with Faster Convergence Rate
Zeyuan AllenZhu (MIT), Lorenzo Orecchia (Boston University) 
A Characterization of the Capacity of Online (Causal) Binary Channels
Zitan Chen (The Chinese University of Hong Kong), Sidharth Jaggi (The Chinese University of Hong Kong), Michael Langberg (SUNY at Buffalo) 
6:056:25 
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Zeyuan AllenZhu (MIT), Zhenyu Liao (Boston University), Lorenzo Orecchia (Boston University) 
ReedMuller Codes for Random Erasures and Errors
Emmanuel Abbe (Princeton University), Amir Shpilka (TelAviv University), Avi Wigderson (IAS, Princeton). 
9:00pm  Business Meeting (Location: Portland 252) 
Tuesday June 16, 2015
Session 4A Chair: Ben Reichardt Location: Portland 252 
Session 4B Chair: Yaron Singer Location: Portland 253  
8:359:00 
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Scott Aaronson (MIT) and Andris Ambainis (University of Latvia) 
Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
Siddharth Barma (California Institute of Technology) 
9:009:25 
Quantum Information Complexity
Dave Touchette (Université de Montréal) 
Approximating the Nash Social Welfare with Indivisible Items
Richard Cole (New York University) and Vasilis Gkatzelis (Stanford University) 
9:259:50 
Sparse Quantum Codes from Quantum Circuits
Dave Bacon (University of Washington and Google), Steven T. Flammia (U Sydney), Aram W. Harrow (MIT), Jonathan Shi (Cornell) 
On the Complexity of Nash Equilibria in Anonymous Games
Xi Chen (Columbia University), David Durfee (Georgia Institute of Technology), Anthi Orfanou (Columbia University) 
9:5010:15 
Small Value Parallel Repetition for General Games
Mark Braverman (Princeton University), Ankit Garg (Princeton University). 
Hardness of Graph Pricing Through Generalized MaxDicut
Euiwoong Lee (Carnegie Mellon) 
10:1510:40 
An Interactive Information Odometer and Applications
Mark Braverman (Princeton University) and Omri Weinstein (Princeton University) 
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Amit Daniely (Hebrew University), Michael Schapira (Hebrew University), Gal Shahaf (Hebrew University) 
10:4011:00 
The Communication Complexity of Interleaved Group Products
W. T. Gowers (University of Cambridge), Emanuele Viola (Northeastern & Harvard) 
Inapproximability of Nash Equilibrium
Aviad Rubinstein (UC Berkeley) 
11:0011:20  Coffee Break  
11:2012:30  FCRC Keynote Session: Olivier Temam (Hall A)  
12:301:55  Lunch 
Session 5A Chair: Yael Kalai Location: Portland 252 
Session 5B Chair: Mary Wootters Location: Portland 253  
1:552:20 
Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
Venkata Koppula (University of Texas at Austin), Allison B. Lewko (Columbia University), Brent Waters (University of Texas at Austin) Succinct Garbling and Indistinguishability Obfuscation for RAM Programs Ran Canetti (TelAviv University and Boston University), Justin Holmgren (MIT), Abhishek Jain (Johns Hopkins), Vinod Vaikuntanathan (MIT) Succinct Randomized Encodings and their Applications Nir Bitansky (MIT), Sanjam Garg (University of California, Berkeley), Huijia Lin (University of California, Santa Barbara), Rafael Pass (Cornell University), Sidharth Telang (Cornell University) 
Sketching and Embedding are Equivalent for Norms
Alexandr Andoni (Simons Institute), Robert Krauthgamer (Weizmann Institute of Science), Ilya Razenshteyn (MIT) 
2:202:45 
Garbled RAM From OneWay Functions
Sanjam Garg (UC Berkeley), Steve Lu (UCLA), Rafail Ostrovsky (UCLA), Alessandra Scafuro (Boston University and Northeastern University) 
Prioritized Metric Structures and Embedding
Michael Elkin (BenGurion University of the Negev), Arnold Filtser (BenGurion University of the Negev), Neiman Ofer (BenGurion University of the Negev) 
2:453:10 
Nonmalleable Reductions and Applications
Divesh Aggarwal (EPFL), Yevgeniy Dodis (NYU), Tomasz Kazana (University of Warsaw), Maciej Obremski (University of Warsaw) 
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space
Jean Bourgain (IAS), Sjoerd Dirksen (RWTH Aachen University), Jelani Nelson (Harvard) 
3:103:30 
Leveled Fully Homomorphic Signatures from Standard Lattices
Sergey Gorbunov (MIT), Vinod Vaikuntanathan (MIT), Daniel Wichs (Northeastern) 
A Directed Isoperimetric Inequality with Application to Bregman Near Neighbor Lower Bounds
Amirali Abdullah (University of Utah), Suresh Venkatasubramanian (University of Utah) 
3:303:55  Coffee Break  
Session 6A Chair: Elena Grigorescu Location: Portland 252 
Session 6B Chair: Costis Daskalakis Location: Portland 253  
3:554:20 
Boolean Function Monotonicity Testing Requires (Almost) n^{1/2} Nonadaptive Queries
Xi Chen (Columbia University), Anindya De (IAS/DIMACS), Rocco A. Servedio (Columbia University), LiYang Tan (Columbia University/Simons Institute) 
Bypassing KLS: Gaussian Cooling and an O*(n^{3}) Volume Algorithm
Ben Cousins (Georgia Tech), Santosh Vempala (Georgia Tech) 
4:204:40 
Quantum Spectrum Testing
Ryan O'Donnell (Carnegie Mellon University), John Wright (Carnegie Mellon University)  FPTAS for #BIS with Degree Bounds on One Side Jingcheng Liu (UC Berkeley), Pinyan Lu (Microsoft Research) 
4:405:00  Break 
5:006:15 
Session 7 Chair: Ronitt Rubinfeld Location: Portland 251/257/258 

5:00pm5:25pm 
Exponential Separation of Information and Communication for Boolean Functions
Anat Ganor (Weizmann Institute), Gillat Kol (IAS), Ran Raz (Weizmann Institute & IAS)  
5:25pm5:50pm 
Lower Bounds on the Size of Semidefinite Programming Relaxations
James R. Lee (University of Washington), Prasad Raghavendra (UC Berkeley), David Steurer (Cornell)  
5:50pm6:15pm 
2Server PIR with SubPolynomial Communication
Zeev Dvir (Princeton University) and Sivakanth Gopi (Princeton University) 

6:157:30  Knuth Prize Lecture: László Babai (Portland 251/7/8) 
Wednesday June 17, 2015
Session 8A Chair: Udi Wieder Location: Portland 252 
Session 8B Chair: Sanjeev Khanna Location: Portland 253  
8:359:00 
Fast Matrix Multiplication: Limitations of the CoppersmithWinograd Method
Andris Ambainis (University of Latvia), Yuval Filmus (Institute for Advanced Study), François Le Gall (University of Tokyo) 
Excluded Grid Theorem: Improved and Simplified
Julia Chuzhoy (Toyota Technological Institute at Chicago) 
9:009:25 
High Parallel Complexity Graphs and MemoryHard Functions
Joël Alwen (IST Austria), Vladimir Serbinenko (Google Zürich) 
The Directed Grid Theorem
Kenichi Kawarabayashi (National Institute of Informatics and JST ERATO) and Stephan Kreutzer (Technical University Berlin) 
9:259:50 
Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity
Ittai Abraham (VMware Research), Danny Dolev (Hebrew University) 
Deterministic Global Minimum Cut of a Simple Graph in NearLinear Time
Kenichi Kawarabayashi (National Institute of Informatics, Tokyo, Japan) and Mikkel Thorup (University of Copenhagen, Denmark) 
9:5010:15 
TestandSet in Optimal Space
George Giakkoupis (INRIA Rennes), Maryam Helmi (University of Calgary), Lisa Higham (University of Calgary), Philipp Woelfel (University of Calgary) 
Beyond the Euler Characteristic: Approximating the Genus of General Graphs
Kenichi Kawarabayashi (National Institute of Informatics, Japan), Anastasios Sidiropoulos (The Ohio State University) 
10:1510:40 
Adjacency Labeling Schemes and InducedUniversal Graphs
Stephen Alstrup (University of Copenhagen), Haim Kaplan (Tel Aviv University), Mikkel Thorup (University of Copenhagen), Uri Zwick (TelAviv University) 
Computing with Tangles
Martin Grohe (RWTH Aachen University) and Pascal Schweitzer (RWTH Aachen University) 
10:4011:00 
How Well Can Graphs Represent Wireless Interference?
Magnus M. Halldorsson (Reykjavik University) and Tigran Tonoyan (Reykjavik University) 
Faster Canonical Forms for Primitive Coherent Configurations
John Wilmes (University of Chicago) and Xiaorui Sun (Columbia University) 
11:0011:20  Coffee Break  
11:2012:30  FCRC Keynote Session: Don Syme (Hall A)  
12:301:55  Lunch  
Session 9A Chair: Elena Grigorescu Location: Portland 252 
Session 9B Chair: Ilias Diakonikolas Location: Portland 253  
1:552:20 
Random Permutations using Switching Networks
Artur Czumaj (University of Warwick) 
Learning Arbitrary Statistical Mixtures of Discrete Distributions
Jian Li (Tsinghua University), Yuval Rabani (The Hebrew University), Leonard J. Schulman (California Institute of Technology), Chaitanya Swamy (University of Waterloo) 
2:202:45 
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
Anand Louis (Princeton University) 
Tight Bounds for Learning a Mixture of Two Gaussians
Moritz Hardt (IBM Research Almaden), Eric Price (The University of Texas at Austin) 
2:453:10 
Testing Cluster Structure of Graphs
Artur Czumaj (University of Warwick), Pan Peng (TU Dortmund and Chinese Academy of Sciences), Christian Sohler (TU Dortmund) 
Learning Mixtures of Gaussians in High Dimensions
Rong Ge (Microsoft Research New England), Qingqing Huang (MIT), Sham M. Kakade (Microsoft Research New England) 
3:103:30 
Solving the Shortest Vector Problem in 2^{n} Time Using Discrete Gaussian Sampling
Divesh Aggarwal (École polytechnique fédérale de Lausanne), Daniel Dadush (Centrum Wiskunde & Informatica), Oded Regev (New York University), Noah StephensDavidowitz (New York University) 
Efficiently Learning Ising Models on Arbitrary Graphs
Guy Bresler (MIT) 
3:304:00  Coffee Break  
Session 10A Chair: Mary Wootters Location: Portland 252 
Session 10B Chair: Shaddin Dughmi Location: Portland 253  
4:004:25 
Approximate kflat Nearest Neighbor Search
Wolfgang Mulzer (FU Berlin), Huy L. Nguyen (Simons Institute), Paul Seiferth (FU Berlin), Yannik Stein (FU Berlin) 
A Polynomialtime Bicriteria Approximation Scheme for Planar Bisection
Kyle Fox (Duke University), Philip N. Klein (Brown University), Shay Mozes (Interdisciplinary Center, Herzliya, Israel) 
4:254:50 
Optimal DataDependent Hashing for Approximate Near Neighbors
Alexandr Andoni (Simons Institute) and Ilya Razenshteyn (MIT) 
Minimizing FlowTime on Unrelated Machines
Nikhil Bansal (Eindhoven University of Technology, Netherlands), Janardhan Kulkarni (Duke University) 
4:505:15 
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
Kasper Green Larsen (Aarhus University), Jelani Nelson (Harvard University), Huy Le Nguyen (Simons Institute) 
Randomized Rounding for the Largest Simplex Problem
Aleksandar Nikolov (Microsoft Research) 
5:155:40 
From Independence to Expansion and Back Again
Tobias Christiani (IT University of Copenhagen), Rasmus Pagh (IT University of Copenhagen), Mikkel Thorup (University of Copenhagen) 
Greedy Algorithms for Steiner Forest
Anupam Gupta (Carnegie Mellon University) and Amit Kumar (IIT Delhi) 
5:406:05 
Superresolution, Extremal Functions and the Condition Number of Vandermonde Matrices
Ankur Moitra (MIT) 
Secretary Problems with NonUniform Arrival Order
Thomas Kesselheim (MaxPlanckInstitut fur Informatik), Robert Kleinberg (Cornell University and Microsoft Research), Rad Niazadeh (Cornell University) 
6:056:25 
Analysis of a Classical Matrix Preconditioning Algorithm
Leonard J. Schulman (Caltech), Alistair Sinclair (UC Berkeley) 
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
Nitish Korula (Google Research), Vahab Mirrokni (Google Research), Morteza Zadimoghaddam (Google Research) 