To cheer you up in difficult times 4: Women In Theory present — I will survive

Posted on May 11, 2020 by

An amazing video

(Update, May18 2020). I failed to explain what WIT is and this may have caused some misunderstanding. Here is a description from the Simons Institute site.

“The Women in Theory (WIT) Workshop is intended for graduate and exceptional undergraduate students in the area of theory of computer science. The workshop will feature technical talks and tutorials by senior and junior women in the field, as well as social events and activities. The motivation for the workshop is twofold. The first goal is to deliver an invigorating educational program; the second is to bring together theory women students from different departments and foster a sense of kinship and camaraderie.”

Continue reading →

Posted in Academics, Combinatorics, Computer Science and Optimization, Convexity, Games, Philosophy, Poetry, What is Mathematics, Women in science | 12 Comments

To cheer you up in difficult times 3: A guest post by Noam Lifshitz on the new hypercontractivity inequality of Peter Keevash, Noam Lifshitz, Eoin Long and Dor Minzer

Posted on May 8, 2020 by

This is a guest post kindly contributed by Noam Lifshitz.

My short introduction: There is nothing like a new hypercontractivity inequality to cheer you up in difficult times and this post describes an amazing new hypercontractivity inequality.  The post describes a recent hypercontractive inequality by Peter Keevash, Noam Lifshitz, Eoin Long and Dor Minzer (KLLM) from their paper: Hypercontractivity for global functions and sharp thresholds. (We reported on this development in this post. By now, there are quite a few important applications.) And for Talagrand’s generic chaining inequality, see this beautiful blog post by Luca Trevisan.

Barry Simon coined the term “hypercontractivity” in the 70s.  (We asked about it here and Nick Read was the first to answer.) A few months ago Barry told us about the early history of hypercontractivity inequalities, and, in particular, the very entertaining story on William Beckner’s Ph. D. qualifying exam.

And now to Noam Lifshitz’s guest post.

Hypercontractivity on product spaces

Analysis of Boolean functions (ABS) is a very rich subject. There are many works whose concern is generalising some of the results on analysis of Boolean functions to other (product) settings, such as functions on the multicube {\left[m\right]^{n},} where {m} is very large. However, in some of these cases the fundemental tools of AOBF seem to be false for functions on the multicube {f\colon\left[m\right]^{n}\rightarrow\mathbb{R}.} However, in the recent work of Keevash, Long, Minzer, and I. We introduce the notion of global functions. These are functions that do not strongly depend on a small set of coordinates. We then show that most of the rich classical theory of AOBF can in fact be generalised to these global functions. Using our machinery we were able to strengthen an isoperimetric stability result of Bourgain, and to make progress on some Erdos-Ko-Rado type open problem.

We now discuss some background on the Fourier analysis on functions on the multicube {f\colon\left\{ 1,\ldots,m\right\} ^{n}\rightarrow\mathbb{R}.}

Derivatives and Laplacians

There are two fundemental types of operators on Boolean functions {f\colon\left\{ 0,1\right\} ^{n}\rightarrow\mathbb{R}.} The first ones are the discrete derivatives, defined by {D_{i}[f]=\frac{f_{i\rightarrow1}-f_{i\rightarrow0}}{2},} where {f_{i\rightarrow x}} denotes the we plug in the value {x} for the {i}th coordinate. The other closely related ones are the laplacians defined by {L_{i}f\left(x\right):=f\left(x\right)-\mathbb{E}f\left(\mathbf{y}\right),} where {\mathbf{y}} is obtained from {x} by resampling its {i}th coordinate.

The laplacians and the derivatives are closely related. In fact, when we plug in {1} in the {i}th coordinate, we obtain {L_{i}[f]_{i\rightarrow1}=D_{i}[f]}, and when we plug in {0} in it, we obtain {L_{i}[f]_{i\rightarrow0}=-D_{i}[f].}

The 2-norm of the {i}th derivative is called the {i}th influence of {f} as it measures the impact of the {i}th coordinate on the value of {f}. It’s usually denoted by {\mathrm{Inf}_{i}[f]}.

Generalisation to functions on the multicube

For functions on the multicube we don’t have a very good notion of a discrete derivative, but it turns out that it will be enough to talk about the laplacians and their restrictions. The Laplacians are again defined via {L_{i}f\left(x\right):=f\left(x\right)-\mathbb{E}f\left(\mathbf{y}\right),} where {\mathbf{y}} is obtained from {x} by resampling its {i}th coordinate. It turns out that in the continuous cube it’s not enough to talk about Laplacians of coordinate, and we will also have to concern ourselves with Laplacians of sets. We define the generalised Laplacians of a set {S} by composing the laplacians corresponding to each coordinate in {S} {L_{\left\{ i_{1},i_{2},\ldots,i_{r}\right\} }\left[f\right]:=L_{i_{1}}\circ\cdots\circ L_{i_{r}}\left[f\right].}

We now need to convince ourselves that these laplacians have something to do with the impact of {S} on the outcome of {f.} In fact, the following notions are equivalent

  1. For each {x,y\in\left[m\right]^{S}}we have {\|f_{S\rightarrow x}-f_{S\rightarrow y}\|_{2}<\delta_{1}}
  2. For each {x\in\left[m\right]^{S}} we have {\|L_{S}[f]_{S\rightarrow x}\|_{2}<\delta_{2},}

in the sense that if (1) holds then (2) holds with {\delta_{2}=C^{\left|S\right|}\delta_{1}} and conversely if (2) holds, then (1) holds with {\delta_{1}=C^{\left|S\right|}\delta_{2}.}

The main theme of our work is that one can understand global function on the continuous cube, and these are functions that satisfy the above equivalent notions for all small sets {S}.

Noise operator, hypercontractivity, and small set expansion

For {\rho\in\left(0,1\right),} the noise operator is given by {\mathrm{T}_{\rho}\left[f\right]\left(x\right)=\mathbb{E}f\left(\mathbf{y}\right)} when {\mathbf{y}} is obtained from {x} by independently setting each coordinate {\mathbf{y}_{i}} to be {\mathbf{x}_{i}} with probability {\rho} and resampling it with uniformly out of {\left\{ -1,1\right\} } otherwise. The process which given {x} outputs {\mathbf{y}} is called the {\rho}-noisy process, and we write {\mathbf{y}\sim N_{\rho}\left(x\right).}

The Bonami hypercontractivity theorem, which was then generalised by Gross and Beckner states that the noise operator {T_{\frac{1}{\sqrt{3}}}} is a contraction from {L^{2}\left(\left\{ 0,1\right\} ^{n}\right)} to {L^{4}\left(\left\{ 0,1\right\} ^{n}\right),} i.e.

\displaystyle \|\mathrm{T}_{\frac{1}{\sqrt{3}}}f\|_{4}\le\|f\|_{2}
for any function {f.}

One consequence of the hypercontractivity theorem is the small set expansion theorem of KKL. It concerns fixed {\rho\in\left(0,1\right)} and a sequence of sets {A_{n}\subseteq\{0,1\}^{n}} with {\left|A_{n}\right|=o\left(2^{n}\right).} The small set expansion theorem states that if we choose {\mathbf{x}\sim A_{n}} uniformly and a noisy {\mathbf{y}\sim N_{\rho}\left(\mathbf{x}\right),} then {\mathbf{y}} will reside outside of {A_{n}} almost surely.

The Generalisation to the multicube:

The small set expansion theorem and the hypercontractivity theorem both fail for function on the multicube that are of a very local nature. For instance, let {A} be the set of all {x\in\left\{ 1,\ldots,m\right\} ^{n},} such that {x_{1}} is {m.} Then {A} is of size {m^{n-1},} which is {o\left(m^{n}\right)} if we allow {m} to be a growing function of {n}. However, the {\rho}-noisy process from the set stays within the set with probability {\rho.} For a similar reason the hypercontractivity theorem fails as is for functions on {\left\{ 1,\ldots,m\right\} ^{n}.} However we were able to generalise the hypercontractivity theorem by taking the globalness of {f} into consideration.

Our main hypercontractive inequality is the following

Theorem 1.

\displaystyle \|\mathrm{T}_{\frac{1}{100}}f\|_{4}^{4}\le\sum_{S\subseteq\left[n\right]}\mathbb{E}_{\mathbf{x}\sim\left\{ 1,\ldots,m\right\} ^{m}}\left(\|L_{S}\left[f\right]_{S\rightarrow\mathbf{x}}\|_{2}^{4}\right).

The terms {\|L_{S}\left[f\right]_{S\rightarrow x}\|_{2}} appearing on the right hand side are small whenever {f} has a small dependency on {S} and it turns out that you have the following corrolary of it, which looks a bit more similar to the hypercontractive intequality.

 

Corollary 2.

Let {f\colon\left\{ 1,\ldots,m\right\} ^{n}\rightarrow\mathbb{R}}, and uppose that {\|L_{S}[f]_{S\rightarrow x}\|_{2}\le4^{\left|S\right|}\|f\|_{2}} for all sets {S.}

Then {\mathrm{\|\mathrm{T}_{\frac{1}{1000}}f\|_{4}\le\|f\|_{2}.}}

Finally, one might ask wonder why this globalness notion appears only when we look at large values of {m} and not when {m=2.} I think the corollary is a good explanation for that as {\|f\|_{2}^{2}\ge\left(\frac{1}{2}\right)^{\left|S\right|}\|f_{S\rightarrow x}\|_{2}^{2}} holds trivially for any Boolean function {f\colon\left\{ 0,1\right\} ^{n}\rightarrow\mathbb{R}.}

Posted in Analysis, Combinatorics, Computer Science and Optimization, Guest post, Poetry, Probability | Tagged , , , , | 3 Comments

Harsanyi’s Sweater

Posted on April 21, 2020 by

Today is the Holocaust Remembrance Day in Israel.  Here is a moving story from the  paper  about  John Harsanyi,  Harsanyi’s Sweater, by Robert J. Aumann.

It is 1944 in Budapest, and John is in his early twenties. He has been taken for deportation, with all that that implies. Arriving at the railroad station, he puts his knapsack down and wanders off a few yards, under the watchful eye of a guard. Then the guard is distracted for a moment, and John sees his chance to escape. But in the knapsack there is a beautiful, warm sweater, lovingly hand-knitted for John by his mother. John hesitates; should he — can he — abandon the sweater? After a moment, the urge to live takes over, and he slips away, taking refuge in a convent by previous arrangement. He survives the Holocaust to become the great thinker that he becomes. Hesitant, careful, open-minded, undogmatic — and in spite of that, or perhaps because of that — great.

Aumann himself  was born in Frankfurt, Germany, and fled at the age of eight to the United States with his family in, two weeks before the 1938 Kristallnacht.

I plan to mention this story in my game theory class this evening and also to mention five great game theorists named John.

Continue reading →

Posted in Games, Teaching | Tagged , | Leave a comment

To cheer you up in difficult times II: Mysterious matching news by Gal Beniamini, Naom Nisan, Vijay Vazirani and Thorben Tröbst!

Posted on April 19, 2020 by

Matching is one of the richest gold mines for ideas and results in mathematics, computer science and other areas.  Today I want to briefly tell you about a curious, surprising, mysterious, and cheerful recent result by Gal Beniamini and Noam Nisan and a subsequent work of Vijay Vazirani. It is a result that will cheer up combinatorialists on both sides of the aisle: graph theorists and researchers in extremal and probabilistic combinatorics as well as algebraic and enumerative combinatorialists.  (And it is related to query complexity, Eulerian lattices, Birkhoff’s polytope, a theorem of Lou Billera and Aravamuthan Sarangarajan, evasiveness, analysis of Boolean functions, and various other things.) At the end of the post I will remind you of a central problem in matching theory: that of extending Lovasz’ randomized algorithm for matching to general graphs. (Perhaps methods from algebraic combinatorics can help.)

I will start with sad news. John Horton Conway, an amazing mathematical hero,  passed away a few days ago. There are very nice posts on Conway’s work by Scott Aaronson (with many nice memories in the comments section), by Terry Tao, and by Dick Lipton and Ken Regan. And a moving obituary on xkcd with a touch of ingenuity of Conway’s style. (There is also a question on MO  “Conway’s less known results,” and two questions on the game of life (I, II).)

Another reading material to cheer you up is my paper: The argument against quantum computers, the quantum laws of nature, and Google’s supremacy claims. It is for Laws, Rigidity and Dynamics, Proceedings of the ICA workshops 2018 & 2019 in Singapore and Birmingham. Remarks are most welcome. (Update (May, 25 2020): An interesting discussion on Hacker news.)

Update: starting today, the algebraic combinatorics online workshop.  Here is the schedule for the first week, and for the second week.

 

Matching theory by Lovasz and Plummer is probably one of the best mathematics books ever written. 

Bipartite Perfect Matching as a Real Polynomial

Bipartite Perfect Matching as a Real Polynomial, by Gal Beniamini and Noam Nisan

Abstract: We obtain a description of the Bipartite Perfect Matching decision problem as a multilinear polynomial over the Reals. We show that it has full degree and (1-o_n(1))\cdot 2^{n^2}  monomials with non-zero coefficients. In contrast, we show that in the dual representation (switching the roles of 0 and 1) the number of monomials is only exponential in \Theta(n \log n)  Our proof relies heavily on the fact that the lattice of graphs which are “matching-covered” is Eulerian.

And here is how the paper starts

Every Boolean function f:\{0,1\}^n\to\{0,1\} can be represented in a unique way as a Real multilinear polynomial. This representation and related ones (e.g. using the {1,−1} basis rather than {0,1}– the “Fourier transform” over the hypercube, or approximation variants) have many applications for various complexity and algorithmic purposes. See, e.g., [O’D14] for a recent textbook. In this paper we derive the representation of the bipartite-perfect-matching decision problem as a Real polynomial.

Definition. The Boolean function BPM_n(x_{1,1},\dots,x_{n,n}) is defined to be 1 if and only if the bipartite graph whose edges are\{(i,j):x_{i,j}=1\} has a perfect matching, and 0 otherwise.

And here are the two main theorems regarding this polynomial and the polynomial for the dual representation:

(For the second theorem you need the notion of totally ordered bipartite graphs.)

And here is a nice picture!

A very interesting open problem is:

Problem: Can the Beniamini-Nisan results be extended to general (non-bipartite) graphs

This reminds me of an old great problem:

Problem: Does Lovasz’ randomized algorithm for matching extend to the non-bipartite case?

For both problems methods of algebraic combinatorics may be helpful.

An Extension by Vijay Vazirani and Thorben Tröbst

A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings, Thorben Tröbst, Vijay V. Vazirani

Abstract:

In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph G \subset K_{n,n} has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary non-negative weight function w on the edges of K_{n,n}, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph G \subset K_{n,n} contains one of these minimum weight perfect matchings.

Three more remarks about VVV

Three more VVV remarks: in the Tel Aviv theory fast fest three months ago (it seems like ages ago) Vijay Vazirani gave a lecture about matching. Here is the link to Vijay’s lecture, and to all plenary lectures.  At the end, I asked him how he explains that matching theory is such inexhaustable gold mine and Vijay mentioned the fact that a polynomial-time algorithm for the assignment problem (which is closely related to matching) was already found by Jacobi in 1890. (Unfortunately VJ’s inspiring answer was not recorded). A few years ago Vijay published a simplified proof of a fantastic famous result he first proved with Silvio Micaly 34 years earlier. And here is a most amazing story: a few years ago I went to the beach in Tel Aviv and I discovered Vijay swimming just next to me.  We were quite happy to see each other and Vijay told me a few things about matching, economics and biology. This sounds now like a truly surrealistic story, and perhaps we even shook hands.

 

 

 

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

Trees not Cubes! Memories of Boris Tsirelson

Posted on April 3, 2020 by

This post is devoted to a few memories of Boris Tsirelson who passed away at the end of January. I would like to mention that a few days ago graph theorist Robin Thomas passed away after long battle with ALS. I hope  to tell about Robin’s stunning mathematics in a future post.

Boris Tsirelson (1950 – 2020); Boris’ home-page, and Wikipedia. (More links, below.)

The title of the post is taken from the title of a very interesting 1999 paper by Boris Tsirelson and Oded Schramm: Trees, not cubes: hypercontractivity, cosiness, and noise stability

I was very sad and shocked to hear that Boris Tsirelson had passed away. Boris was one of the greatest Israeli mathematicians, and since 1997 or so we established mathematical connections surrounding several matters of common interest.  Here are a few memories.

Love for coding

1) One thing that Boris told me was that he loves to code. Being a “refusnik”, he could not get into Academia and (luckily) he could work as a programmer. And he told me that afterwards deciding what he liked more – programming or doing mathematical research – was no longer a trivial question for him.  Boris chose to go back to mathematical research, but he continued to enjoy programming, and when he needed it in his mathematical research, he could easily program.

Love for quantum

2) Another thing that Boris loved is “quantum”, the mathematics and physics of quantum mechanics and various connections to mathematics. Early on he proved his famous Tsirelson’s bound related to Bell’s inequalities, and later he was enthusiastic about the area of quantum computing. (And he learned it quickly, taught a course about it in 1997, and his 1997 lecture notes are still considered very useful.)

Black Noise and noise sensitivity

3) Perhaps the most significant mathematical connection between us was in the late 90s, and was centered around the theory of noise stability and noise sensitivity by Benjamini, Schramm and myself, which was closely related to a theory initiated by Boris Tsirelson and Anatoly Vershik. The translation between the different languages that we used and that Boris used was awkward, since the analog of Boolean functions that we studied was the “noise” that Boris studied, and the analog of noise sensitive Boolean functions in our language was “black noise” in Boris’s language. In any case, we had email discussions and we also met a few times with Itai and Oded regarding this connection.

Black Noise and noise sensitivity II

4)  Boris developed a very rich theory of black noise with relations to various areas of probability theory and operator algebras. He also found hypercontractivity that we used in our work quite useful to his applications, and also in this theory, he considered both classical and quantum aspects. I know only a little about Boris Tsirelson’s theory and its applications, but as far as tangent points with our Boolean interests are concerned, I can mention that Boris was enthusiastic by the result of Schramm and Stas Smirnov that percolation is a “black noise” and also that, in 1999, Boris and Oded Schramm wrote a paper whose title started with “Trees not cubes!”, presenting a different angle on this theory.

Tsirelson saw white noise (what we call noise stability) as manifesting “linearity” while “black noise” (what we call noise sensitivity) as manifesting “non-linearity”. Over the years, I often asked him to explain this to me.

Tsireslon’s Banach spaces

5) Geometry of Banach spaces is a very strong area in Israel so naturally I heard as a graduate student about “Tsirelson’s space” from 1974 and some subsequent developments in the 80s. Boris Tsirelson constructed a  Banach space that does not contain an imbedding of \ell_p or c_0.

Bible codes

6) My first personal connection with Boris was related to claims regarding a hidden Bible Code, and a 1994 paper claiming a statistical proof of the existence of these Bible codes. For many years my attitude was that these claims should be ignored, but around 1997, I changed my mind and did some work to see what was going on. Now, Boris kept a site linked in his homepage devoted to developments regarding the Bible Code claims. In this site Boris kindly reported about my first 1997 paper on the topic, my observation that the proximity of two reported p-values for the two Bible code experiments was “too good to be true”, and my interpretation that this suggests that the claimed results manifest naïve statistical expectations rather than scientific reality.  A few weeks later, Boris reported about a much stronger evidence (by McKay and Bar Nathan) against the Bible Code claims (they demonstrated codes of similar quality in Tolstoy’s “War and Peace”) and subsequently after some time he lost interest in this topic.

Quantum computing skepticism

6) In 2005 we had some correspondence and meetings regarding my quantum computing skepticism. In his first email he told me that my reference to “decoherence” seemed strange and I realized that I consistently referred to “entanglement” as “decoherence” and to “decoherence” as “entanglement”.

7) In his 1997 lecture notes on quantum computing (that I cannot find on the web, so I count on my memory), Boris addressed the concerns of early quantum computers skeptics like Rolf Landauer. He did not accept the analogy between quantum computing and analog computation, but he also regarded the analogy with digital computation as problematic. Rather, he regarded quantum information based on qubits as something (at least a priori) different from both these examples. (Update: I found one non-broken link to the lecture notes; indeed the subtitle of Chapter 9 is “neither analog nor digital”.)

A joke that I heard from Boris at that time

8) I remember that once when I asked him about some aspects of quantum fault tolerance he told me the following joke: A student is entitled to a special exam, he arrives at the professor’s office, is given three questions to answer and he fails to do so. He request and is granted a make-up exam two weeks later. When the student shows up at the office two weeks later the professor, who forgot all about it, gave him the same three questions. “This is extremely unfair”, said the student “you ask me questions that you already know that I cannot answer.”

Noise sensitivity and high energy physics

9) In 2006 I came up with the idea that noise sensitivity might be a great idea for physics. Knowing very little physics, I wrote a little manifesto with this idea and tried it, among other people, on Boris. As it turned out, Boris had the idea that noise sensitivity could add a useful modeling power to physics (especially high energy physics) well before that time. (And by 2006 he was already a bit skeptical regarding his own idea.) He also told me that one of the motivations of his 1998 paper with Tolya Vershik came from some mathematical ideas related to physics of the big bang. When I asked him if this was written somewhere in the paper itself, he answered: “Of course, not!”

Boris Tsirelson’s lecture at Oded’s memorial school

10) in 2009 we organized a meeting in memory of Oded Schramm and Boris gave a lecture related to the Schramm-Smirnov “percolation is black noise” result with a single theorem. And what was remarkable about it that it was that he presented a classical theorem with a quantum proof. You can find the videotaped lecture here  (And here are the slides. Boris never wrote up this result.) Following this lecture we had a short correspondence with Scott A. and Greg K. about quantum proofs to classical theorems. (Namely theorems that do not mention quantum in the statement).

Tsirelson’s problem

11) Our last correspondence in 2019 was about Thomas Vidick’s  Notices AMS article about Tsirelson’s problem. (This was a couple of months before the announcement of the solution.) Boris was pleased to hear about these developments, as he was regarding earlier developments in this area. He humorously refers to the history of his problem on his homepage and this interview.

12) People who knew Boris regarded him as a genius from a very early age, and former students have fond memories of his classes.

 

More resources:

Boris’s home page contains  “Museum to my courses” with many useful lecture notes; link to a small page on quantum computation with a link to Boris’ 1997 lecture notes on quantum computing.  Links to comments on some of Tsirelson’s famous papers. Tsirelson’s 1980 bound. Boris published papers, and his “self-published” papers.

Boris was a devoted Wikipedian and his Wikipidea user page is now devoted to his memory; Here is a great interview with Boris; A very nice memorial post on Freeman Dyson and Boris Tsirelson on the Shtetl Optimized; Tim Gowers explains some ideas behind Tsirelson’s space over Twitter; and here in Polymath2.

Below the fold some emails of interest from Boris, mainly where he explained to me various mathematics. (More can be found in this page.)

Continue reading →

Posted in Combinatorics, Obituary, Probability, Quantum | Tagged | 3 Comments

A small update from Israel and memories from Singapore: Partha Dasgupta, Robin Mason, Frank Ramsey, and 007

Posted on April 1, 2020 by

A small update about the situation here in Israel

Eight weeks ago I wrote that my heart goes out to the people of Wuhan and China, and these days my heart goes out to people in Italy, Spain, the US, Iran, France, the United Kingdom, Germany, Netherland and many other countries all over the world. Of course, I am especially worried about the situation here in my beloved country Israel, and let me tell you a little about it.

The pandemic started here late but it hit us pretty hard with 5,358 identified cases yesterday. Severe measures of social distancing were gradually introduced, and right now it is too early to tell if the pandemic is under control.

My part in this struggle is to stay at home. (Many Israeli scientists are making various endeavors and proposing ideas of various kind for fighting the disease and I salute them all for their efforts.) Like all of us I am very thankful to medical and other essential workers who are in the front-lines. As a scientist, I am especially impressed by the people from the Ministry of Health who manage the crisis and communicate with the public. They represent the very best we can offer in terms of science and medicine, decision making, gathering information, communicating with the public, and managing the crisis. In the picture below you can see three of the leaders – Moshe Bar Siman Tov (middle) Prof. Itamar Grotto (right) and Professor Sigal Sadetzki (left).

And now for today’s post

We had a tradition of sharing entertaining taxi-and-more stories and this post belongs to this category. We note that our highest quality story teller Michal Linial, a prominent Israeli biologist, is now involved in various aspects of the struggle against the disease. Our post today is part of a report by Michal Feldman and me on our experience from the ICA3 conferences in Singapore and Birmingham.

Partha Dasgupta, Robin Mason, Frank Ramsey, and James Bond

After hearing about him for many years, it was a great pleasure for both Michal Feldman and myself to finally meet Partha Dasgupta in person and to listen to his lecture. Partha who is the Frank Ramsey Professor of Economics at Cambridge was introduced by a person, who entered the room directly from an intercontinental flight, whom we did not know but who made a strong impression on us. He devoted part of his introduction to Frank Ramsey who was a mathematician, philosopher and economist, and who had made fundamental contributions to algebra and had developed the canonical model of saving in economic growth, before he died at the young age of 26. (And yes! also Ramsey’s theorem!)

Seeing the introducer, Robin Mason, three words came into our minds (more precisely two words, one repeated twice): “Bond, James Bond.”

Indeed, this has led to the following sequence of profound ideas:

1) Robin Mason is a perfect choice for a new generation James Bond.

2) The name “James Bond” is overused. “Robin Mason” is a perfect name to replace the name “James Bond”.

3) Espionage is a little obsolete and it lost much of its prestige and charm. Science and academia is the new thing! An international interdisciplinary academics is the perfect profession which, at present, deserves the prestige formely associated with espionage.

In summary, we came a full circle. Robin Mason is the perfect new choice for James Bond, “Robin Mason” is the perfect new name to replace the name “James Bond,” and Mason’s academic activities and title of Pro-Vice-Chancellor (International) are the perfect replacement for Bond’s activities and the title ‘007’.

(The option of Mason playing his role on the movies rather than in real life should be considered. ‘Q’ could be handy for science as well. )

Clique here for Robin’s introduction and Partha’s lectur

Posted in Algebra, Combinatorics, Conferences, Economics, Taxi-and-other-stories, Updates | Tagged , , , , , , , , | 2 Comments

Game Theory – on-line Course at IDC, Herzliya

Posted on March 29, 2020 by

Game theory, a graduate course at IDC, Herzliya; Lecturer: Gil Kalai; TA: Einat Wigderson,  ZOOM mentor: Ethan.

Starting Tuesday March 31, I am giving an on-line course (in Hebrew) on Game theory at IDC, Herzliya (IDC English site; IDC Chinese site).

In addition to the IDC moodle (course site) that allows IDC students to listen to recorded lectures, submit solutions to problem sets , etc., there will be a page here on the blog devoted to the course. Zoom link for the first meeting. https://idc-il.zoom.us/j/726950787

A small memory: In 1970 there was a strike in Israelis’ high schools and I took a few classes at the university. One of these classes was Game theory and it was taught by Michael Maschler. (I also took that trimester a course on art taught by Ziva Meisels.) Our department at HUJI is very strong in game theory, but once all the “professional” game theorists retired, I gave twice a game theory course which I enjoyed a lot and it was well accepted by students. In term of the number of registered students, it seems that this year’s course at IDC is quite popular and I hope it will be successful.

The first six slides of the first presentation

(Click to enlarge)

Game Theory 2020, games, decisions, competition, strategies, mechanisms, cooperation

The course deals with basic notions, central mathematical results, and important examples in non-cooperative game theory and in cooperative game theory, and with connections of game theory with computer science, economics and other areas.

What we will learn

1. Full information zero-sum games. The value of a game. Combinatorial games.

2. Zero-sum games with incomplete information. Mixed strategies, the Minmax Theorem and the value of the game.

3. Non cooperative games, the prisoner dilemma, Nash equilibrium, Nash’s theorem on the existence of equilibrium.

4. Cooperative games, the core and the Shapley value. Nash bargaining problem, voting rules and social choice.

Background material:

Game theory alive by Anna Karlin and Yuval Peres (available on-line).

In addition I may use material from several books in Hebrew by Maschler, Solan, Zamir, by Hefetz, and by Megiddo (based on lectures by Peleg). (If only I will manage to unite with my books that are not here.) We will also use a site by Ariel Rubinstein for playing games and some material from the book by Osborne and Rubinstein.

Requirement and challenges:

  • Play, play, play games, in Ariel Rubinshtein site and various other games.
  • Solve 10 short theoretical problem set.
  • Final assignment, including some programming project that can be carried out during the semester.
  • Of course, we will experience on-line study which is a huge challenge for us all.

Games and computers

  • Computer games
  • Algorithms for playing games
  • algorithmic game theory:
    • Mechanism design
    • Analyzing games in tools of computer science
    • Electronic commerce
  • Games, logic and automata: there will be a parallel course by Prof. Udi Boker

I still have some difficulty with the virtual background in ZOOM.

Posted in Combinatorics, Computer Science and Optimization, Economics, Games, Rationality, Teaching | Tagged , | 2 Comments

TYI44: “What Then, To Raise an Old Question, is Mathematics?”

Posted on March 26, 2020 by

“The argument is carried out not in mathematical symbols but in ordinary English, there is no obscure or technical terms. Knowledge of calculus is not presupposed. In fact, one hardly need to know how to count. Yet any mathematician will immediately recognize the argument as mathematical.” 

Test your intuition 44: what is the argument? who and where wrote this view about “what is mathematics”.

Zero-knowledge answers please.

Comments regarding this view itself and on “what is mathematics” are also welcome.

(Here are other posts on “What is mathematics.”)

 

 

PS. The last facetious sentence was omitted in the Journal version of the paper. (Indeed it was a good decision to take it out.) PPS Yannai Gonczarowski pointed out the the journal formulation is also rather condescending (perhaps even more so) towards non-mathematicians.

Posted in Test your intuition, What is Mathematics | Tagged , | 12 Comments

Kelman, Kindler, Lifshitz, Minzer, and Safra: Towards the Entropy-Influence Conjecture

Posted on March 22, 2020 by

Let me briefly report on a remarkable new paper by Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra, Revisiting Bourgain-Kalai and Fourier Entropies. The paper describes substantial progress towards the Entropy-Influence conjecture, posed by Ehud Friedgut and me in 1996. (See this blog post from 2007.)

Abstract: The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is o(logn), however, both results become useless when the total influence of the function is ω(logn). The only case in which this logarithmic barrier has been broken for an interesting class of function was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of S_n.

In this paper, we revisit the key ideas of the Bourgain-Kalai paper. We prove a new general inequality that upper bounds the correlation between a Boolean function f and a real-valued, low degree function g in terms of their norms, Fourier coefficients and total influences.

Some corollaries of this inequality are:

  1. The Bourgain-Kalai result.
  2. A slightly weaker version of the Fourier-Entropy Conjecture. More precisely, we prove that the Fourier entropy of the low-degree part of f is at most O(I[f]log^2 I[f]), where I[f] is the total influence of f. In particular, we conclude that the Fourier spectrum of a Boolean function is concentrated on at most 2O(I[f]log^2 I[f]) Fourier coefficients.
  3. Using well-known learning algorithms of sparse functions, the previous point implies that the class of functions with sub-logarithmic total influence (i.e. at most O(\log n/(\log \log n)2)) is learnable in polynomial time, using membership queries.

Our theorem on influence under symmetry. From my videotaped lecture on Jean Bourgain. See this post about Jean Bourgain.

A few remarks:

A) Given a Boolean function f:\{-1,1\}^n\to \{-1,1\} let f=\sum_{S \subset \{1,2,\dots ,n\}}\hat f(S)W_S be its Fourier-Walsh expansion. (Here W_S(x_1,x_2,\dots ,x_n)=\prod_{i\in S}x_i.) The total influence I(f) of f is described by

I(f)=\sum {S \subset \{1,2,\dots ,n\}}\hat f^2(S)|S|.

The spectral entropy E(f) of f is defined by

E(f)=\sum_{S \subset \{1,2,\dots ,n\}}\hat f^2(S) \log (\hat f^2(S)).

The entropy-influence conjecture (here called the Fourier-entropy conjecture) asserts that for some universal constant C

I(f) \ge C E(f).

B) One interesting feature of the conjecture is that the RHS is invariant under arbitrary linear transformations of \{-1,1\}^n (regarded as an n-dimensional vector space) while the LHS is invariant only to permutations of the variables.

C) My paper with Jean Bourgain, Influences of variables and threshold intervals under group symmetries, describes lower bounds on total influences for Boolean function invariant under certain groups of permutations (of the variables). Those results are stronger (but more restrictive) than what the Entropy/influence conjecture directly implies. (This was overlooked for a while.) The new paper gives (much hoped for, see below) simpler proofs and stronger results compared to those in my paper with Jean Bourgain.

D) Ryan O’Donnel wrote about Bourgain and some of his contributions to the analysis of Boolean functions:

“I spent close to 5 years understanding one 6-page paper of his (“On the distribution of the Fourier spectrum of Boolean functions”), and also close to 10 years understanding a 10-page paper of his (the k-SAT sharp threshold ‘appendix’). If anyone’s up for a challenge, I’m pretty sure no one on earth fully understands the second half of his paper “Influences of variables and threshold intervals under group symmetries” with Kalai (including Gil 🙂 )”

It looks that by now we have pretty good understanding and even some far-reaching progress regarding all three papers that Ryan mentioned. (It is unclear if we can hope now for an exponential spread of understanding for Bourgain’s proofs.)

 

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , , | Leave a comment

Or Ordentlich, Oded Regev and Barak Weiss: New bounds for Covering Density!

Posted on March 18, 2020 by

Barak Weiss lectured about his breakthrough results with Or Ordentlich, and Oded Regev, at a Simons Institute workshop: Lattices: Geometry, Algorithms and Hardness.

It is a famous problem what is the densest (or, most efficient) packing of unit balls in Euclidean n-dimensional spaces and, of course, you can ask the same questions for other convex bodies. A sort of a dual problem, also famous, is the question of the most efficient covering the n-dimensional Euclidean space by balls or by translates of other convex bodies.

A very basic insight is that covering is much more efficient than packing. Can you explain the reason for that? The only thing that came up to my mind was that convex sets are roundish from the outside but not from the inside which makes it easier to cover with them.

But how efficiently can we cover the n-dimensional Euclidean space with translates of a convex body $K$?

C.A. Rogers with coauthors had some very fundamental results regarding covering (and packing) in the 50s and 60s. Or Ordentlich, Oded Regev and Barak Weiss have made a terrific improvement for one of the main questions in this area. They showed that for every convex set K, you can find a lattice L  of determinant 1, and r>0  such that rK+L = \mathbb R^n and

{\rm vol} (rK) \le cn^2.

The best earlier upper bound was n^{\log \log n}.

One surprising aspect of the proof is the use of finite field Kakeya-type questions. Since the breakthrough by Zeev Dvir, many people had hopes for applications from the finite fields results to the Euclidean setting (in particular, to the Euclidean Kakeya problem itself) and it is rare to see such applications. The proof here relies on results by  Dvir, Kopparty, Saraf, Sudan, and Lev. The Ordentlich-Regev-Weiss paper is not yet on the arXiv but the lecture gives a good picture about the results and the proofs.

The definition of the covering density of L with respect to a convex body K

The definition of the covering density of K

Old results for the Euclidean ball

Old results for general convex bodies

The first main result

 

The required finite field Kakeya theorem.

Posted in Combinatorics, Computer Science and Optimization, Geometry | Tagged , , | 2 Comments