
Videos from Workshops
Playlist: 24 videos
Computational Complexity of Low-Polynomial Time Problems
Nov. 30 – Dec. 3, 2015
Despite the widely demonstrated usefulness of the notion of NP-hardness, there are many situations in which it is not applicable. This is the case, for example, when the goal is to show hardness of problems that are known to...
Videos from Workshops Talks
0:39:58
Clustered Integer 3SUM via Additive Combinatorics
Moshe Lewenstein, Bar-Ilan University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/moshe-lewenstein-2015-11-30
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/moshe-lewenstein-2015-11-30
0:47:41
Higher Lower Bounds from the 3SUM Conjecture
Seth Pettie, University of Michigan
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/seth-pettie-2015-11-30
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/seth-pettie-2015-11-30
0:38:8
3SUM Hardness of Triangle Enumeration Problems, and their Consequences.
Tsvi Kopelovitz, University of Michigan
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/tsvi-kopelovitz-2015-11-30
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/tsvi-kopelovitz-2015-11-30
0:45:42
Playing with Grammars: What Have We Known So Far!
Barna Saha, University of Massachusetts Amherst
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/barna-saha-2015-12-01
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/barna-saha-2015-12-01
0:43:6
3SUM, 3XOR, Triangles
Emanuele Viola, Northeastern University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/emanuele-viola-2015-11-30
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/emanuele-viola-2015-11-30
0:39:38
Lower Bounds and Open Problems in Streams
Raphaël Clifford, University of Bristol
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/raphael-clifford-2015-12-01
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/raphael-clifford-2015-12-01
0:21:19
The New P
Amir Abboud, Stanford University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/amir-abboud-2015-11-30
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/amir-abboud-2015-11-30
0:23:27
Which Regular Expression Patterns are Hard to Match?
Arturs Backurs, Massachusetts Institute of Technology
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/arturs-backurs-2015-12-01
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/arturs-backurs-2015-12-01
0:41:5
Conditional Lower Bounds for Longest Common Subsequence
Karl Bringmann, ETH Zürich
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/conditional-lower-bounds-longest-common-subsequence
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/conditional-lower-bounds-longest-common-subsequence
0:49:9
Optimal Data-Dependent Hashing for Nearest Neighbor Search
Alex Andoni, Columbia University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/alex-andoni-2015-12-01
Visit talk page
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/alex-andoni-2015-12-01