Author Archives: Gil Kalai

New Isoperimetric Results for Testing Monotonicity

photo (11)

Muli, Dor and Subash, Jerusalem May 21 2015.

Talagrand1 Margulis2

Michel Talagrand            Gregory Margulis

Property testing

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.

Testing monotonicity

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 \epsilon2^n 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 n^{7/8} polylog (n) 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 n^{5/6} polylog (n) 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)  \sqrt n polylog (n).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 \epsilon.  Khot, Minzer and Safra also give (up to powers of log) optimal dependence on \epsilon.

Isoperimetric results: Margulis, Talagrand, and beyond

Margulis’s Theorem:  Let f be a Boolean function on \Omega_n={0,1}^n. Let $\latex \mu$ be the uniform probability measure on $\Omega_n$.  For x \in \Omega_n define

I(x)=|\{y \in \Omega_n,f(x)=1,d(x,y)=1, f(y) \ne f(x)\}|. 

Now, the edge boundary (or total influence) of f is defined by

I(f)-\mathbb E I(x) it is also denoted by B_e(f).

The vertex boundary of f is defined by  \Gamma (f)=\mu(\{x \in \Omega_n: I(x) \ne 0\})

The classic edge-isoperimetric result asserts that

(1)  I(f) \ge 2 var (f),

Here var(f), is the variance of f.

Margulis theorem asserts that for some constant C:

(2) I(f)\cdot \Gamma(f)\ge C (var (f))^2.

In fact Margulis proved the result in greater generality for Bernoulli probability measures defined by \mu_p(x)=p^k(1-p)^{n-k} where k=x_1+x_2+\dots +x_n.

Talagrand’s theorem

Talagrand’s theorem:

(3) \mathbb E(\sqrt{I(x)})\ge C'var(f).

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 Update

Angry birds peace treaty by Eretz Nehederet

Arqade

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!) abd Is Angry Birds deterministic? (Click on pictures to enlarge.) arqaFP

Arqade’s top questions

abdc

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!

My question

I decided to ask a similar question about new versions and hoped for a similar success. Continue reading

Two Delightful Major Simplifications

simplify

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!

Random regular graphs are nearly Ramanujan: Charles Bordenave gives a new proof of Friedman’s second eigenvalue Theorem and its extension to random lifts

Here is the paper. Abstract: It was conjectured by Alon and proved by Friedman that a random d-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 2\sqrt{d-1} +o(1) 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.

A simple proof for the theorem of Aizenman and Barsky and of Menshikov. Hugo Duminil-Copin and Vincent Tassion give  a new proof of the sharpness of the phase transition for Bernoulli percolation on \mathbb Z^d

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 p<p_c, the probability that the origin is connected by an open path to distance $n$ decays exponentially fast in $n$. – for p>p_c, the probability that the origin belongs to an infinite cluster satisfies the mean-field lower bound \theta(p)\ge\tfrac{p-p_c}{p(1-p_c)}. 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 \mathbb Z^d.

פרוק הממשלה על ידי נתניהו וההליכה לבחירות – משאל נוסף

עכשיו שתוצאות הבחירות בישראל ידועות אנא השיבו למשאלים

 כיצד אתה רואה את המהלך של נתניהו להקדמת הבחירות

אנא ענו שוב גם אם עניתם כבר למשאל הדומה לפני ארבעה ימים

מה היתה הרגשתך

מה משמעות המהלך

And to non-Hebrew speakers:

How do you see Netanyahu’s move of early election

 

Election Day

Today is the general election day in Israel, the third since starting this blog (I-2009,and II-2013). This is an exciting day. For me election is about participation much more than it is about influence and I try not to miss it. This time, for the first time,  I publicly supported one political party “the Zionist camp” headed by Herzog and Livni. The last four posts written in Hebrew are related to my position. (The fourth one has a poll which expresses also some academic curiosity, and I plan one more post with a similar follow-up  but post-election poll. But then we go back to combinatorics and more)

The blog also has now a new appearance and the header is a picture from 1999 with Jirka Matousek, a great mathematician and a great person who enlightened our community and our lives in many ways and who passed away at a terribly young age last Tuesday.

מדוע פרק נתניהו את הממשלה והלך לבחירות? משאל

 כיצד אתה רואה את המהלך של נתניהו להקדמת הבחירות

question-mark-red

  מה משמעות המהלך לגבי התאמת נתניהו לתפקיד

מה הרגשתך

המשאלים יסגרו עם סיום ההצבעה ביום הבחירות, ניתן להצביע ליותר מתשובה אחת או להוסיף תשובה

For our English readers:

Continue reading