As promised in the previous post, I will explain how an algorithm designed for the approximate near neighbor problem, the LSH algorithm, leads to a solution for the exact near neighbor problem (henceforth NNS). While, the algorithm for the exact problem will not have full guarantees, we will be able to give some partial guarantees. Usually … Continue reading Exact Algorithms from Approximation Algorithms? (part 2)
Exact Algorithms from Approximation Algorithms? (part 1)
One great "soft" challenge in (T)CS I find to be how to go on to find useful algorithms for problems that we believe (or have even proven!) to be hard in general. Let me explain by giving the all-too-common-example: Practitioner: I need to solve problem X. Theoretician: Nice question, let me think... Hm, it seems hard. … Continue reading Exact Algorithms from Approximation Algorithms? (part 1)
Tiny ToCT
Tiny ToCT studies the following question: could a marvelous field of huge impact be squeezed into a tiny space of 140 characters? Good luck!
An Economic Perspective on Academic Publication
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
On Endre Szemerédi’s Gifts to Computer Science
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
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 