Workshops

Fall 2015

Computational Complexity of Low-Polynomial Time Problems

Nov 30, 2015 to Dec 3, 2015

Return to event »

Click on the titles of individual talks for abstract, slides and archived video (available approximately one week after the conclusion of the workshop).

Please note that this schedule is subject to change. All events take place in the Calvin Lab Auditorium.

Monday, November 30th, 2015
8:45 am–9:05 am		Coffee & Check-In
9:05 am–9:15 am		Opening Remarks
9:15 am–10:00 am		Higher Lower Bounds from the 3SUM Conjecture Seth Pettie, University of Michigan
10:00 am–10:45 am		3SUM Hardness of Triangle Enumeration Problems, and their Consequences. Tsvi Kopelovitz, University of Michigan
10:45 am–11:15 am		Break
11:15 am–12:00 pm		Clustered Integer 3SUM via Additive Combinatorics Moshe Lewenstein, Bar-Ilan University
12:00 pm–2:00 pm		Lunch
2:00 pm–2:45 pm		3SUM, 3XOR, Triangles Emanuele Viola, Northeastern University
2:45 pm–3:15 pm		Break
3:15 pm–3:40 pm		The New P Amir Abboud, Stanford University
3:40 pm–5:00 pm		Reception

Tuesday, December 1st, 2015
8:45 am–9:15 am		Coffee & Check-In
9:15 am–10:00 am		Playing with Grammars: What Have We Known So Far! Barna Saha, University of Massachusetts Amherst
10:00 am–10:45 am		Lower Bounds and Open Problems in Streams Raphaël Clifford, University of Bristol
10:45 am–11:15 am		Break
11:15 am–12:00 pm		Optimal Data-Dependent Hashing for Nearest Neighbor Search Alex Andoni, Columbia University
12:00 pm–2:00 pm		Lunch
2:00 pm–2:45 pm		Conditional Lower Bounds for Longest Common Subsequence Karl Bringmann, ETH Zürich
2:45 pm–3:30 pm		Fast Combinatorial 3SUM breaks BMM Kasper Green Larsen, Aarhus University
3:30 pm–4:00 pm		Break
4:00 pm–4:25 pm		Which Regular Expression Patterns are Hard to Match? Arturs Backurs, MIT
4:25 pm–5:00 pm		Rump Session

Wednesday, December 2nd, 2015
8:45 am–9:15 am		Coffee & Check-In
9:15 am–10:00 am		Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter Fabrizio Grandoni, IDSIA, University of Lugano
10:00 am–10:45 am		Upper and Lower Bounds for Graph Problems in Computer Aided Verification Monika Henzinger, University of Vienna
10:45 am–11:15 am		Break
11:15 am–12:00 pm		Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made Amir Abboud, Stanford University
12:00 pm–2:00 pm		Lunch
2:00 pm–2:45 pm		Deterministic APSP, Orthogonal Vectors, and More Ryan Williams, Stanford University
2:45 pm–3:30 pm		Some Emergency Barriers to Worst-Case Dynamic MST Danupon Nanongkai, KTH Royal Institute of Technology
3:30 pm–4:00 pm		Break
4:00 pm–4:25 pm		Algorithmic Uses of SETH-Based Lower Bounds Marvin Künnemann, Max Planck Institut für Informatik
4:25 pm–5:30 pm		Open Problem Session

Thursday, December 3rd, 2015
8:45 am–9:15 am		Coffee & Check-In
9:15 am–10:00 am		Deterministic Edge Connectivity in Near-Linear Time Mikkel Thorup, University of Copenhagen
10:00 am–10:45 am		Finding k Simple Shortest Paths and Cycles Vijaya Ramachandran, University of Texas at Austin
10:45 am–11:15 am		Break
11:15 am–12:00 pm		Light Spanners Shiri Chechik, Tel-Aviv University
12:00 pm–2:00 pm		Lunch
2:00 pm–2:45 pm		Input Sparsity and Hardness for Linear Algebra Problems David Woodruff, IBM Almaden
2:45 pm–3:10 pm		ETH Hardness for Densest-k-Subgraph with Perfect Completeness Aviad Rubinstein, UC Berkeley
3:10 pm–3:35 pm		Subquadratic Algorithms for Succinct Stable Matching Daniel Moeller, UC San Diego
3:35 pm–4:05 pm		Break
4:05 pm–4:30 pm		Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs Josh Wang, Stanford University
4:30 pm–4:55 pm		Orthogonal Vectors is Hard for First-Order Properties on Sparse Graphs Jiawei Gao, UC San Diego