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

Remote video URL
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
Remote video URL
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
Remote video URL
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
Remote video URL
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
Remote video URL
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
Remote video URL
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
Remote video URL
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
Remote video URL
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
Remote video URL
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
Remote video URL
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