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...

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
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
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
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
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
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
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
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
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
0:39:45

Fast Combinatorial 3SUM breaks BMM

Kasper Green Larsen, Aarhus University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/kasper-larsen-2015-12-01
Visit talk page