Tiny ToCT studies the following question: could a marvelous field of huge impact be squeezed into a tiny space of 140 characters? Good luck!

Personally, I was so very pleased to hear that Endre Szemerédi won the 2012 Abel Prize. In my eyes, this sentiment should be shared by all mathematicians and certainly by all who study the theory of computations. Szemerédi's contributions to computer science are immense. The first examples that come to mind are most probably Szemerédi's regularity lemma … Continue reading On Endre Szemerédi’s Gifts to Computer Science

The guest blogger for today is our colleague  Moises Goldszmidt from MSR-SVC  who was Judea Pearl 's student from 88 to 92  (a couple of related posts can be found here and here): ---------------------------------------------------------------------- In celebration of Judea Pearl winning the 2011 A.M. Turing Award I would like to provide a personal view and perspective on a couple of Judea’s key insights. … Continue reading Embracing uncertainty, causality, and curiosity: Judea Pearl wins the 2011 A. M. Turing Award

About a month ago, in our theory seminar, we had a talk by Paul Ohm. Paul is a Professor of Law at the University of Colorado and has done important work in the interface between Computer Science and the Law (which was also the title of his talk). There is much to report about this … Continue reading Occupy Database – Privacy is a Social Choice

In my last post I promised a simple proof that there are no deterministic extractors for SV sources. The proof is due to Salil Vadhan, Avi Wigderson and myself and its technique has been used to obtain impossibility results on doing cryptography with SV sources. We show that even more restricted classes of sources are not amenable to deterministic … Continue reading No Deterministic Extraction from Santha-Vazirani Sources – A Simple Proof

Last week Ryan O'Donnell mentioned, as part of his Simons Symposium report, that Per Austrin (with Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth) have a new, Fourier-based, proof of an "old" result due to Miklos Santha and Umesh Vazirani. This is a great opportunity to tell you a bit about deterministic extraction. I will also discuss (in my … Continue reading Correlations and Bias in Deterministic Extraction

Our first guest blog (which is more of an announcement) comes from Cynthia Dwork. You can email Cynthia if you want to learn more … ---------------- An inter-disciplinary group of researchers based at Stanford University, UC Berkeley, and Microsoft Research, Silicon Valley, invites applications for two-year postdoctoral fellowships under the Sloan foundation-sponsored project “Towards Practicing … Continue reading New Interdisciplinary Center on Privacy with Postdoc Positions