# NatiFest is Coming

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

# Real Analysis Introductory Mini-courses at Simons Institute

The Real Analysis ‘Boot Camp’ included three excellent mini-courses.

Inapproximability of Constraint Satisfaction Problems (5 lectures)
Johan Håstad (KTH Royal Institute of Technology)

Unlike more traditional ‘boot camps’ Johan rewarded answers and questions by chocolates (those are unavailable for audience of the video).

Starting from the PCP-theorem (which we will take as given) we show how to design and analyze efficient PCPs for NP-problems. We describe how an efficient PCP using small amounts of randomness can be turned into an inapproximability result for a maximum constraint satisfaction problem where each constraint corresponds to the acceptance criterion of the PCP. We then discuss how to design efficient PCPs with perfect completeness in some interesting cases like proving the hardness of approximating satisfiable instances of 3-Sat.

We go on to discuss gadget construction and how to obtain optimal reductions between approximation problems. We present Chan’s result on how to take products of PCPs to get hardness for very sparse CSPs and give some preliminary new results using these predicates as a basis for a gadget reduction.

Finally we discuss approximation in a different measure, and in particular the following problem. Given a (2k+1)-CNF formula which admits an assignment that satisfies k literal in each clause, is it possible to efficiently find a standard satisfying assignment?

Analytic Methods for Supervised Learning​ (4 lectures)
Adam Klivans (University of Texas, Austin)

(Lecture I, Lecture II, Lecture III, Lecture IV) additional related lecture by Adam on Moment matching polynomials.

In this mini-course we will show how to use tools from analysis and probability (e.g., contraction, surface area and limit theorems) to develop efficient algorithms for supervised learning problems with respect to well-studied probability distributions (e.g., Gaussians). One area of focus will be understanding the minimal assumptions needed for convex relaxations of certain learning problems (thought to be hard in the worst-case) to become tractable.

Introduction to Analysis on the Discrete Cube (4 lectures)
Krzysztof Oleszkiewicz (University of Warsaw)

(Lecture I, Lecture II, Lecture III, Lecture IV) Here are the slides for the lecture which contain material for 1-2 additional lectures.

The basic notions and ideas of analysis on the discrete cube will be discussed, in an elementary and mostly self-contained exposition. These include the Walsh-Fourier expansion, random walk and its connection to the heat semigroup, hypercontractivity and related functional inequalities, influences, the invariance principle and its application to the Majority is Stablest problem. The mini-course will also contain some other applications and examples, as well as several open questions.

# Simons@UCBerkeley

Raghu Meka talking at the workshop

I spend the semester in Berkeley at the newly founded Simons Institute for the Theory of Computing. The first two programs demonstrate well the scope of the center and why it is needed. One program on real analysis in computer science seems to demonstrate very theoretical aspects of the theory of computing and its relations with pure mathematics. The second program is on big data analysis, a hot topic in statistics, machine learning and many areas of science, technology, and beyond. And one surprise is that there is a lot in common to these two areas. Next semester, there will be one special program on quantum Hamiltonian complexity which again may seem in the very far-theoretic side of TOC as it largely deals with computational classes between NP and QMA, (far beyond what we seem relevant to real-life), and yet this study is related to classical efficient algorithms in condensed matter physics, with connections to real-life physics and technology. The other special program in Spring 2014 is on evolution (evolutionary biology and TOC)!

The program I am mainly involved with is on real analysis in computer science. It started with a very successful and interesting workshop Real Analysis in Testing, Learning and Inapproximability. This week (Spet 9-13) there is a “Boot camp on real analysis” with three mini-courses. The amount of activity in the center and around it is too vast to allow any sort of live-blogging but I do hope to share with you a few things over the semester. Two things for now: Kalvin Lab, the building where the institute is located is beautiful! The video coverage of talks, (both the live streaming and the video archives) is of very high quality (reflecting both the excellent equipment and the people that operate it).

It is always a special feeling to witness the first days of the academic year whether it is in Israel or in the US. Many students returning to school, many first-year students, at times, accompanied by their proud parents, and quite a few colleagues who share this excitement and are just as surprised on how younger and younger these students are becoming (and some other colleagues, who this year are proud parents themselves). This time, I spent a few days in Yale and saw the excitement there, and then continued with the same “high” mood on the first days of school here at Berkeley.

# Poznań: Random Structures and Algorithms 2013

Michal Karonski (left) who built Poland’s probabilistic combinatorics group at Poznań, and a sculpture honoring the Polish mathematicians who first broke the Enigma machine (right, with David Conlon, picture taken by Jacob Fox).

I am visiting now Poznań for the 16th Conference on Random Structures and Algorithms. This bi-annually series of conferences started 30 years ago (as a satellite conference to the 1983 ICM which took place in Warsaw) and this time there was also a special celebration for Bela Bollobás 70th birthday. I was looking forward to  this first visit to Poland which is, of course, a moving experience for me. Before Poznań I spent a few days in Gdańsk visiting Robert Alicki. Today (Wednesday)  at the Poznań conference I gave a lecture on threshold phenomena and here are the slides. In the afternoon we had the traditional random run with a record number of runners. Let me briefly tell you about very few of the other lectures: Update (Thursday): A very good day, and among others a great talk of Jacob Fox on Relative Szemeredi Theorem (click for the slides from a similar talk from Budapest) where he presented a joint work with David Conlon and Yufei Zhao giving a very general and strong form of Szemeredi theorem for quasi-random sparse sets, which among other applications, leads to a much simpler proof of the Green -Tao theorem.

### Mathias Schacht

Mathias Schacht gave a wonderful talk  on extremal results in random graphs (click for the slides) which describes some large recent body of highly successful research on the topic. Here are two crucial slides, and going through the whole presentation can give a very good overall picture.

### Vera Sós

Vera Sós gave an inspiring talk about the random nature of graphs which are extremal to the Ramsey property and connections with graph limits. Vera presented the following very interesting conjecture on graph limits. We say that a sequence of graphs $(G_n)$ has a limit if for every k and every graph H with k vertices the proportion in $G_n$ of induced H-subgraphs among all k-vertex induced subgraphs tend to a limit. Let us also say that $(G_n)$ has a V-limit if for every k and every e the proportion in $G_n$ of induced subgraphs with k vertices and e edges among all k-vertex induced subgraphs tend to a limit. Sós’ question: Is having a V-limit equivalent to having a limit. This is open even in the case of quasirandomness, namely, when the limit is given by the Erdos-Renyi model G(n,p). (Update: in this case V-limit is equivalent to limit, as several participants of the conference observed.) Both a positive and a negative answer to this fundamental question would lead to many further (different) open problems.

### Joel Spencer

Joel Spencer gave a great (blackboard) talk about algorithmic aspects of the probabilistic method, and how existence theorems via the probabilistic method now often require complicated randomized algorithm. Joel mentioned his famous six standard deviation theorem. In this case, Joel conjectured thirty years ago that there is no efficient algorithm to find the coloring promised by his theorem. Joel was delighted to see his conjecture being refuted first by Nikhil Bansal (who found an algorithm whose proof depends on the theorem) and then later by Shachar Lovett and  Raghu Meka (who found a new algorithm giving a new proof) . In fact, Joel said, having his conjecture disproved is even more delightful than having it proved. Based on this experience Joel and I are now proposing another conjecture: Kalai-Spencer (pre)conjecture: Every existence statement proved by the probabilistic method can be complemented by an efficient (possibly randomized) algorithm. By “complemented by an efficient algorithm” we mean that there is an efficient(polynomial time)  randomized algorithm to create the promised object with high probability.  We refer to it as a preconjecture since the term “the probabilistic method” is not entirely well-defined. But it may be possible to put this conjecture on formal grounds, and to discuss it informally even before.

# Joram’s Memorial Conference

Joram Lindenstrauss 1936-2012

This week our local Institute of Advanced Study holds a memorial conference for Joram Lindenstrauss. Joram was an immensely powerful mathematician, in terms of originality and conceptual vision, in terms of technical power, in terms of courage to confront difficult problems, in terms of clarity and elegance, and in terms of influence and leadership. Joram was a dear teacher and a dear colleague and I greatly miss him.

One nice anecdote that I heard in the conference was about the ceremony where Joram received the Israel Prize. When he shook the hand of the Israeli president, Itzhak Navon, Navon told him: “If you have a little time please drop by to tell me sometime what Banach spaces are.” Next Joram shook the hand of prime minister Menchem Begin who overheard the comment and told Joram: “If you have a little time please do not drop by to tell me sometime what Banach spaces are.”

Physics, Computer Science, Mathematics, and Foundations’
views on quantum information

Inauguration conference for the Quantum Information Science Center (QISC),
Hebrew university of Jerusalem

Update: The news of our conference have made it to a big-league blog.

Update (July 2013): QStart was a very nice event- there were many interesting talks, and the speakers made the effort to have lectures accessible to the wide audience while discussing the cutting edge and at times technical matters.Streaming video of the talks is now available.

# A Few Mathematical Snapshots from India (ICM2010)

Can you find Assaf in this picture? (Picture: Guy Kindler.)

In my post about ICM 2010 and India I hardly mentioned any mathematics. So here are a couple of mathematical snapshots from India. Not so much from the lectures themselves but from accidental meetings with people. (Tim Gowers extensively live-blogged from ICM10.) First, the two big problems in analysis according to Assaf Naor as told at the Bangalore airport waiting for a flight to Hyderabad.  Next, a lecture on “proofs from the book” by Günter Ziegler. Then, some interesting things I was told on the bus to my hotel from the Hyderabad airport by François Loeser, and finally what goes even beyond q-analogs (answer: eliptic analogs) as explained by Eric Rains. (I completed this post  more than two years after it was drafted and made major compromises on the the quality of my understanding of the things I tell about. Also, I cannot be responsible today for the 2-year old attempts at humor.)