Simons Institute for the Theory of Computing

78K subscribers • 6432 videos

The Simons Institute for the Theory of Computing is the world's leading venue for collaborative research in theoretical computer science. Established on July 1, 2012, the Institute is housed in Calvin

Latest Videos

1:05:15 NEW

Revisiting the xor lemma and exponential correlation bounds for polynomials

687 views Today

44:40 NEW

How to construct random strings

464 views Today

1:09:50 NEW

Extractors for samplable sources

496 views Today

1:03:25 NEW

How Haar Is It to Look Random?

1.4K views Yesterday

40:00 NEW

Trading time, space, and alternations: General plasticity for algorithms from hardness of range...

817 views Yesterday

42:30 NEW

Pseudorandomness against AM circuits and new oracle separations

751 views Yesterday

48:54 NEW

The BRRY analysis of the INW generator is optimal

464 views Yesterday

48:48 NEW

Hitting-set generators for low-degree F2-polynomials with almost optimal density

382 views Yesterday

31:12 NEW

Pseudorandom bits for low degree modular polynomials

330 views Yesterday

57:36

Bipartite matching is in NC

1.0K views 2 days ago

1:03:55

The power of subspace designs: Applications in coding theory, pseudorandomness, and beyond

1.8K views 2 days ago

35:36

Simple pseudorandom constructions in algebra

904 views 2 days ago

47:45

On derandomizing the line-point tester

934 views 2 days ago

1:07:16

A survey on PIT for read-once algebraic branching programs

1.2K views 2 days ago

UPCOMING

A survey on lower bounds from derandomization

2 days ago

1:03:50

Targeted samplers

1.3K views 3 days ago

40:40

New directions in catalytic derandomization

544 views 3 days ago

1:06:46

Linear hashing and friends

1.3K views 4 days ago

1:04:45

Spectral approximation of directed graphs and more

1.2K views 4 days ago

46:30

Pseudorandomness, symmetry, smoothing

804 views 4 days ago

44:21

TBD

1.2K views 4 days ago

1:00:10

OpenAI's proof that BPL=L

9.4K views 4 days ago

1:30:10

The Computer in the Sky | Theoretically Speaking

2.7K views 1 week ago

46:21

Apollonian random manifolds and their bass notes

3.0K views 2 weeks ago

49:56

Strong convergence of right-angled Artin groups and spectral gaps of hyperbolic 3-manifolds

1.5K views 2 weeks ago

UPCOMING

tbd

2 weeks ago

UPCOMING

Compressed timestamps and efficient random walks in catalytic space

2 weeks ago

UPCOMING

Derandomization to catalytic space

2 weeks ago

48:31

Matching Correlated Random Geometric Graphs

1.2K views 2 weeks ago

53:05

Balancing Vectors with an Ising Model

3.4K views 2 weeks ago