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
Month: March 2012
Maximizing Submodular Functions (Part 2)
Continuing on my last post, today I will talk about recent work by Niv Buchbinder, Moran Feldman, Seffi Naor, and Roy Schwartz that gives a simple 1/2 approximation to the (unconstrained) submodular maximization problem, matching the hardness. Do see the paper (which should be available in a couple of weeks) for full details. Apologies in … Continue reading Maximizing Submodular Functions (Part 2)
Maximizing Submodular Functions (Part 1)
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)
Embracing uncertainty, causality, and curiosity: Judea Pearl wins the 2011 A. M. Turing Award
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
Encouraged, Expected, and Enforced?
Has anything changed in the way the TCS community publishes papers? Comparing recent STOC 2012 and FOCS 2012 to their counterparts STOC 2003 and FOCS 2004 one thing that has changed is that today we do not allow submitting printed copies by mail anymore. All submissions are done electronically. But a much more radical change is happening … Continue reading Encouraged, Expected, and Enforced?
Are You Working too Hard?
Uri Alon is a very influential Weizmann Professor studying Molecular Cell Biology and Physics of Complex Systems and also a friend. His research deserves many superlatives but I am not qualified to give them. I'd like to point to a talk he gave a few years ago at the Harvard theory lunch (mind you, its … Continue reading Are You Working too Hard?
Windows On Theory 