### The Return of the Page Limit

Boaz is pointing out that page limit is back for STOC 2018. Too bad. When we got rid of the page limit (FOCS 2013), we discussed our rational before and after, and I think it [...]

Boaz is pointing out that page limit is back for STOC 2018. Too bad. When we got rid of the page limit (FOCS 2013), we discussed our rational before and after, and I think it [...]

At times I have a title that is only waiting for a paper or a joke that is only waiting for a talk. And (with some effort) the opportunity usually presents itself. I am now [...]

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 [...]

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!

[...]