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

Remote video URL
0:47:41
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
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:39:58
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:43:6
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:21:19
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:45:42
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:39:38
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:49:9
Alex Andoni, Columbia University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/alex-andoni-2015-12-01
Visit talk page
Remote video URL
0:41:5
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:39:45
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