Monthly Archives: May 2015

Choongbum Lee proved the Burr-Erdős conjecture

Posted on May 22, 2015 by Gil Kalai

Let be a graph. The Ramsey number is the smallest such that whenever you color the edges of the complete graph with vertices with two colors blue and red, you can either find a blue copy or a red copy … Continue reading →

Posted in Combinatorics, Updates | Tagged , | 2 Comments

More Reasons for Small Influence

Posted on May 13, 2015 by Gil Kalai

Readers of the big-league ToC blogs have already heard about the breakthrough paper An average-case depth hierarchy theorem for Boolean circuits by Benjamin Rossman, Rocco Servedio, and Li-Yang Tan. Here are blog reports on Computational complexity, on the Shtetl Optimized, and of Godel … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Open problems, Probability | 13 Comments