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