Piotr Indyk’s Motwani Distinguished Lecture
Since 2011, the Stanford theory group has hosted the Rajeev Motwani Distinguished Lecture Series, a series of theory colloquia aimed at a broad audience. You can see the [...]
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 [...]
Theory Explosion at Stanford
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 [...]
Struggles of the Pioneers
Pseudorandom Functions (PRFs) are among the most fundamental Cryptographic primitives. with applications as basic as private-key encryption, identification and authentication [...]
Intransitive Dice
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 [...]
Does Pigeonhole Degrade Gracefully?
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 – a Dish Best Served Warm
Theory Dish – A new research blog by the warm theory of computing community here at Stanford. Enjoy!
[...]