Prediction with a short memory
‘’If any one faculty of our nature may be called more wonderful than the rest, I do think it is memory’’ — Jane Austen In this blog, we’ll consider the [...]
Edit Distance: Recovering Alignments using Black-Box Estimation Algorithms
By Moses Charikar, Ofir Geri, Michael P. Kim, and William Kuszmaul. The edit distance between two strings and is the minimum number of insertion, deletion, or substitution [...]
Dahlia Malkhi on Industrial Computing Research Labs
My friend and colleague Dahlia Malkhi from the glory days of MSR-SVC (RIP), has posted her insightful thoughts on industrial computing research labs. As someone that spent [...]
A Glimpse at Stein’s Method, in Memory of Charles Stein
Charles Stein was one of the most active and influential Statisticians of the past century, with a career spanning seven decades including over sixty year as a professor in [...]
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 [...]
The Racist Side of ‘Fairness’
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 [...]
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 [...]
Theory Dish 