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

Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter

Fabrizio Grandoni, IDSIA, University of Lugano
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/fabrizo-grandoni-2015-12-02
Visit talk page
0:49:32

Upper and Lower Bounds for Graph Problems in Computer Aided Verification

Monika Henzinger, University of Vienna
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/monika-henzinger-2015-12-02
Visit talk page
0:45:24

Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made

Amir Abboud, Stanford University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/amir-abboud-2015-12-02
Visit talk page
0:47:14

Deterministic APSP, Orthogonal Vectors, and More

Ryan Williams, Stanford University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/ryan-williams-2015-12-02
Visit talk page
0:44:51

Some Emergency Barriers to Worst-Case Dynamic MST

Danupon Nanongkai, KTH Royal Institute of Technology
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/danupon-nanongkai-2015-12-02
Visit talk page
0:49:43

Deterministic Edge Connectivity in Near-Linear Time

Mikkel Thorup, University of Copenhagen
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/mikkel-thorup-2015-12-03
Visit talk page
0:50:56

Finding k Simple Shortest Paths and Cycles

Vijaya Ramachandran, University of Texas, Austin
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/vijaya-ramachandran-2015-12-03
Visit talk page
0:39:30

Light Spanners

Shiri Chechik, Tel-Aviv University
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/shiri-chechik-2015-12-03
Visit talk page
0:43:18

Input Sparsity and Hardness for Linear Algebra Problems

David Woodruff, IBM Almaden
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/david-woodruff-2015-12-03
Visit talk page