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!

 

Advertisements
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 , , , , , , , | 1 Comment

Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture

Kazhdan’s Basic Notion Seminar is back!

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 v_1, v_2,\dots, v_m be points in \mathbb R^d, m \ge (r-1)(d+1)+1. Then there is a partition S_1,S_2,\dots, S_r of \{1,2,\dots,m\} such that \cap _{j=1}^rconv (v_i: i \in S_j) \ne \emptyset.

The Cascade Conjecture

Given a set X of points  in \mathbb R^d, X= \{ x_1,x_2,\dots ,x_n \} we let  T_r(X) be the set of  points in \mathbb R^d which belong to the convex hull of r pairwise disjoint subsets of X. (We may allow repetitions among the elements of X.) Thus, T_1(X) is just the convex hull of X.

Let \bar t_r(X)=\dim T_r(X)+1.

Radon’s theorem:  If \bar t_1(X) < |X| then \bar t_2(X)>0.

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

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

Conjecture 1: If \bar t_1(X)+ \bar t_2(X) < |X| then \bar t_3(X)>0.

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

Conjecture 2 (The Cascade Conjecture): If \bar t_1(X)+ \bar t_2(C) +\cdots+\bar t_r(X) < |X| then \bar t_{r+1}(X)>0.

Another formulation of Conjecture 2 is

The Cascade Conjecture: \sum_{i=1}^{|X|} \bar t_i(X) \ge |X|.

Of course, the cascade conjecture implies Tverberg’s theorem since given (r-1)(d+1)+1 points in \mathbb R^d, we have that \sum_{i=1}^{r-1} \bar t_i(X) \le (d+1)(r-1) < |X|, and therefore the conjecture implies that T_r(X) \ne \emptyset.

For the 5-point configuration on the left \bar t_1=3 and \bar t_2=2. For the configuration on the right \bar t_1=3 and \bar t_2=1. Indeed also \bar t_3=1

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

Posted in Combinatorics, Convexity, Open problems | Tagged , , | 4 Comments

My Very First Book “Gina Says”, Now Published by “World Scientific”

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 the World Scientific page, and here is its Amazon page (paperback)  and Amazon page (Kindle).

 

Posted in Academics, Combinatorics, Mathematics over the Internet, Physics, Updates | Tagged , | 3 Comments

Itai Benjamini: Coarse Uniformization and Percolation & A Paper by Itai and me in Honor of Lucio Russo

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 Lucio Russo, 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.

Lucio Russo

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

After-Dinner Speech for Alex Lubotzky

An after-dinner speech given on November  9, 2016*, on Alex Lubotzky’s 60th birthday conference: 60 faces to Groups.

 

As we all realized waking up this morning, today is a historic day*. It is the dinner day for Alex 60th‘s birthday conference, and I am thrilled to say a few words about Alex and to Alex. First let me send my love and my wife Mazi’s love to Alex and Yardena and all the family. A 60th birthday is a somber event, especially so when the birthday boy is younger than you, so I will be serious and try to move you and bring tears to your eyes,  rather than try to be funny and make you laugh. (This is a new experience for me.) I will leave the many funny stories I can tell about Alex to his 70th birthday. To be on the safe side I will write them down soon so not to forget them.

Early days

I don’t know how and when Alex and I first met. Perhaps it was in 1970 or 1971 when Ron Livne (at the time a high school student like me and Alex) invited me to Tel Aviv to their “math club”.   I remember meeting Alex in his home in the late 70s when we were both soldiers and he worked on his thesis and on the beautiful paper merging many different ideas and techniques using the “Golod-Shafarevich” theorem, along with Euler’s theorem for solving a well known problem. The paper appeared in the top journal of mathematics, the “Annals of Mathematics”, a rare achievement.

In 1985 I joined the Hebrew University as a faculty member, and Alex was already a professor there.  When I joined the department I was in awe of the extraordinary group of people, not only in terms of their mathematical achievements, but also when their scholarly nature, their personalities, activities and interests beyond math. This feeling paralyzed me and I hoped it would pass in a couple of months. It didn’t, and even today on the verge of retirement, this is still my feeling and it extends also to the amazing group of people we hired since.

Alex is a great mathematician

I should not tell you how  extraordinarily great a mathematician Alex is, and the mathematicians here can describe Alex’s work better than I can.  But to his family I want to mention a few “buzz words” reflecting some of Alex’s work:  “Ramanujan graphs”, and “powerful groups,” “subgroup growth” and the “Tau property” and the “Sandwich technique” (juggling between Tao and Kazhdan’s T-poperty) , “high dimensional expanders” (I taught with Alex four times a course on this topic. At the end I may understand what it’s about) and many, many more concepts.

Alex is a great friend

both to his close friends and to people who are more distant.  In many cases people enjoy listening to Alex’s life-wisdom (this was already the case when he was in his twenties, even when they were much older) and advice, and confide in him their most intimate experiences and dilemmas.  In these cases, the friendship relations are not quite symmetric, can we characterize what they are? It is not like the relationship you have with a father. Usually you do not want to hear words of wisdom about life from a parent and you certainly don’t want to share your intimate matters with them. It is more like the relation you have with a loving… grandfather. So you can say that Alex’s form of friendship was an early practice for grandfatherhood. Alex practiced being a grandfather all his life and now he can use his skills with his 16 and counting grandchildren. Alex is a great champion of grandchildren and I suppose he is starting to pressure his children to have grandchildren of their own about now.

Alex is an idealist

This is why he and Yardena settled in Efrat, this is why he worked hard to save and advance the “Israel Journal of Mathematics”,  and this is why he went into politics.  Alex joined politics in 95 and the Israeli parliament  after the 99 elections. (A major upset at the time. Commentators and polls predicted victory for one candidate but the other candidate won. This happens from time to time*.)  I remember talking with Hillel about hosting a farewell party for Alex. Hillel was surprised that a mathematical genius like Alex would join the parliament and I thought he would never come back.

Alex’ many virtues and two weaknesses as a leader

Alex had a lot of virtues and two weaknesses as a leader and a politician. Alex was very smart and he could understand the fine details as well as the large picture. He befriended and connected well with other politicians from all parties. In politics and administration just like in mathematics, he could identify the important problems and he went head on to tackle them. He is famous for the Beilin-Lubotzky convention for relations between orthodox and non-orthodox Jews and many other related issues. One of his weaknesses is that he is not malicious and does not appreciate the joy of malice.  As in mathematics, also in politics and in academic administration, he could identify the important problems and he went head on to tackle them. He was also the founder  of the committee for the status of women in the Israeli parliament.  [Here, in the lecture,  Alex corrected me and said that I am exaggerating and he was not the founder. But I made the mistake on purpose to make another point.]  …  Right, Alex was an active member of this committee, not the founder. It was founded 4 years earlier by Yael Dayan (Moshe Dayan’s daughter). This brings me to the second weakness of Alex as a politician. He is too honest. Most politicians and also a few mathematicians will not correct an undeserved credit.

Parents

Alex comes from a family of holocaust survivors and to a large extent regards himself as one. In my impression this accounts primarily for his immense gratitude for what he was blessed with, including the sweet life of a mathematician.  It is also related to a principle he has of never wasting food and never wasting time. We shared apartments quite a few times and he also refused to throw away food. (About Alex’s cooking wait 10 years.) Once I visited him and Yardena when they were renting a house filled with spoiled non kosher food that had been left by the owner and I secretly threw away most of it.  A  legacy from Alex’s father Issar is never to waste time. (I mean time when one is awake, this does not include sleeping, we already heard stories about Alex’s sacred afternoon sleep.) “A time being wasted is like a time being dead,” Alex once told me when he caught me playing a computer game at the computer room at Yale. (I wonder how this statement could be scientifically verified.) Since then I was careful to quickly move to a different screen when Alex entered the computer room.

You can read about the remarkable history of Alex’s  parents in WW2 in  Asael’s soon to be published second book.

Asael

And I want to conclude with mentioning Alex as a father to Asael, and how Alex and Yardena handles Asael’s grave injury in 2006. I remember Mazi and I had dinner with Alex and Yardena and Avi and Edna a day or two before Alex and Yardena got the news that Asael was injured and that  was in critical condition. This was a terrible ordeal and a difficult struggle, mainly for Asael but also for  his parents and the entire family. Asael, now a medical doctor as well as a researcher,  wrote his first book about his experiences, and has recently been translated to English.

Let me send again love from Mazi, myself and my children to Alex, Yardena and the family and wish Alex many more years. I haven’t talked about many joint adventures from the Jordan river to the Amazonas.   I promise to be funny ten years from now.

*At that day November 9, 2016, we woke up in the morning realizing that Donald Trump was the newly-elected President of the United States. Efim Zelmanov mentioned in his after dinner speech that Alex did not share the universal confidence that Trump will not be elected.

Posted in Conferences, Nostalgia, personal | Tagged | Leave a comment