The last few weeks have seen amazing results in additive combinatorics, where following a breakthrough by Croot, Lev and Pach, several longstanding open questions have been resolved using short simple proofs. I haven’t been following this progress, but fortunately Bobby Kleinberg gave an excellent talk yesterday in our reading group about some of these works, … Continue reading Yet another post on a.p. free set bounds
University funds spent on study of Unicorns
Actually, not really... Northwestern University held a workshop on semidefinite programming hierarchies and sum of squares. Videos of the talks by Prasad Raghavendra, David Steurer and myself are available from the link above. The content to unicorns ratio in Prasad and David's talks is much higher ☺
Happy towel day
Tomorrow, Wednesday May 25, is the international Towel Day in honor of Douglas Adams, author of the 5-book trilogy "The hitchhiker's Guide to the Galaxy". In his book (and his prior 1978 radio series) Adams gave a nice illustration of computational complexity and non uniform computation in his story about the "deep thought" computer who took 7.5 million … Continue reading Happy towel day
Theory Life-Hacks
LifeHacker is a website dedicated to tricks, especially technology related, to make people more efficient or productive. The signal to noise ratio in that website is not particularly high, but I think it is a good idea to share tricks that can save time and effort. In particular, are there tools or tricks that made a difference in your … Continue reading Theory Life-Hacks
Highlights of Algorithms registration
Aleksander Madry asks me to announce that registration for the Highlights of Algorithms conference he posted about is open. The registration link is http://highlightsofalgorithms.org/registration/. (Early registration is due April 30.) Also, the preliminary program is available at http://highlightsofalgorithms.org/program/. The program is packed with 28 invited talks and with even a larger number of short contributions. Those interested in attending … Continue reading Highlights of Algorithms registration
Bayesianism, frequentism, and the planted clique, or do algorithms believe in unicorns?
(See also pdf version , and these lecture notes) The divide between frequentists and Bayesians in statistics is one of those interesting cases where questions of philosophical outlook have actual practical implications. At the heart of the debate is Bayes’ theorem: $latex \Pr[A|B] = \Pr[A \cap B ]/\Pr[B]\;.$ Both sides agree that it is correct, but they disagree … Continue reading Bayesianism, frequentism, and the planted clique, or do algorithms believe in unicorns?
Stanford, Here I Come
Most of the stories in the research-life story project (including mine) are already processed and often told with some well-packaged perspective the teller wants to share. Today I am sharing a moment as it unfolds: Come next fall, I’ll be joining the Stanford CS Department. I’m very excited. Since the closing of MSR-SV, I’ve been … Continue reading Stanford, Here I Come
Chaining Method workshop – travel funding
Jelani Nelson tells me there's travel funding for the workshop at http://toc.seas.harvard.edu/cmacs for postdocs and students, but the deadline to apply is next Friday (April 1). Instructions to apply are at the link above.
The iPhones of terrorists
On December 5, 2015, Syed Farook and his wife, Tashfeen Malik entered the banquet room in the Inland Regional Center in San Bernardino, California wearing ski masks and holding semi-automatic pistols and rifles. They shot and killed 14 people- parents, spouses, children who will never return to their loved ones. It is the right, and indeed the duty of … Continue reading The iPhones of terrorists
Chaining methods continued (guest post by Jelani Nelson)
[This is the sequel to Jelani's previous post on chaining method; for more, see the post STOC workshop on this topic --Boaz] 1. A case study: (sub)gaussian processes To give an introduction to chaining, I will focus our attention on a concrete scenario. Suppose we have a bounded (but possibly infinite) collection of vectors $latex {T\subset \mathbb{R}^n}&fg=000000$. … Continue reading Chaining methods continued (guest post by Jelani Nelson)
Windows On Theory 