By Ittai Abraham and Moshe Babaioff Can we use Economic insights to better understand the ecosystem of Academic Publication? In light of recent changes, how can we optimize this ecosystem? After all, this is a system with many participants with different interests: authors, publishers, academic institutions, consumers (of academic publications) which can all be modeled … Continue reading An Economic Perspective on Academic Publication

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

In this post and the next, I will talk about the problem of maximizing a submodular function. Submodularity is a natural property of set functions, that captures the diminishing returns property. Formally, let $latex f$ be a set function $latex f : 2^{U} \rightarrow \Re$, and let us assume that $latex U=[n]$.  Then $latex f$ … Continue reading Maximizing Submodular Functions (Part 1)

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