Jacob Fox, David Conlon, and Benny Sudakov: Vast Improvement of our Knowledge on Unavoidable Patterns in Words

I heard a lecture by Benny Sudakov on the remarkable paper  Tower-type bounds for unavoidable patterns in words, by David Conlon, Jacob Fox, and Benny Sudakov.  Here are the slides, and let me let the slides speak for themselves.

The problem

Continue reading

Advertisements
Posted in Combinatorics | Tagged , , , | Leave a comment

Subhash Khot, Dor Minzer and Muli Safra proved the 2-to-2 Games Conjecture

Update: A related blog post by Boaz Barak: Unique Games Conjecture – halfway there?

The 2-to-2 Games Conjecture is a somewhat weaker form of Khot’s unique game conjecture.

The paper is: Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion by Subhash Khot, Dor Minzer and Muli Safra. (See this post for a team photo and another breakthrough.)

Here is the abstract: We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes the proof of the 2-to-2 Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a contribution from [BKT].

The Grassmann graph Gr_{global} contains induced subgraphs Gr_{local} that are themselves isomorphic to Grassmann graphs of lower orders. A set is called pseudorandom if its density is o(1) inside all subgraphs Gr_{local} whose order is O(1) lower than that of Gr_{global}.

We prove that pseudorandom sets have expansion 1−o(1), greatly extending the results and techniques in [DKKMS-2].

This is a great result. The Grassman graphs are graphs with vertices corresponding to k-dimensional subspaces of an n-dimensional vector space over a (small as possible) field. Of course, they are of much interest to combinatorialists.

The earlier papers mentioned are:

[DKKMS1]    Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra, Towards a Proof of the 2-to-1 Games Conjecture?

[DKKMS2] – Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra,  On Non-Optimally Expanding Sets in Grassmann Graphs.

[BKT] Boaz Barak, Pravesh Kothari, and David Steurer – personal communication.

A field with one element

Talking to the authors one gets the impression that what seems to be missing for proving the unique game conjecture is a field with one element.

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , | 5 Comments

Interesting Times in Mathematics: Enumeration Without Numbers, Group Theory Without Groups.

Lie Theory without Groups:

Enumerative Geometry and Quantization of Symplectic Resolutions

Our 21th Midrasha (school) IIAS, January 7 – January 12, 2018 Jerusalem

Enumerative Geometry Beyond Numbers

MSRI,  January 16, 2018 to May 25, 2018

Abstract for the Midrasha

Continue reading

Posted in Algebra and Number Theory, Combinatorics, Geometry, Updates | Leave a comment

Cody Murray and Ryan Williams’ new ACC breakthrough: Updates from Oded Goldreich’s Choices

Thanks to Irit Dinur for telling me about the following:

Oded Goldreich’s recent choice is about the paper: Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP, by Corry Murray and Ryan Williams.

Ryan Williams proved seven years 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!), herehere, and here.

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , | 8 Comments

Yael Tauman Kalai’s ICM2018 Paper, My Paper, and Cryptography

Yael Tauman Kalai: Delegating Computation via No-Signaling Strategies.

Ladies and Gentelmen,  Here is, exclusively for our readers, Yael Tauman Kalai’s ICM2018 paper: Delegating Computation via No-Signaling Strategies.

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.

Here are slides of a related talk by Yael on the evolution of proofs in computer science. Vidotaped lectures by her at the Simons Institute (Lecture 1, Lecture 2), and blog posts by Yael on Windows to Theory: The evolution of proofsChallenges in Outsourcing Computation;  and with Guy Rothblum: Progress and Challenges in Code Obfuscation (part 1 and part 2).

 

 

With Adam, Yael, and Maya,  Atlanta, 2007.

My ICM2018 paper, spectral sequences and cryptography

Many thanks for all the comments to the three thirds of my paper. Here is the combined and corrected version: Three puzzles on mathematics, computations, and games. Corrections and comments welcome.

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!

 

Posted in Combinatorics, Computer Science and Optimization | Tagged , , | 6 Comments

Ilan Karpas: Frankl’s Conjecture for Large Families

Frankl’s conjecture

Frankl’s conjecture is the following: Let \cal A be a finite family of finite subsets of N=\{1,2,\dots,n\} which is closed under union, namely,  if S,T \in {\cal A} then also S \cup T \in {\cal A}.

Then there exists an element x which belongs to at least half the sets in \cal A.

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 2^{n-1} sets.

Notation: For a family \cal A and an element x \in N let {\cal A}_x=\{S \in {\cal A}: x \in S\}. The  abundance  a(x) of  an element x is |{\cal A}_x|/|{\cal A}|. Let’s call an element good,  if a(x) \ge 1/2. 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 N of size at least \frac{2}{3}2^n there is a good element. In fact, they showed that in this case the average of a(x) over all elements is at least 1/2. For the average statement this result is best possible. Eccles improved it further and showed that the assertion of Frankl’s conjecture holds when |{\cal A}|\ge (2/3-1/104)2^n.

The new results by Ilan Karpas.

Here are three main results from Karpas’ paper two results on union closed families

Theorem 1: The assertion of Frankl’s conjecture holds when |{\cal A}| \ge 2^{n-1}.

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 \cal A  covers at most one set in \cal A.  (For this larger class the assertion of Frankl’s conjecture may fail when |{\cal A}|  < 2^{n-1})

Theorem 2: For some c>0, the assertion of Frankl’s conjecture holds when |{\cal A}|\ge (1-c) 2^{n-1}.

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 \cal A  that cover a set in \cal A  is at most 2^{n-1}. (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.

 

Posted in Combinatorics, Open problems | Tagged , , , | 2 Comments

Third third of my ICM 2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Update: Here is a combined version of all three parts: Three puzzles on mathematics computations and games. Thanks for the remarks and corrections. More corrections and comments welcome.

Dear all, here is the draft of the third third of my paper for ICM 2018. Corrections and comments are very welcome! This part is around the feasibility of quantum computers.

Posted in Combinatorics, Computer Science and Optimization, Open problems, Physics, Quantum | Tagged , | 3 Comments

Second third of my ICM 2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Update: Here is a combined version of all three parts: Three puzzles on mathematics computations and games. Thanks for the remarks and corrections. More corrections and comments welcome.

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.

Posted in Combinatorics, Computer Science and Optimization, Games | Tagged , , , , , | 6 Comments

First third of my ICM2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Update: Here is a combined version of all three parts: Three puzzles on mathematics computations and games. Thanks for the remarks and corrections. More corrections and comments 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.

 

Posted in Combinatorics, Computer Science and Optimization, Games, Updates | Tagged | 12 Comments

Preview: The solution by Keller and Lifshitz to several open problems in extremal combinatorics

Peter Frankl (right) and Zoltan Furedi

The news

A new paper by Nathan Keller and Noam Lifshitz settles several open problems in extremal combinatorics for wide range of parameters. Those include the three problems we mention next.

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 E_1,\dots ,E_{d+1} such that there exists a set S= \{v_1,\dots , v_{d+1}\} for which E_i\cap S = S \backslash \{v_i\} 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 t=1, 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

The paper by Keller and Lifshitz settles all these problems for a wide range of parameters! A subsequent paper by David Ellis, Nathan Keller, and Noam Lifshitz extends (among various other results) the range of parameters for the  Erdős-Sós problem even further.

Plans for posts

Michel Deza

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 

Posted in Combinatorics, Open problems, Updates | Tagged , , , , , , , | Leave a comment