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