My beloved mother Carmella Kalai passed away last week.
With me, 1956
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 of .
Ramsey’s famous theorem asserts that if is a complete graph on vertices then is finite. Ir follows that is finite for every graph and understanding the dependence of on is a very important question. Of course there are very basic extensions: to many colors, to different requirements for different colors, and to hypergraphs.
A graph is -degenerate if it can be reduced to the empty graph by successively deleting vertices of degree at most . Thus, trees are 1-degenerate (and 1-degenerate graphs are forests), and planar graphs are 5-degenerate. For graphs to be degenerate is equivalent to the condition that the number of edges is at most linear times the number of vertices uniformly for all subgraphs.
In 1973, Burr and Erdős conjectured that that for every natural number , there exists a constant such that every -degenerate graph on vertices satisfies This is a very different behavior than that of complete graphs where the dependence on the number of vertices is exponential. In 1983 Chvátal, Rödl, Szemerédi, and Trotter proved the conjecture when the maximum degree is bounded. Over the years further restricted cases of the conjectures were proved some weaker estimates were demonstrated. These developments were instrumental in the developments of some very basic tools in extremal and probabilistic combinatorics. Lee’s paper Ramsey numbers of degenerate graphs proved the conjecture!
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 Lost letter and P=NP. Let me mention one of the applications: refuting a 1999 conjecture by Benjamini, Schramm and me.
Update: Li-Yang Tang explained matters in an excellent comment below. Starting with: “In brief, we believe that an average-case depth hierarchy theorem rules out the possibility of a converse to Hastad-Boppana-LMN when viewed as a statement about the total influence of *constant*-depth circuits. However, while the bound is often applied in the setting where d is constant, it in fact holds for all values of d. It would interesting to explore the implications of our result in regimes where d is allowed to be super-constant.
Let me add that the bounded depth case is an important case (that I referred to here), that there might be some issues failing the conjecture for non-constant depth “for the wrong reasons”, and that I see good prospect that RST’s work and techniques will refute BKS conjecture in full also for non-bounded depth.
Update: Rossman, Servedio, and Tan refuted some important variations of our conjecture, while other variations remain open. My description was not so accurate and in hindsight I could also explained the background and motivation better. So rather than keep updating this post, I will write a new one in a few weeks.
Theorem: If f is described by a bounded depth circuit of size s and depth d then I(f) the total influence of f, is at most .
The total influence of is defined as follows: for an input write for the number of neighbors y of x with . .
The history of this result as I remember it is that: it is based on a crucial way on Hastad Switching lemma going back to Hastad 1986 thesis, and for monotone functions one can use an even earlier 1984 result by Boppana. It was first proved (with exponent “d”) in 1993 by Linial-Mansour and Nisan, as a consequence of their theorem on the decay of Fourier coefficients for AC0 functions, (also based on the switching lemma). With the correct exponent d-1 it is derived from the switching lemma in a short clean argument in a 97 paper by Ravi Boppana; and finally it was extended to a sharpening of LMN result about the spectral decay by Hastad (2001).
Conjecture: (Benjanmini, Kala, and Schramm, 1999): Every Boolean function f is “close” to some depth-d size s circuit with not much larger than I(f).
Of course, the exponent (d-1) is strongest possible but replacing it with some constant times d is also of interest. (Also the monotone case already capture much interest.)
As we will see the conjecture is false even if the exponent d-1 is replaced by a constant times d. I do not know what is the optimal function u(d) if any for which you can replace the exponent d-1 by u(d).
Update: Following some comments by Boaz Barak I am not sure that indeed the new examples and results regarding them leads to disproof of our conjecture. The remarkable part of RST’s paper is that the RST example cannot be approximated by a circuit of smaller depth – even by one. (This has various important applications.) In order to disprove our conjecture one need to show that the influence of the example is smaller than what Boppana’s inequality ( ) gives. This is not proved in the paper (but it may be true).
The RST’s result does say that if the influence is (say) logn (where n is the number of variables,) and the function depends on a small number of variables then it need not be correlated with a function in AC0.
Anyway I will keep you posted.
in 2007 O’Donnell and Wimmer showed that our inverse conjecture is false as stated. They took a Boolean function which is a tribe function on half the variables and “anti-tribes” on the rest. This still left the possibility that the exponent d-1 could be replaced by d or that “close” could be replaced by a weaker conclusion on substantial correlation.
Rossman, Servedio, and Tan.show a genuinely new reason for small influence!Their example, named after Mike Sipser, is based on the AND-OR tree – a Boolean formula with alternating AND and OR levels and carefully designed parameters. The crucial part is to show that you cannot approximate this function by lower depth circuits. The theorem proved by RST is amazingly strong and does not allow reducing the depth even by one! The novel technique for proving it of random projections is very exciting.
It is still possible (I think) that such inverse theorems hold when the individual influences of all variables is below polylog(n)/n where n is the number of variables. Let me pose it as a conjecture:
Conjecture: Every Boolean function f with n variables and individual influences below polylog (n)/n is close to a function g
in AC0 of size s depth d where is polylog (n).
It is a pleasure to announce my own birthday conference which will take place in Jerusalem on June 15-16 2015.
Here is the meeting’s homepage!
The organizers asked me also to mention that some support for accommodation in Jerusalem for the duration of the conference is available.
Muli, Dor and Subash, Jerusalem May 21 2015.
Michel Talagrand Gregory Margulis
In this post I will tell you about a new paper by Subhash Khot, Dor Minzer and Muli Safra entitled: On Monotonicity Testing and Boolean Isoperimetric type Theorems. This remarkable paper gives a definite answer to one of the main open problems on property testing, proves some wonderful new isoperimetric inequalities, and shed some light on the still mysterous property of monotonicity.
Property testing is an exciting area which lies between mathematics and the theory of computing. (Closely related to PCP and to some modern aspects of error-correcting codes.) Here is a post about it in Terry Tao’s blog.
Suppose that you have an unknown graph G and you want to distinguish between two possibilities
1) The graph G contains a triangles
2) We can remove an 1% of the edges of G so that no triangle will remain.
It turns out that by looking at a bounded number of edges drawn at random we can either demonstrate that G contains a triangle or demonstrate that with high probability the second possibility holds! Moreover, this is a deep mathematical result.
Property testing resembles a little election polls (and, more generally statistical hypothesis testing): We can estimate the outcomes of the election with good accuracy and high probability by probing the votes of a bounded number of voters.
Given a Boolean function f, what is the smallest number of queries needed to be able to say
1) The function f is not monotone:
2) With high probability f is at most ε-far from monotone, namely, it can be made monotone by flipping the value of at most values.
We will denote by ε(f) the normalized Hamming distance distance of a Boolean function f to the set of monotone functions.
A brief incomplete history of monotone testing
1) Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Combinatorica, 20(3):301–337, 2000.
This paper considered the tester: Choose x and y at random such that y > x test if f(y) < f(x).
Using the basic edge isoperminetric inequality it was proved that n queries suffice.
It tooks 15 years a new tester and a new isoperimetric inequality to break this record and show that queries suffice.
2) Deeparnab Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions over the hypercube. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 411–418, 2013.
An improvement to was achieved here
3) Xi Chen, Rocco Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In Annual Symposium on Foundations of Computer Science, FOCS ’14, 2014.
The paper by Khot, Minzer and Safra reduces this to the optimal (apart from powers of logn) .They use yet a new tester and a new isoperimetric inequality.
I did not talk about adaptive version of the problem about lower bounds and about the dependence on . Khot, Minzer and Safra also give (up to powers of log) optimal dependence on .
Margulis’s Theorem: Let f be a Boolean function on . Let $\latex \mu$ be the uniform probability measure on $\Omega_n$. For define
Now, the edge boundary (or total influence) of f is defined by
it is also denoted by .
The vertex boundary of f is defined by
The classic edge-isoperimetric result asserts that
Here var(f), is the variance of f.
Margulis theorem asserts that for some constant C:
In fact Margulis proved the result in greater generality for Bernoulli probability measures defined by where .
Again Talagrand’s theorem extends to the Bernoulli case. Talagrand’s theorem implies Margulis’ theorem by a simple application of the Cauchy-Swarz inequality. Continue reading
Angry birds peace treaty by Eretz Nehederet
A few years ago I became interested in the question of whather new versions of the computer game “Angry Birds” gradually makes it easier to get high scores. Devoted to the idea of Internet research activity I decided to explore this question on “ARQADE” a Q/A site for video games. I was especially encouraged by the success of an earlier question that was posted there by Andreas Bonini: Is Angry Birds deterministic? As you can see Bonini’s question got 239 upvotes making it the second most popular quastion in the site’s history. (The answer with 322 upvotes may well be the most popular answer!) Is Angry Birds deterministic? (Click on pictures to enlarge.)
Arqade’s top questions
Some comments to the answer regarding Angry Birds.
The question if Angry Birds is deterministic is the second most decorated question on Arqade, and its answers were extremely popular as well. (Other decorated questions include: How can I tell if a corpse is safe to eat? How can I kill adorable animals? and My head keeps falling off. What can I do?.) As you can see from the comments taken from the site referring to science was warmly accepted!
I decided to ask a similar question about new versions and hoped for a similar success. Continue reading
Arguably mathematics is getting harder, although some people claim that also in the old times parts of it were hard and known only to a few experts before major simplifications had changed matters. Let me report here about two recent remarkable simplifications of major theorems. I am thankful to Nati Linial who told me about the first and to Itai Benjamini and Gady Kozma who told me about the second. Enjoy!
Here is the paper. Abstract: It was conjectured by Alon and proved by Friedman that a random -regular graph has nearly the largest possible spectral gap, more precisely, the largest absolute value of the non-trivial eigenvalues of its adjacency matrix is at most with probability tending to one as the size of the graph tends to infinity. We give a new proof of this statement. We also study related questions on random n-lifts of graphs and improve a recent result by Friedman and Kohler.
Here is the paper Abstract: We provide a new proof of the sharpness of the phase transition for nearest-neighbour Bernoulli percolation. More precisely, we show that – for , the probability that the origin is connected by an open path to distance $n$ decays exponentially fast in $n$. – for , the probability that the origin belongs to an infinite cluster satisfies the mean-field lower bound . This note presents the argument of this paper by the same authors, which is valid for long-range Bernoulli percolation (and for the Ising model) on arbitrary transitive graphs in the simpler framework of nearest-neighbour Bernoulli percolation on .