Theoretical Computer Science is blessed (or cursed?) with many open problems. For some of these questions, such as the $latex {P}&fg=000000$ vs $latex {NP}&fg=000000$ problem, it seems like it could be decades or more before they reach resolution. So, if we have no proof either way, what do we assume about the answer? We could … Continue reading Truth vs Proof: The Unique Games Conjecture and Feige’s Hypothesis

Having your assumptions and beliefs challenged by a group of seasoned law enforcement professionals and subject matter experts can be a rather disturbing experience. It is exactly what happened to me this week during the workshop on the role of technology in combating human trafficking, organized by Rane Johnson-Stempson, danah boyd, and the good folks … Continue reading Inconvenient Truth

You are heading to Paris for the first time. You finally get there and it is time for dinner, you need to pick a restaurant. Of course you would like to avoid  Tourists-Traps. Traditionally, people were relying on rule of thumb, and if they were lucky and knew someone that has some useful information, they … Continue reading Community brain

Hastad's Switching Lemma is one of the gems of computational complexity. The switching lemma analyzes the effect of random restrictions on $latex AC^0$ circuits, which are constant depth circuits with AND, OR and NOT gates of unbounded fanin. It says that such restrictions tends to simplify  $latex AC^0$ circuits in surprising ways. An immediate consequence of the switching lemma is strong … Continue reading The Switching Lemma

Tim Gowers reports on a new set of open access math journals. There will be a Forum of Mathematics:Pi that is supposed to be a generalist math journal, and Forum of Mathematics:Sigma that would have "clusters" for different areas. It will be paid for by Cambridge University Press for the first three years, and will then … Continue reading Interesting new development in Math publishing