Tag Archives: Nati Linial

NatiFest is Coming

Nati Poster_Final

The conference Poster as designed by Rotem Linial

A conference celebrating Nati Linial’s 60th birthday will take place in Jerusalem December 16-18. Here is the conference’s web-page. To celebrate the event, I will reblog my very early 2008 post “Nati’s influence” which was also the title of my lecture in the workshop celebrating Nati’s 50th birthday.

Nati’s Influence

When do we say that one event causes another? Causality is a topic of great interest in statistics, physics, philosophy, law, economics, and many other places. Now, if causality is not complicated enough, we can ask what is the influence one event has on another one.  Michael Ben-Or and Nati Linial wrote a paper in 1985 where they studied the notion of influence in the context of collective coin flipping. The title of the post refers also to Nati’s influence on my work since he got me and Jeff Kahn interested in a conjecture from this paper.

Influence

The word “influence” (dating back, according to Merriam-Webster dictionary, to the 14th century) is close to the word “fluid”.  The original definition of influence is: “an ethereal fluid held to flow from the stars and to affect the actions of humans.” The modern meaning (according to Wictionary) is: “The power to affect, control or manipulate something or someone.”

Ben-Or and Linial’s definition of influence

Collective coin flipping refers to a situation where n processors or agents wish to agree on a common random bit. Ben-Or and Linial considered very general protocols to reach a single random bit, and also studied the simple case where the collective random bit is described by a Boolean function f(x_1,x_2,\dots,x_n) of n bits, one contributed by every agent. If all agents act appropriately the collective bit will be ‘1’ with probability 1/2. The purpose of collective coin flipping is to create a random bit R which is immune as much as possible against attempts of one or more agents to bias it towards ‘1’ or ‘0’. Continue reading

A Beautiful Garden of Hypertrees

We had a series of posts (1,2,3,4) “from Helly to Cayley” on weighted enumeration of Q-acyclic simplicial complexes. The simplest case beyond  Cayley’s theorem were Q-acyclic complexes  with n vertices, {n \choose 2} edges, and {{n-1} \choose {2}} triangles. One example is the six-vertex triangulation of the real projective plane. But here, as in many other places, we are short of examples.

Nati Linial,  Roy Meshulam and Mishael Rosenthal wrote a paper with very surprising examples of Q-acyclic simplicial complexes called “sum complexes”. The basic idea is very simple: The vertices are \{1,2,\dots , n\}. Next you pick three numbers a,b and c and consider all the triples i,j,k so that i+j+k is either a or b or c. And let’s assume that n is a prime.

So how many triangles do we have? A fraction of 3/n of all possible triangles which is what we want ({{n-1} \choose {2}}).

If the three numbers form an arithmetic progression then the resulting simplicial complex is collapsible. In all other cases it is not collapsible. The proof that it is Q-acyclic uses a result of Chebotarëv on Fourier analysis. (So what does Fourier analysis have to do with computing homology? You will have to read the paper!) The paper considers the situation in all dimensions.

What about such combinatorial constructions for Q-homology spheres?

Nati’s Influence

When do we say that one event causes another? Causality is a topic of great interest in statistics, physics, philosophy, law, economics, and many other places. Now, if causality is not complicated enough, we can ask what is the influence one event has on another one.  Michael Ben-Or and Nati Linial wrote a paper in 1985 where they studied the notion of influence in the context of collective coin flipping. The title of the post refers also to Nati’s influence on my work since he got me and Jeff Kahn interested in a conjecture from this paper.

Influence

The word “influence” (dating back, according to Merriam-Webster dictionary, to the 14th century) is close to the word “fluid”.  The original definition of influence is: “an ethereal fluid held to flow from the stars and to affect the actions of humans.” The modern meaning (according to Wictionary) is: “The power to affect, control or manipulate something or someone.”

Ben-Or and Linial’s definition of influence

Collective coin flipping refers to a situation where n processors or agents wish to agree on a common random bit. Ben-Or and Linial considered very general protocols to reach a single random bit, and also studied the simple case where the collective random bit is described by a Boolean function f(x_1,x_2,\dots,x_n) of n bits, one contributed by every agent. If all agents act appropriately the collective bit will be ‘1’ with probability 1/2. The purpose of collective coin flipping is to create a random bit R which is immune as much as possible against attempts of one or more agents to bias it towards ‘1’ or ‘0’. Continue reading