Ryan Williams provedsevenyears ago that ACC does not contain NEXP. The new paper shows that ACC does not contain NQP (nondeterministic quasi-polynomial time). A huge improvement!

(ACC stands for Boolean functions that can be described by bounded depth polynomial size citcuits with Boolean gates and mod 6 gates.)

Oded’s next choice is a paper by Roei Tell pointing out a remarkable direct consequence from the Murray-Williams result for the hardness vs. randomness agenda. If the goal is to show that BPP=P implies that NP ≠ P, then if earlier we had results 10% this strong the consequence is perhaps 70% strong.

Remarks:Above there are links to three posts (by Oded, Scott, and Dick and Ken) on Ryan’s older result. I wrote several posts on bounded depth circuits of several kinds, here (with an interesting comment by Ryan!), here, here, and here.

The opportunity to present the paper arose when a week ago I attended a great lecture on game theory by Yair Tauman and met there Adam Kalai, Yael, and Yoyo.

Due to space limitation I did not include the following planned comment/footnote:

“Allan Hatcher wrote in the preface of his legendary textbook on algebraic topology:

Not included in this book is the important but somewhat more sophisticated topic of spectral sequences. It was very tempting to include something about this marvelous tool here, but spectral sequences are such a big topic that it seemed best to start with them afresh in a new volume.

A similar story can be told about the marvelous area of cryptography in the context of my paper. We talked about P and NP, graph algorithms, randomized algorithms, complexity of linear programming, computational geometry, algorithmic game theory, Papadimitriou’s classes, circuit complexity, bounded depth computation, parallel computing (a little), distributed computing and collective coin flipping, probabilistically checkable proofs (PCP) and hardness of approximations, property testing, quantum computing, Hamiltonian complexity, quantum fault-tolerance, efficient learnability, sampling complexity, primality and factoring. But for similar reasons to Hatcher’s it seems best that connections with cryptography will wait to a fresh new paper … (by a different author).”

In hindsight I could have even said “by a different Kalai”. Yael’s paper is centered around cryptography, and it has some tangent points with my paper: it talks about the new types of proofs appearing in the theory of computing, mentions games with provers and verifier, and connections to the quantum world via the non-signaling property.

Towards Kalai, Kalai, Kalai, and Kalai paper

There is an ongoing plan for writing a paper coauthored by Adam, Ehud, Gil and Yael Kalai involving learnability, game theory, algorithms, and cryptography.

Trivia question (thanks to Joan Feigenbaum): Who said and in what context: tangents have rights too!

Frankl’s conjecture is the following: Let be a finite family of finite subsets of which is closed under union, namely, if then also .

Then there exists an element which belongs to at least half the sets in .

Polymath 11 was devoted to this question (Wiki, first post, last post). We mentioned the conjecture in the first blog post over here and several other times, it was also mentioned over Lipton and Regan’s blog (here and here) and various other places.

In this post I want to mention a recent improvement by Ilan Karpas on the problem for large families. Ilan showed that the conjecture is true when the family contains at least sets.

Notation: For a family and an element let . The abundance of an element is . Let’s call an element good, if . Frankl’s conjecture thus asserts that for every union closed family there is a good element.

The earlier record

Balla, Bòllobas and Eccles proved that for every union-closed family of subsets of of size at least there is a good element. In fact, they showed that in this case the average of over all elements is at least . For the average statement this result is best possible. Eccles improved it further and showed that the assertion of Frankl’s conjecture holds when .

Theorem 1: The assertion of Frankl’s conjecture holds when .

The proof is a surprisingly simple Fourier theoretic proof and it applies for a larger class of families: families with the property that every set not in covers at most one set in . (For this larger class the assertion of Frankl’s conjecture may fail when )

Theorem 2: For some , the assertion of Frankl’s conjecture holds when .

The proof is a more involved Fourier-based proof. It also uses the following result of independent interest.

Theorem 3: for any union-closed family, the number of sets which are not in that cover a set in is at most . (The inequality is tight.)

As far as I know this is the first time Fourier’s method helps for Frankl’s problem. I wonder what is the potential of this method.

Abigail Raz’ result

In a recent very nice paper Abigail Raz’ showed that a nice extension of Frankl’s conjecture proposed in polymayh11 fails.

Dear all, here is the draft of the second third of my paper for ICM 2018. Corrections and comments are very welcome! This part is around voting games and election rules, Boolean functions and their Fourier representation, noise stability and sensitivity especially of percolation, and a little circuit complexity and PCP. Corrections and comments are most welcome.

I have a very strict December 20 deadline (self-imposed, I missed the official one) for my ICM2018 paper. I plan to talk about three puzzles on mathematics, computation and games, and here is a draft of the first third. Corrections and comments are very welcome! This part is around the simplex algorithm for linear programming.

Three central open problems in extremal combinatorics are

The 1975 Erdős-Sós forbidding one intersection problem, asks for the maximal
size of a k-uniform hypergraph that does not contain two edges whose intersection
is of size exactly t−1;

The 1987 Frankl-Füredi special simplex problem asks for the maximal
size of a k-uniform hypergraph that does not contain the following forbidden configuration: d+1 edges such that there exists a set for which for any i and the sets {Ei \ S} are pairwise disjoint.

The 1974 Erdős-Chvátal’s simplex conjecture proposes an answer for the maximal
size of a k-uniform hypergraph that does not contain a d-simplex. Here, a d-simplex is a family of d+1 sets that have empty intersection, such that the intersection
of any d of them is nonempty.

All these questions are related to the Erdős-Ko-Rado theorem (see this post and many others). For , two edges whose intersection is of size exactly t−1 are just two disjoint edges and so is a 1-simplex and a special 1-simplex.

The papers by Keller and Lifshitz and by Ellis, Keller, and Lifshitz

I have an ambitious plan to devote two or three posts to these developments (but not before January). In the first post I will give some general background on Turan’s problem for hypergraphs and the new new exciting results, Then (perhaps in a second post) I will give little background on two major methods, the Delta-system method initiated by Deza, Erdos and Frankl and used in many earlier papers mainly by Frankl and Furedi, and the Junta method initiated by Friedgut which is used (among other ingredients) in the new paper. Then I will write about the new results in the last post.

Paul Erdos, Thomas Luczak, Ehud Friedgut, and Svante Janson

The “basic notion seminar” is an initiative of David Kazhdan who joined the Hebrew University math department around 2000. People give series of lectures about basic mathematics (or not so basic at times). Usually, speakers do not talk about their own research and not even always about their field. My first lecture series around 2004 was about computational complexity theory, and another one on extremal combinatorics developed into a series of posts (I,II,III,IV,VI). Since then I talked in the seminar about various other topics like convex polytopes, generalization of planar graphs, and Boolean functions. The seminar did not operate for a few years and we were all very happy to have it back last spring!

Helly-type theorems

I just finished two lectures on Helly-type theorems in the basic notions seminar. which is the topic of my doctoral thesis. (I am interested in Helly type theorems since I was an undergraduate student.) Recently, Helly-type theorems where involved in the study of high dimensional expanders and other topics in high dimensional combinatorics. Alex Lubotzky and Tali Kaufman are running now a special year at the IIAS devoted to high dimensional combinatorics so I thought it would be nice to devote a basic notion seminar to this topic.

My first talk followed quite closely these two posts (I,II). Let me devote this post to the “cascade conjecture” which is a generalization of Tverberg’s theorem.

Tverberg’s theorem (1965): Let be points in , . Then there is a partition of such that .

The Cascade Conjecture

Given a set of points in , we let be the set of points in which belong to the convex hull of pairwise disjoint subsets of . (We may allow repetitions among the elements of .) Thus, is just the convex hull of .

Let .

Radon’s theorem: If then .

Radon theorem is a simple consequence of the fact that points in an affine space of dimension are affinely dependent. (Note that is one plus the dimension of the affine span of .)

It seems that the following conjecture requires some “higher linear algebra”

Conjecture 1: If then .

Conjecture 1 is wide open. It is a special case of the following more general conjecture

Conjecture 2 (The Cascade Conjecture): If then .

Another formulation of Conjecture 2 is

The Cascade Conjecture: .

Of course, the cascade conjecture implies Tverberg’s theorem since given points in , we have that , and therefore the conjecture implies that .

For the 5-point configuration on the left and . For the configuration on the right and . Indeed also

There are two facts about the cascade conjecture that are separately quite innocuous but combined are mind blogging. The first fact is that the conjecture was made in 1974, namely 43 years ago. Continue reading →

I just received an advanced copy of my very first book: “Gina Says: Adventures in the Blogsphere String War” published by Word Scientific. It is a much changed version compared to the Internet version of 8 years ago and it contains beautiful drawings by my daughter Neta Kalai. How exciting!

Here is another video of a smashing short talk by my dear friend Itai Benjamini with beautiful conjectures proposing an important new step in the connection between percolation and conformal geometry.

Here is the link to Itai’s original paper Percolation and coarse conformal uniformization. It turns out that the missing piece for proving the conjecture is a very interesting (innocent looking) theorem of Russo-Seymour-Welsh type.

This conjecture appears also in a paper Itai wrote with me Around two theorems and a lemma by Lucio Russo. Our paper is part of a special issue of Mathematics and Mechanics of Complex Systems (M&MoCS), in honor of LucioRusso, in occasion of his retirementis. In addition to the conjectural Russo-Seymour-Welsh type theorems, we also present some developments, connections, and problems related to Russo’s lemma and Russo’s 0-1 law.