Monthly Archives: December 2011

Ryan O’Donnell: Analysis of Boolean Function

Posted on December 18, 2011 by Gil Kalai

Ryan O’Donnell has begun writing a book about Fourier analysis of Boolean functions and  he serializes it on a blog entiled Analysis of Boolean Function.  New sections appear on Mondays, Wednesdays, and Fridays. Besides covering the basic theory, Ryan intends to describe applications … Continue reading →

Posted in Combinatorics, Computer Science and Optimization | Tagged , , | 1 Comment

Alexander Chervov MO’s Question: Noteworthy-Achievements-In-And-Around-2010

Posted on December 14, 2011 by Gil Kalai

Alexander Chervov asked over Mathoverflow about Noteworthy results in and around 2010  and some interesting results were offered in the answers. If you would like to mention additional results you can comment on them here. The only requirement is to … Continue reading →

Posted in Mathematics over the Internet | Tagged | 5 Comments

Cap Sets, Sunflowers, and Matrix Multiplication

Posted on December 9, 2011 by Gil Kalai

This post follows a recent paper On sunflowers  and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , , , , | 10 Comments

Projections to the TSP Polytope

Posted on December 7, 2011 by Gil Kalai

Michael Ben Or told me about the following great paper Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf. The paper solves an old conjecture … Continue reading →

Posted in Computer Science and Optimization, Convex polytopes | Tagged , , , | 2 Comments