### Universal Traversal on the Clique?

Consider a -regular undirected graph. A walk from a vertex is a sequence of edge labels in , which corresponds to a path on the graph that starts at and at step follows the [...]

Consider a -regular undirected graph. A walk from a vertex is a sequence of edge labels in , which corresponds to a path on the graph that starts at and at step follows the [...]

It’s exciting times for theory at Stanford these days, with more activity than ever. In the computer science department alone, we’ve hired six new theory [...]

Pseudorandom Functions (PRFs) are among the most fundamental Cryptographic primitives. with applications as basic as private-key encryption, identification and authentication [...]

About a month ago, Tim Gowers described a fun potential new polymath project. Here is the basic setup: Say are -sided dice, i.e. each takes values in . We say that beats if [...]

By Steve Mussmann and Jacob Steinhardt. The celebrated pigeonhole principle says that if we have disjoint sets each of size , then (the number of sets) is at most . [...]

Theory Dish – A new research blog by the warm theory of computing community here at Stanford. Enjoy!

[...]