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

ETH Hardness for Densest-k-Subgraph with Perfect Completeness

Aviad Rubinstein, UC Berkeley
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/aviad-rubinstein-2015-12-03
Visit talk page
0:20:42

Subquadratic Algorithms for Succinct Stable Matching

Daniel Moeller, UC San Diego
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/daniel-moeller-2015-12-03
Visit talk page
0:26:50

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

Josh Wang, Stanford University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/josh-wang-2015-12-03
Visit talk page
0:22:43

Orthogonal Vectors is Hard for First-Order Properties on Sparse Graphs

Jiawei Gao, UC San Diego
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/jaiwei-gao-2015-12-03
Visit talk page