sum of squares lower bounds versus low-degree polynomial lower bounds
Published Streamed 2 years ago • 442 plays • Length 29:06Download video MP4
Download video MP3
Similar videos
-
30:31
sum of squares lower bounds for refuting any csp
-
1:01:45
sum-of-squares lower bound for statistical problems
-
36:46
approximate degree and quantum query lower bounds via dual polynomials
-
1:02:23
pseudocalibration and sos lower bounds
-
34:05
lower bounds against non-commutative models of algebraic computation
-
1:00:16
lower bounds in complexity theory, communication complexity, and sunflowers - toniann pitassi
-
16:56
probabalistically checkable proofs and the graph coloring problem - dor minzer
-
3:22
sum of squares visual proofs: from level 1 to level 5
-
26:50
a polynomial degree bound on equations for non-rigid matrices and small linear circuits
-
1:07:06
explicit sum-of-squares lower bounds via the polynomial method
-
26:59
lower bounds on non-adaptive data structures maintaining sets of numbers, from sunflowers
-
1:03:14
time-space lower bounds for learning ii
-
33:06
lower bounds for subexponential parameterized complexity of minimum fill-in and related problems
-
17:26
lower bounds by birkhoff interpolation
-
55:20
lower bounds against pc with extension variables
-
1:02:22
lower bounds techniques in proof complexity ii
-
47:35
unprovability of strong complexity lower bounds in bounded arithmetic
-
11:26
understanding statistical-to-computational gaps via low-degree polynomials
-
28:34
chebyshev polynomials, moment matching and optimal estimation of the unseen
-
1:00:00
lower bounds in arithmetic circuit complexity ii
-
40:06
exponential lower bounds on spectrahedral representations of hyperbolicity cones
-
57:18
chasing lower bounds