Conference Program

Sunday June 14, 2015

	Workshop and Tutorials
9:00-5:30	9:00-5:00 Location: E141-142 Algorithmic Frontiers of Modern Massively Parallel Computation Organizers: Ashish Goel, Sergei Vassilvistskii, Grigory Yaroslavtsev	11:20-5:30 Location: E143-144 Tutorial: Hardness and Equivalences in P Organizers: Amir Abboud, Arturs Backurs, Piotr Indyk, Virginia V. Williams	2:00-5:30 Location: D133-D134 Tutorial: Sampling and Volume Computation in High Dimension Organizer: Santosh Vempala
	Note: Sunday meals are not part of STOC registration
6:00-7:15	Turing Award Lecture: Michael Stonebraker (Hall A)
7:30-9:30	Welcome Reception (Portland 251)

Monday June 15, 2015

	Continental Breakfast in lobby outside Portland 252-3
	Session 1A Chair: Udi Wieder Location: Portland 252	Session 1B Chair: Chris Umans Location: Portland 253
8:35-9:00	Approximate Distance Oracles with Improved Bounds Shiri Chechik (Tel-Aviv 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:00-9: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:25-9:50	Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector 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:50-10:15	Clustered Integer 3SUM via Additive Combinatorics Timothy M. Chan (University of Waterloo), Moshe Lewenstein (Bar-Ilan University)	Sum-of-squares Lower Bounds for Planted Clique Raghu Meka (UCLA), Aaron Potechin (MIT), Avi Wigderson (IAS)
10:15-10: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:40-11: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:00-11:20	Coffee Break
11:20-12:30	FCRC Keynote Session: Andrew Yao (Hall A)
12:30-1:55	Lunch
	Session 2A Chair: Ilias Diakonikolas Location: Portland 252	Session 2B Chair: Krzysztof Onak Location: Portland 253
1:55-2: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 Core-sets for Distributed Submodular Maximization Vahab Mirrokni (Google Research New York), Morteza Zadimoghaddam (Google Research New York)
2:20-2:45	Local, Private, Efficient Protocols for Succinct Histograms Raef Bassily (The Pennsylvania State University), Adam Smith (The Pennsylvania State University)	Dimensionality Reduction for k-Means Clustering and Low Rank Approximation Michael B. Cohen (MIT), Sam Elder (MIT), Cameron Musco (MIT), Christopher Musco (MIT), Madalina Persu (MIT)
2:45-3:10	Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions Shachar Lovett (University of California, San Diego), Jiapeng Zhang (University of California, San Diego)	Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass 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:10-3:30	Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method Boaz Barak (Microsoft Research), Jonathan Kelner (MIT), David Steurer (Cornell University)	Lp Row Sampling by Lewis Weights Michael B. Cohen (MIT) and Richard Peng (MIT)
3:30-4:00	Coffee Break
	Session 3A Chair: Sanjeev Khanna Location: Portland 252	Session 3B Chair: Michael Forbes Location: Portland 253
4:00-4: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:25-4: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:50-5:15	An Improved Version of the Random-Facet 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:15-5:40	Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs Shuchi Chawla (University of Wisconsin-Madison), Konstantin Makarychev (Microsoft Research), Tselil Schramm (UC Berkeley), Grigory Yaroslavtsev (University of Pennsylvania)	The List Decoding Radius of Reed-Muller Codes over Small Fields Abhishek Bhowmick (University of Texas at Austin) and Shachar Lovett (University of California, San Diego)
5:40-6:05	Nearly-Linear Time Positive LP Solver with Faster Convergence Rate Zeyuan Allen-Zhu (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:05-6:25	Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates Zeyuan Allen-Zhu (MIT), Zhenyu Liao (Boston University), Lorenzo Orecchia (Boston University)	Reed-Muller Codes for Random Erasures and Errors Emmanuel Abbe (Princeton University), Amir Shpilka (Tel-Aviv 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:35-9: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:00-9: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:25-9: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:50-10:15	Small Value Parallel Repetition for General Games Mark Braverman (Princeton University), Ankit Garg (Princeton University).	Hardness of Graph Pricing Through Generalized Max-Dicut Euiwoong Lee (Carnegie Mellon)
10:15-10: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:40-11: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:00-11:20	Coffee Break
11:20-12:30	FCRC Keynote Session: Olivier Temam (Hall A)
12:30-1:55	Lunch

	Session 5A Chair: Yael Kalai Location: Portland 252	Session 5B Chair: Mary Wootters Location: Portland 253
1:55-2: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 (Tel-Aviv 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:20-2:45	Garbled RAM From One-Way 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 (Ben-Gurion University of the Negev), Arnold Filtser (Ben-Gurion University of the Negev), Neiman Ofer (Ben-Gurion University of the Negev)
2:45-3:10	Non-malleable 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:10-3: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:30-3:55	Coffee Break
	Session 6A Chair: Elena Grigorescu Location: Portland 252	Session 6B Chair: Costis Daskalakis Location: Portland 253
3:55-4:20	Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries Xi Chen (Columbia University), Anindya De (IAS/DIMACS), Rocco A. Servedio (Columbia University), Li-Yang Tan (Columbia University/Simons Institute)	Bypassing KLS: Gaussian Cooling and an O*(n3) Volume Algorithm Ben Cousins (Georgia Tech), Santosh Vempala (Georgia Tech)
4:20-4: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:40-5:00	Break

5:00-6:15	Session 7 Chair: Ronitt Rubinfeld Location: Portland 251/257/258
5:00pm-5:25pm	Exponential Separation of Information and Communication for Boolean Functions Anat Ganor (Weizmann Institute), Gillat Kol (IAS), Ran Raz (Weizmann Institute & IAS)
5:25pm-5:50pm	Lower Bounds on the Size of Semidefinite Programming Relaxations James R. Lee (University of Washington), Prasad Raghavendra (UC Berkeley), David Steurer (Cornell)
5:50pm-6:15pm	2-Server PIR with Sub-Polynomial Communication Zeev Dvir (Princeton University) and Sivakanth Gopi (Princeton University)
6:15-7: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:35-9:00	Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd 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:00-9:25	High Parallel Complexity Graphs and Memory-Hard Functions Joël Alwen (IST Austria), Vladimir Serbinenko (Google Zürich)	The Directed Grid Theorem Ken-ichi Kawarabayashi (National Institute of Informatics and JST ERATO) and Stephan Kreutzer (Technical University Berlin)
9:25-9: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 Near-Linear Time Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo, Japan) and Mikkel Thorup (University of Copenhagen, Denmark)
9:50-10:15	Test-and-Set 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 Ken-ichi Kawarabayashi (National Institute of Informatics, Japan), Anastasios Sidiropoulos (The Ohio State University)
10:15-10:40	Adjacency Labeling Schemes and Induced-Universal Graphs Stephen Alstrup (University of Copenhagen), Haim Kaplan (Tel Aviv University), Mikkel Thorup (University of Copenhagen), Uri Zwick (Tel-Aviv University)	Computing with Tangles Martin Grohe (RWTH Aachen University) and Pascal Schweitzer (RWTH Aachen University)
10:40-11: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:00-11:20	Coffee Break
11:20-12:30	FCRC Keynote Session: Don Syme (Hall A)
12:30-1:55	Lunch
	Session 9A Chair: Elena Grigorescu Location: Portland 252	Session 9B Chair: Ilias Diakonikolas Location: Portland 253
1:55-2: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:20-2: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:45-3: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:10-3:30	Solving the Shortest Vector Problem in 2n 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 Stephens-Davidowitz (New York University)	Efficiently Learning Ising Models on Arbitrary Graphs Guy Bresler (MIT)
3:30-4:00	Coffee Break
	Session 10A Chair: Mary Wootters Location: Portland 252	Session 10B Chair: Shaddin Dughmi Location: Portland 253
4:00-4:25	Approximate k-flat Nearest Neighbor Search Wolfgang Mulzer (FU Berlin), Huy L. Nguyen (Simons Institute), Paul Seiferth (FU Berlin), Yannik Stein (FU Berlin)	A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection Kyle Fox (Duke University), Philip N. Klein (Brown University), Shay Mozes (Interdisciplinary Center, Herzliya, Israel)
4:25-4:50	Optimal Data-Dependent Hashing for Approximate Near Neighbors Alexandr Andoni (Simons Institute) and Ilya Razenshteyn (MIT)	Minimizing Flow-Time on Unrelated Machines Nikhil Bansal (Eindhoven University of Technology, Netherlands), Janardhan Kulkarni (Duke University)
4:50-5: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:15-5: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:40-6:05	Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices Ankur Moitra (MIT)	Secretary Problems with Non-Uniform Arrival Order Thomas Kesselheim (Max-Planck-Institut fur Informatik), Robert Kleinberg (Cornell University and Microsoft Research), Rad Niazadeh (Cornell University)
6:05-6: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)