Recent Comments

Recent Posts
 Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes
 Happy Birthday Ervin, János, Péter, and Zoli!
 My Mathematical Dialogue with Jürgen Eckhoff
 Test Your Intuition (23): How Many Women?
 Happy Birthday Richard Stanley!
 Influence, Threshold, and Noise
 Erdős Lectures 2014 – Dan Spielman
 Answer to Test Your Intuition (22)
 Test your intuition (22): Selling Two Items in a Bundle.
Top Posts & Pages
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 Believing that the Earth is Round When it Matters
 Polymath 8  a Success!
 Why Quantum Computers Cannot Work: The Movie!
 NavierStokes Fluid Computers
 Another Forgotten Bet: Is Don Zagier About to Owe Me 1000 Shekels For The Proof of the ABC Conjecture?
 Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes
 Noise Stability and Threshold Circuits
 Five Open Problems Regarding Convex Polytopes
RSS
Category Archives: Combinatorics
Celebrations in Sweden and Norway
Celebrations for Endre, Jean and Terry Anders Bjorner presents the 2012 Crafoord Prize in Mathematics I am in Sweden for two weeks to work with colleagues and to take part in two celebrations. Jean Bourgain and Terence Tao are the 2012 laureates … Continue reading
Posted in Academics, Combinatorics, Conferences, Updates
Tagged Endre Szemeredi, Jean Bourgain, Terrence Tao
2 Comments
Galvin’s Proof of Dinitz’s Conjecture
Dinitz’ conjecture The following theorem was conjectured by Jeff Dinitz in 1979 and proved by Fred Galvin in 1994: Theorem: Consider an n by n square table such that in each cell (i,j) you have a set with n or more elements. … Continue reading
Posted in Combinatorics, Games
4 Comments
Fractional SylvesterGallai
Avi Wigderson was in town and gave a beautiful talk about an extension of SylvesterGallai theorem. Here is a link to the paper: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes by Boaz Barak, Zeev … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Geometry
Tagged Avi Wigderson, Codes, Greg Kuperberg, SylvesterGallai
3 Comments
Ryan O’Donnell: Analysis of Boolean Function
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
Cup Sets, Sunflowers, and Matrix Multiplication
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 Grouptheoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), … Continue reading
High Dimensional Expanders: Introduction I
Alex Lubotzky and I are running together a year long course at HU on High Dimensional Expanders. High dimensional expanders are simplical (and more general) cell complexes which generalize expander graphs. The course is taking place in Room 110 of the mathematics building on … Continue reading
Posted in Combinatorics, Teaching
4 Comments
Noise Sensitivity and Percolation. Lecture Notes by Christophe Garban and Jeff Steif
Lectures on noise sensitivity and percolation is a new beautiful monograph by Christophe Garban and Jeff Steif. (Some related posts on this blog: 1, 2, 3, 4, 5)
Posted in Combinatorics, Probability
Tagged Christoph Garban, Jeff Steif, Noise, Noisesensitivity, Percolation
Leave a comment
Alantha Newman and Alexandar Nikolov Disprove Beck’s 3Permutations Conjecture
Alantha Newman and Alexandar Nikolov disproved a few months ago one of the most famous and frustrating open problem in discrepancy theory: Beck’s 3permutations conjecture. Their paper A counterexample to Beck’s conjecture on the discrepancy of three permutations is already on … Continue reading
Discrepancy, The BeckFiala Theorem, and the Answer to “Test Your Intuition (14)”
The Question Suppose that you want to send a message so that it will reach all vertices of the discrete dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the … Continue reading
Test Your Intuition (14): A Discrete Transmission Problem
Recall that the dimensional discrete cube is the set of all binary vectors ( vectors) of length n. We say that two binary vectors are adjacent if they differ in precisely one coordinate. (In other words, their Hamming distance is 1.) This … Continue reading