The Logarithmic Minkowski Problem

NYC-origin

The logarithmic origin of Manhattan

We are spending the fall semester in NYC at NYU and yesterday* I went to lunch with two old friends Deane Yang and Gaoyong Zhang. They told me about the logarithmic Minkowski problem, presented in the paper The logarithmic Minkowski problem by Károly Böröczky, Erwin Lutwak, Deane Yang and Gaoyong Zhang (BLYZ). (See also this paper by BLYZ.) We will get to the problem after a short reminder of Minkowski’s theorem.

The Discrete Minkowski problem: Find necessary and sufficient conditions on a set
of unit vectors u_1,\dots, u_m in \mathbb R^n and a set of real numbers a_1,\dots,a_m > 0 that will guarantee the existence of an m-faced polytope in \mathbb R^n whose faces have outer unit normals u_1,\dots, u_m and corresponding face-areas a_1,\dots,a_m .

Minkowski himself gave a complete solution in 1911, a necessary and sufficient condition is that the following relation holds:

a_1u_1 + a_2u_2 + \cdots a_mu_m=0.

If a polytope contains the origin in its interior, then the cone-volume
associated with a face of the polytope is the volume of the convex hull of the face
and the origin.

The Discrete logarithmic Minkowski problem: Find necessary and sufficient conditions on a set
of unit vectors u_1,\dots, u_m in \mathbb R^n and a set of real numbers a_1,\dots,a_m > 0 that will guarantee the existence of an m-faced polytope in \mathbb R^n whose faces have outer unit normals u_1,\dots, u_m and corresponding cone-volumes a_1,\dots,a_m .

The problem was solved by BLYZ for the centrally symmetric case. It is related to a lot of deep mathematics (convexity, valuations, Brunn-Minkowski theory, analysis, PDE… perhaps combinatorics).  In both cases there are continuous versions that are a little harder to formulate.

 

20211102_134826

With Deane Yang and Gaoyong Zhang

* Actually it was four weeks ago and since then we had another lunch and Deane explained some recent issues that are discussed/debated in the American mathematical community with a lot of excitement. (I did not really understand.) (Actually there was a thorough and nice discussion on Facebook a year ago about double-blind refereeing which seems a small corner of the large excitement.)

Posted in Convex polytopes, Convexity, Updates | Tagged , , , | 1 Comment

Face to face talks and recorded videotaped introductions

Many face to face activities are now resuming. Last week I took part in a great conference on high dimensional expanders at the Simons Foundation, I recently gave real life talks with large audiences also in U. Chicago and Rutgers, and next week I talk here at the Courant colloquium. In these times when people hesitate about attending in-door activities and some of these activities are restricted, I decided to prepare a 20-minute introduction for every in-person talk, and in this post I will share with with my recent three introductory talks. The lectures themselves (blackboard-lectures in all these cases) are self-contained and do not depend on the introductory videos. The Zoom era also offers new opportunities like a talk I gave a few weeks ago in the John-Conway spirited seminar at LUMS, Lahore, Pakistan.

An invitation to the NYU Courant colloquium

Title: Noise sensitivity, Fourier, and the quantum computer puzzle

Speaker: Gil Kalai, Hebrew University of Jerusalem, Reichman University and NYU

Location: Warren Weaver Hall 1302

Date: Monday, November 8, 2021, 3:45 p.m.

Synopsis: I will start with the analysis of Boolean functions and the related theory of noise stability and noise sensitivity. Next, I will discuss the sensitivity of noisy intermediate scale quantum (NISQ) computers, and explain why NISQ computers are computationally primitive and incapable of demonstrating neither “quantum computational advantage” nor the harder task of quantum error-correction. Finally, I will briefly discuss recent papers claiming a huge quantum computational advantage for NISQ systems which appears to be in sharp contrast with my theory.

Introductory video: click here.;  Here is the presentation; Here is the colloquium page.

I plan to give a blackboard talk. The title is very similar to my ICM 2018 lecture except that a lot has happened since 2018.

Two other introductory videotaped:

  1. Helly-type problems with emphasis on the cascade conjecture
  2. Problems about convex polytopes (see this post)

My lecture in Lahore

My lecture in LUMS, was entitled “A word devoid of quantum computers with emphasis on predictability and free will”. Here is the presentation and here is the seminar page with links to the video recording (and to other interesting lectures). The lecture is related to this post on quantum computers and free will.

sl19
 
 

The last slide of the NYU introductory presentation. (I plan a blackboard lecture.)

At the end I gave a presentation. Here are the slides for the full representation. Apparently it was the first live Courant colloquium after almost two years.

courantPicture: Vlad Vicol

courant-deane

Picture: Deane Young

Posted in Combinatorics, Physics, Probability, Quantum, Updates | Leave a comment

Alef’s Corner: QED (two versions)

Untitled - 9 September 2021 09.34

QED:  Version 2

 

 

Untitled - 8 September 2021 17.04

Posted in Art, What is Mathematics | Tagged | 1 Comment

Dream a Little Dream: Quantum Computer Poetry for the Skeptics (Part II, The Classics)

Quantum poetry for the skeptics had long roots, and, also here, Peter Shor along with Jennifer Shor had a pioneering role. Volker Strassen’s response is the earliest poem known to me on the skeptics’ side. We will start with Jennifer and Peter’s poem and to Volker Strassen’s response and move on to other heroic quantum poem-writers Daniel Gottesman and John Preskill. (Here is a link to Part I in the series.)

Classic Quantum Poetry and Art

Jennifer and Peter Shor and Volker Strassen (before 1998)

(source)

Here is what Peter wrote:

” My wife and I wrote the following for a poetry contest by Science News. It didn’t win, so I posted it on my web page.

If computers that you build are quantum,
Then spies of all factions will want ’em.
Our codes will all fail,
And they’ll read our email,
Till we’ve crypto that’s quantum, and daunt ’em.

Jennifer and Peter Shor

When he introduced me at the 1998 International Congress of Mathematicians, Prof. Volker Strassen recited my limerick, and added a reply:

To read our E-mail, how mean
of the spies and their quantum machine;
Be comforted though,
they do not yet know
how to factorize twelve or fifteen.

Volker Strassen”

Early sonnet and poetic art work by Daniel Gottesman

(Here is the link Quantum Error Correction Sonnet.)

Quantum Error Correction Sonnet
By Daniel Gottesman

We cannot clone, perforce; instead, we split
Coherence to protect it from that wrong
That would destroy our valued quantum bit
And make our computation take too long.

Correct a flip and phase – that will suffice.
If in our code another error’s bred,
We simply measure it, then God plays dice,
Collapsing it to X or Y or Zed.

We start with noisy seven, nine, or five
And end with perfect one. To better spot
Those flaws we must avoid, we first must strive
To find which ones commute and which do not.

With group and eigenstate, we’ve learned to fix
Your quantum errors with our quantum tricks.

February 25, 1999

Above: Daniel’s artistic view of quantum error correction

 John Preskill

John is a prolific poet, I am not aware of poetry he wrote specifically for quantum computer skeptics (It’s  never too late for that, go John!), but he has several other quantum poems. (See also below for a poetic slogan by John.) His anyon poem

Anyon, Anyon (click for the full poem.)

Starts with

Anyon, anyon, where do you roam?
Braid for a while before you go home.

Here is a recent haiku by John

Qubits very cold
A dil fridge holds them gently
Mustn’t decohere

#QuantumHaiku

And a 2001 poem quantum cryptography. (The link contains some attempts to find rhymes for “Daniel Gottesman”.)

Quantum Cryptography

Alice said to her friend Eve,
“Why do you practice to deceive?
You know I need to talk to Bob.
Without that I won’t have a job.

“Bob can’t know where my note has been.
He thinks that you are listening in.
He wonders if it’s safe enough
For me to send him secret stuff.

“And Bob’s right not to trust you, Eve,
With quantum tricks stuffed up your sleeve.
But he thinks we can freeze you out,
With quantum tricks we’ve learned about.

“With quantum states, what we achieve
Defeats whatever you conceive.
So even Bob has to believe
That you can’t hear us, can you Eve?”

John Preskill, November 1, 2001

 

Poetic classic quantum slogans and quotes

John Preskill: slogan for quantum error correction (classic, 1997)

We can fight entanglement with entanglement

Daniel Gottesman: slogan for quantum error correction (1999, see sonnet above)

With group and eigenstate, we’ve learned to fix
Your quantum errors with our quantum tricks.

Scott Aaronson: (source)  (repeatedly in various forms since 2012 or so.)

The number one application of quantum computers is to disprove Gil Kalai who said they are impossible.

Gil Kalai (2013):

The importance of quantum error-correction to physics is similar to the importance of non-deterministic computation to the theory of computing. Their importance is that they cannot be achieved.

(source)

John Martinis (2014) (source)

ECH ≠  MNP

ECH stands for “Experimentally Crazy Hard” and refers to monumental experimental physics achievements. MNP refers to “Maximum Nature Publications”.

(Martinis led the Sycamore experiment, and Nature is the journal where the sycamore paper appeared.)

David Deutsch

Quantum computation is a distinctively new way of harnessing nature. It will be the first technology that allows useful tasks to be performed in collaboration between parallel universes.

To me quantum computation is a new and deeper and better way to understand the laws of physics, and hence understanding physical reality as a whole.

 

Quantum computers as seen by Michel Dyakonov, myself, and Alexander Vlasov

Motivation

Robert Alicki and I climbing the mountain of quantum computers “because it is not there” (2014).

Posted in Art, Computer Science and Optimization, Controversies and debates, Music, Poetry, Quantum | Leave a comment

Giving a talk at Eli and Ricky’s geometry seminar. (October 19, 2021)

One of my favorite seminars in the world is the Courant Institute (NYU) Geometry seminar that Eli Goodman and Ricky Pollack started in the 1980s (I think). On Tuesday October 19, I will give a seminar, details follow.

Jacob E. Goodman

Jacob Eli Goodman (1933-2021). Eli (as we knew him) was a dear friend and a great geometer. He  passed away a few days ago.  

Talking at Eli and Ricky’s seminar

This semester I am visiting NYU and was invited to give the NYU geometry seminar that for many years was run by Eli Goodman and Ricky Pollack. It was always one of my favorite seminars and since the mid eighties I have given there many lectures. At least twice, my lectures were on Halloween day and I came to them with a costume. My story about a taxi ride to give a seminar lecture appeared here and was even translated to Russian. Janos Pach, who joined the organizers sometime in the 90s, once gave the craziest introduction I ever received. Some lectures had large attendance, while in others there were only a few participants. Once I gave a lecture where some participants were slowly leaving, while others were sleeping. I noticed one participant in deep slumber. “At least he will stay,” I comforted myself, but then when I next wrote on the blackboard and turned back to the audience, he disappeared. 

In recent years the seminar was promoted and was also named the NYC geometry, seminar and is run by Boris Aronov, Adam Sheffer, and Joe Malkevich.  My talk will take place on Tuesday October 19, 2021. Initially the invitation was for a zoom lecture as many participants (and speakers) prefer zoom, and NYU has strict rules about visitors attending talks. But I preferred a face-to-face event and proposed to send a 15-minute introductory video and then give the lecture in an informal discussion manner in a park near NYU. At the end, we decided on a sort of mixed event: So here is the plan:

  1. The lecture’s title is “Open problems about convex polytopes”
  2. Here is a 15 minute introductory video
  3. We will meet for an informal discussion in front of Warren Weaver Hall (231 Mercer Street) on the Mercer Street side, around noon. The plan is to discuss open problems about convex polytopes in the nearby garden.
  4. We will then meet for a hybrid seminar lecture; the Zoom talk will start at 2pm as usual, I and others who attend in person will head to Baruch College; the talk will take place in room 6-215 (6th floor). All are welcome to join. You just need to be fully vaccinated and fill this out in advance: https://app.cleared4.org/self-registration;
  5. Click here To join via zoom (at 14:00) Meeting ID: 997 2747 4288 Passcode: m^2/3n^2/3

(Please feel free to join any subset from 2) , 3) and 4).) 

Two of the problems that I will mention in the lecture (at least) are closely related to joint work by Eli and Ricky. 

Eli was also a gifted composer and here is a beautiful performance by Craig Ketter of his wonderful piece “variations on a theme of Beethoven”.

Update: I learned that the seminar started in 1980, and that Erwin Lutwak and Joe Malkevitch were along with Ricky and Eli founding members of this seminar.

Update: The various parts of the lecture worked nicely; Thanks to Joe, Boris and Adam for inviting me.

Posted in Combinatorics, Convex polytopes, Geometry | Tagged | 1 Comment

To cheer you up in difficult times 32, Annika Heckel’s guest post: How does the Chromatic Number of a Random Graph Vary?

This is a guest post kindly written by Annika Heckel. We first reported about Annika Heckel’s breakthrough in this post. A pdf version of this post can be found here.

Pick an {n}-vertex graph uniformly at random. Pick another one. Will it have the same chromatic number? Or if not, how different are their chromatic numbers likely to be if {n} is large?

The chromatic number of a random graph is a random variable, so what we are really asking is: Is this random variable essentially deterministic? That is, is the weight of the distribution concentrated on one value, or on just a few values which are close together?

Until recently we did not know whether or not this is the case. In this blog post I’ll describe a new result showing that, at least for infinitely many {n}, the chromatic number of a random {n}-vertex graph is not concentrated on fewer than about {\sqrt{n}} consecutive values.

Random graphs

A uniform {n}-vertex graph is generated by the random graph {G_{n, 1/2}} where we include each possible edge independently with probability {1/2}, and more generally we can ask about the chromatic number {\chi(G_{n,p})} of {G_{n,p}}.

Results about {\chi(G_{n,p})} generally fall into one of two categories: Can we find (i) upper and lower bounds for its typical value, and (ii) bounds on how much it varies about this typical value?

The typical value

On (i), we have the well-known 1987 result of Bollobás who showed that, with high probability (whp), {\chi(G_{n, 1/2}) \sim n / (2 \log_2 n)}. This was improved and generalised several times, the current best bounds are from 2016:

\displaystyle (1)~~~~\chi(G_{n,1/2}) = \frac{n}{2 \log_2 n - 2\log_2 \log_2 n - 2} + o \left( \frac{n}{\log^2 n} \right) \text{ whp.} \ \ \ \ \

(I am writing out this result because it will become important when talking about question (ii) later.)

Upper concentration bounds

So how about the width of the distribution of {\chi(G_{n,p})} — what is the length of the shortest interval (or rather sequence of intervals) which is likely to contain {\chi(G_{n,p})}?

Of course (1) is already a weak concentration type result, giving an explicit such interval of length {o \left( \frac{n}{\log^2 n} \right)}. However, it turns out that if we don’t have to specify the interval, we can do a lot better.

The starting point for question (ii) is the classic 1987 result of Shamir and Spencer, who showed that for any function {p(n)}, {\chi(G_{n,p})} is whp contained in some sequence of intervals of length about {\sqrt{n}}. If {p \rightarrow 0} quickly enough, however, much sharper concentration holds: in 1997, Alon and Krivelevich reduced the interval length to only {2} in the case p<n^{-1/2-\varepsilon}. So here the chromatic number behaves almost like a deterministic function; almost all of the weight of the distribution is on two consecutive values.

The opposite question

In view of strong results showing that the chromatic number is sharply concentrated, in the late 1980s Bollobás raised the following question (later popularized by him and Erdős): Can we find any examples where χ(G_{n,p}) is not very sharply concentrated? This is trivially true for p = 1 − 1/(10n) (as noted by Alon and Krivelevich), but how about non-trivial examples, and what about the most natural special case, p = 1/2?

This question remained open for quite some time, for a simple reason: while we have a number of standard tools to prove upper bounds on the concentration of a random variable (for example the martingale concentration argument of Shamir and Spencer), we have few ways of giving lower concentration bounds. (Unless we can work out the entire approximate distribution, for example by proving asymptotic normality.)

A lower bound for concentration

I will sketch the main ideas needed for the following result:

Theorem 1 (H. 2019; H., Riordan 2021). Let ε > 0, and let {[s_n, t_n]} be a sequence of intervals such that {\chi(G_{n, 1/2}) \in [s_n, t_n]} whp. Then there are infinitely many values {n} such that

\displaystyle \ell_n := t_n - s_n \ge n^{1/2 - \varepsilon}.

Of course we can also replace {\varepsilon} with some function {o(1)} which tends to {0} slowly. Up to this {o(1)}-term, the lower bound matches Shamir and Spencer’s upper bound.

A word of caution: The theorem only says that there are some {n} so that {\chi(G_{n, 1/2})} is not very sharply concentrated. It does not tell us what these values {n} are, and no bound is given for the other {n}. In fact, we do not believe the conclusion of Theorem 1 is true for every {n} — more on this later!

Basic proof strategy

The proof needs two ingredients:

(1) A (weak) concentration type result

A result that says that, whp, {|\chi(G_{n, 1/2}) - f(n)| \le \Delta(n)} for some well-behaved function {f(n)} and an error term {\Delta}. Here, {\Delta} is much larger than the scale on which we are trying to prove non-concentration. We also need a lower bound on the slope of {f}, \displaystyle \frac{\mathrm{d}}{\mathrm{d} n}f(n) > \frac{1}{\alpha}+ \delta, where we will specify {\alpha=\alpha(n)} later.

(2) A coupling result

A coupling that shows that, for {n} and some slightly larger {n'}, {\chi(G_{n,1/2})} and {\chi(G_{n', 1/2})} are close together. More specifically, we need a coupling of {G_{n, 1/2}} and {G_{n', 1/2}} with {n'=n+\alpha r} (with {\alpha} as above) so that with probability at least {1/4}, say, \displaystyle \chi(G_{n', 1/2}) \le \chi(G_{n, 1/2}) + r.

Now suppose {[s_n, t_n]} is a sequence of intervals as in Theorem 1. As shown in the picture, we now know that {\chi(G_{n, 1/2})} is concentrated around a function {f(n)} with slope more than {1/\alpha} (blue area), but it also follows from the coupling that the slope between the concentration intervals (red lines) is at most {r/(\alpha r) = 1 / \alpha}.

intervals2-color-withlabels

If all intervals were short, then as we increase {n}, eventually this would lead to a contradiction: an interval {[s_n, t_n]} lying outside the blue area. So there must be at least one long interval.

Working out the numbers, under certain reasonable conditions there is an interval of length about {\alpha \delta r}. We will have {\alpha} of order {\log n}, {\delta} of order {1/\log^2 n} and {r} close to {\sqrt{n}}.

Independence number and large independent sets

So what’s the function {\alpha(n)}? This turns out to be the independence number of {G_{n,1/2}}, that is, the size of the largest independent vertex set. Matula and independently Bollobás and Erdős proved that the independence number of {G_{n, 1/2}} behaves almost deterministically: for most {n}, whp it takes an explicitly known deterministic value {\alpha = \alpha(n) \approx 2 \log_2 n}.

What does this have to do with {\chi(G_{n, 1/2})}? Each colour class in a colouring (i.e. all the vertices of one particular colour) is independent, because neighbouring vertices must be coloured differently. So there are at most {\alpha(n)} vertices in each colour class, and therefore {\chi(G_{n, 1/2}) \ge n / \alpha(n)}. We saw in (1) that this easy lower bound is in fact asymptotically correct.

We call an independent set of size {\alpha} an {\alpha}-set. It is plausible that the optimal colouring of {G_{n, 1/2}} contains all or almost all {\alpha}-sets as colour classes. Roughly speaking, this is because the expected number of {k}-colourings is dominated by colourings with as many {\alpha}-sets as possible.

Let {X_\alpha} count the number of {\alpha}-sets, then it can be shown that {X_{\alpha}} is approximately Poisson with mean {\mu_\alpha=n^\theta}, where {\theta = \theta(n) \in [o(1),1+o(1)]}. In particular, {X_\alpha} typically varies by about {\sqrt{\mu_\alpha}}. If we must use all {\alpha}-sets in the colouring, then it seems plausible that the overall number of colours we end up with also varies by roughly this amount. (Divided by {\log n}, as we will see in a moment.)

The weak concentration result

Luckily we already have a suitable estimate for {\chi(G_{n, 1/2})} in (1). Writing {f(n)} for this estimate, then for most {n},

\displaystyle \frac{\mathrm{d}}{\mathrm{d} n}f(n) = \frac{1}{\alpha} + \Theta \left(\frac{1}{\log^2 n} \right).

So what is the effect of having one extra {\alpha}-set in {G_{n, 1/2}}? Using one colour for this {\alpha}-set, we need to colour the remaining {n-\alpha} vertices. So one extra {\alpha}-set should save us about

\displaystyle \alpha \left(\frac{\mathrm{d}}{\mathrm{d} n}f(n)\right) -1 = \Theta \left(\frac{1}{\log n} \right)

colours. So {\sqrt{\mu_\alpha}} extra {\alpha}-sets should reduce {\chi(G_{n,1/2})} by about {\sqrt{\mu_\alpha} /\log n}.

The coupling

We construct the coupling in the following way: take {n'=n+r\alpha} vertices (we will pick {r} later). Choose {r} vertex sets of size {\alpha} uniformly at random and make them independent sets, and then include every edge outside these {r} {\alpha}-sets independently with probability {1/2}. secondattempt-edges-color-withlabels

The inner graph {G} on {n} vertices is simply {G_{n,1/2}}. It is also clear that, if {G'} is the outer graph on {n'} vertices, then

\displaystyle \chi(G') \le \chi(G) + r.

This is because any colouring of {G} can be extended to a colouring of {G'} by giving a new colour to each of the {r} {\alpha}-sets.

The trouble is that {G'} is not distributed as {G_{n', 1/2}} — we have disturbed the distribution by planting the {r} {\alpha}-sets. The key point is that, as long as {r} is not too large — less than the standard deviation {\sqrt{\mu_\alpha}} of {X_\alpha} — then {G'} and {G_{n', 1/2}} are very similar. This makes sense on an intuitive level: the random graph doesn’t `notice’ the extra {\alpha}-sets as long as we have planted fewer than the natural fluctuation {\sqrt{\mu_\alpha}}.

So we let {r=o(\sqrt{\mu_\alpha})} (or in fact {r=\varepsilon \sqrt{\mu_\alpha}} works). For the formal proof, we bound the total variation distance of the two random graph models.

Tying it all together

The two ingredients above can be combined to show that for every {n}, there is some nearby {n^*} with concentration interval length {\ell_{n^*} \ge C \sqrt{\mu_\alpha (n^*)} / \log n^*}, with {\mu_\alpha (n^*) \approx \mu_\alpha}. If we pick {n} so that {\mu_\alpha} is close to {n}, Theorem 1 follows.

How close to Shamir and Spencer’s upper bound {\sqrt{n}} can we actually get? At the moment, nothing better than {n^{1/2-o(1)}} for some unspecified function {o(1)} is possible. The main bottleneck is the size of the error term {\Delta=o(n / \log^2 n)} in (1).

Konstantinos Panagiotou and I have been working on an improved estimate for {\chi(G_{n, 1/2})} in a paper we are currently writing up. Assuming this result, Oliver Riordan and I can prove that there are infinitely many {n} such that

\displaystyle \ell_n \ge \frac{\sqrt{n}\log \log n}{\log^ {3} n }.

The best upper concentration bound for {p=1/2} is {\sqrt{n}/\log n}, due to Alon.

Which of these is closer to the truth? We conjecture that, for the worst case {n}, the width of the distribution of {\chi(G_{n, 1/2})} matches our lower bound up to the constant. However, the concentration behaviour seems to be very different for different {n}, as described below.

The Zigzag conjecture

Let {g(n)} be the standard deviation of {\chi(G_{n, 1/2})}. We already gave a heuristic argument that {g(n) \ge C \sqrt{\mu_\alpha}/\log n}, coming from fluctuations in the number {X_\alpha} of {\alpha}-sets.

There is another conjectured lower bound coming from fluctuations in {X_{\alpha-1}}, the number of {(\alpha-1)}-sets, namely

\displaystyle g(n) \ge C \frac{\sqrt{n}}{\sqrt{\mu_\alpha}\log^{5/2} n}.

The Zigzag conjecture, made recently by Bollobás, Heckel, Morris, Panagiotou, Riordan and Smith, states that at least for most {n}, {g(n)} is essentially the maximum of these two lower bounds. Ignoring {n^{o(1)}}-terms, we have the following simplified statement.

Define {\theta} by letting {\mu_\alpha = n^\theta}. Let \displaystyle \lambda = \max \left(\frac{\theta}{2}, \frac{1-\theta}{2} \right).

Then, if {g(n)} denotes the standard deviation of {\chi(G_{n, 1/2})}, \displaystyle g(n) = n^{\lambda + o(1)}.

conjecture-color-withlabels

It is not hard to show that the function {\lambda(n)} `zigzags’ between {1/4+o(1)} and {1/2+o(1)}, roughly linearly in {\log n}, as shown in the picture (the orange and blue lines are the lower bounds coming from {\alpha}– and {(\alpha-1)}-sets, respectively).

There’s a detailed heuristic explanation of the conjecture in the paper. We also think that we have a pretty good idea of the behaviour of {g(n)} at the extreme points. In particular, we believe that in the `worst case’, {g(n)} is of order {n^{1/2} \log \log n /\log^3 n}, while in the `best case’ it’s of order {n^{1/4} / \log^{7/4} n}.

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

To Cheer You Up in Difficult Times 31: Federico Ardila’s Four Axioms for Cultivating Diversity

Todos Cuentan (Everybody counts)

In a beautiful NAMS 2016 article Todos Cuentan: Cultivating Diversity in Combinatorics, Federico Ardila put forward four thoughtful axioms which became a useful foundation for Ardila’s own educational and outreach efforts, and were offered as a pressing call to action for the academic community as a whole. (See also here, and here.)

Here are the axioms

Axiom 1. Mathematical talent is distributed equally among different groups, irrespective of geographic, demographic, and economic boundaries.

Axiom 2. Everyone can have joyful, meaningful, and empowering mathematical experiences.

Axiom 3. Mathematics is a powerful, malleable tool that can be shaped and used differently by various communities to serve their needs.

Axiom 4. Every student deserves to be treated with dignity and respect

Of course, these axioms extend even further when you replace “mathematics” with other academic areas and also with “art”, “music”, “sport”, “literature” “business” “politics”, etc.

My view is quite close to Federico’s view.

Two remarks: First, I learned from Ardila’s paper, interesting mathematical results that I did not know about. One result is by Anastasia Chavez and Nicole Yamzon about Dehn-Somerville’s relations that we mentioned here several time (I, II, III, IV). Chavaz and Yamzon’s paper is The Dehn-Sommerville Relations and the Catalan Matroid. The Dehn-Somervilles relation asserts that the affine dimension of f-vectors of simplicial d-polytopes is [d/2]. We can ask which [d/2] coordinates of the f vector determine the other coordinates. (If I had to guess I would have said that every subsets of [d/2] coordinates spanned the other coordinates; but this is incorrect.) It turns out that the answer is related to very interesting combinatorics.

Second, I was quite surprised that I came across Ardila’s paper and axioms only now, almost five years after the paper was published. I could certainly referred to Ardila’s axioms had I known about them in a few tedious (while important) discussions on the matter, and in a short (here, shortened further) letter to the NAMS editor that I wrote on the subject in 2019.

Dear editor,
In my opinion, diversity is an important social and academic value, the pursuit of which can also be an important means for academic excellence. One reason we need to pay special attention to diversity is that there are various mechanisms against it, which in and of themselves are harmful to academic life and excellence, such as dominance and, at times, even bullying by members of majority/power groups. On this and other issues, academic institutions have the right and duty to form academic policies and pursue them, and also the obligation to allow free debate about these policies.

—Gil Kalai
Hebrew University of Jerusalem and IDC, Herzliya
(Received November 28, 2019)

Followup discssions on FB (I,II,III,IV)

Posted in Academics, Combinatorics, What is Mathematics, Women in science | Tagged , | 12 Comments

Dream a Little Dream: Quantum Computer Poetry for the Skeptics (Part I, mainly 2019)

Stars shining bright above you,
Night breezes seem to whisper “I love you”
Birds singing in the sycamore tree.
Dream a little dream.
(YouTube)

Greetings from NYC everybody!

Peter Shor pioneered (Nov 26, 2019) quantum poetry for the skeptics over Twitter. (We will come shortly to Peter’s poem.) On November and December 2019, there were many very nice contributions all over social media by Renan Gross, John Dowling, Nidit Nanda, ⟨dl|yonge|mallo⟩, Alfred Marcel Bruckstein, Kenneth Regan, Ehud Friedgut, Avi Wigderson, and others. Keep the quantum poems coming! Of course, the poems should be taken with humor. Let me start with a beautiful poem by Renan Gross and small a taste of poems from 2020-2021. Stay tuned for a post on classic quantum poems since the late 90’s, and for a post with the latest 2020/2021 vintage.

Renan Gross

My favorite poem is by Renan Gross.

Renan: “I can’t quite say I’m a skeptic, but I do like to play with words. Here is my contribution:”

Bit by bit as if on cue,
The beat of qubits slowly grew
To fit the neverending queue
Of them who bit more they could chew.
Yet there is hope.

For quantum queries queer with wonder
Quibbling quarrels break asunder,
Quenching squabbles, quitting squander –
Quite quaint quest for us to ponder!
Shall we not try?

Google‘s (impressive) Hebrew translate for the first stanza of Renan’s poem

,טיפה אחר טיפה כאילו נמצא בתור
פעימות הקוויטיטים גדלו לאט
כדי להתאים לתור שלא נגמר
.מתוכם שנשכו יותר (מש)הם יכלו ללעוס
.עם זאת יש תקווה

Here is Renan Gross Hebrew poem “לבחורה שיושבת מלפני בקומבינטוריקה” (“A la fille qui est assise devant moi en combinatoires“: from a grand poetry slam festival.)

Taste of 2020/2021 poems

asdf (source, 2021) (try singing it in your heart)

Detecting interference,
Cryogenics for maintaining coherence,
Birds tweeting from the Sycamore tree,
Dream of solving BQP.

More: a bosonsampling advantage poem for the skeptics by Peter Shor;  A professional excellent quantum rap for the skeptics Qubits – Baba Brinkman; a punk-rock song about BosonSampling by Mark Wilde.

Six-word stories

Ehud Friedgut

For sale: quantum computer. Never used.

Another 6-word story (mine) with a rhyme (of some sort)

Michelson and Morley weren’t Google‘s employees.

Google: Not about quantum, about life itself

If for supremacy Google chooses to cut corners 
We are all in deep shit

(Great rhyme, isn’t it)

And now, ladies and gentlemen

Shor’s pioneering poem

This wave of poems for quantum computers skeptics was pioneered by Peter Shor.

Peter’s introduction to his poem

With the Google quantum supremacy paper, the claims that quantum computers can’t possibly work keep on coming. It is becoming clear that reasoned arguments will not stop them.

I don’t think illogical poetry is going to work, either. But it’s fun to write

Peter Shor

A Poem for Quantum Computing Skeptics

Quantum computers may at first sight seem
To be impossible. How dare we dream
Of solving problems that else would take more time
Than has passed since the cosmos’s Big Bang!

But is there any reason to believe
The universe computes the way we do?
Nature is profligate with galaxies.
Why shouldn’t her extravagance hold true
For other things? Why mightn’t she achieve
Prodigious feats of computation, too?

My short response

Understanding nature and ourselves is a worthy dream
Requiring no interaction with the supreme

My long response

A poem for supreme-power dreamers of the good kind

Nature’s prodigious feats of computation enable us to dream
Dreams of  a supreme power that watch us and care 
Dreams of a supreme morality and a supreme kind of justice
Dreams of God and Heaven

Dreams of supreme kind of computation,
Of solving problems that else would take more time
Than has passed since the cosmos’s Big Bang!

Dreams of amazing shortcuts in our difficult slow quest
For understanding and meaning

Dreams that give us solace and hope
Don’t let those transform into deception, hate, and malice.

Beware of turning into a supremacy dreamer of the bad kind.

Beware of turning into a supremacy dreamer of the bad kind

Jacob Blumoff’s praise poem for Peter’s poetry vision

Quantum Twitter, said Peter Shor, needs
More poems filling our feeds.
A great proposition–
Nay a super position–
Another field owes him its seeds.

Alfred Marcel Bruckstein

There is a guy called Shor
Who knows what qc’s are for
When he encounters Gil
Who says qc’s never will
Do what they promise to do
He writes some poems too!

(source, below The Three Package-Monsters by Alfred Marcel Bruckstein.)

AMB

Limericks

Jon Dowling

A quantum computer from Google,
Turned the Church-Turing thesis to strudel.
And yet there remain,
Many doubting this claim,
And we lash all of them with wet noodles.

(source)

My response to Jon

A quantum computer from Google,
Turned the Church-Turing thesis to strudel.
And yet there remain,
Many doubting this claim:
“It’s just a stone-less stone-soup with noodles”

Jon Dowling was an eminent quantum physicist who passed away in 2020. See here for some personal memories of John.

⟨dl|yonge|mallo⟩

Claimed a skeptic named Gil
“Quantum computers can never be built!”
So we showed him a Sycamore
But that just caused him to bicker more
“That device is too noisy still!” 

(I’m just kidding @GilKalai we love you.)

(source)

My response

Claimed a skeptic named Gil
“Quantum computers can never be built!”
So we showed him a Sycamore
But that just caused him to bicker more
“That device is too noisy still!” 

(I’m not kidding.)

Vidit Nanda

Said Peter to all detractors
Naysayers, you two-bit actors
From one to sixteen
My quantum machine
Every integer it factors.

(I’m so sorry @PeterShor1)

(source)

Kenneth Regan – “My perspective”:

“It From Bit” we once proclaimed;
but now the Bit has bit the dust
from whizzing quantum chips that gamed
coherence to evade the trust
that the Word drove creation’s hour:
Mother Nature fully lexical.
Why not evolve us that same power?
It is a status most perplexical

(source)

Avi Wigderson

“There once was a quantum computer
Whose pet was a five-legged hamster …”
So Peter and Gil
Their grandchildren will
Tell “…happy they lived ever after”

I suggest a kids’ chorus saying “yeah, right” or “sure, sure”, after each line

2019 Poetic quantum slogans

Greg Kuperberg: Google’s supremacy experiment

This is quantum David vs classical Goliath, in the extreme, —

(source)

Gil Kalai: about Google’s supremacy demo

This is a very very very delicate issue

(source Supremacy panel discussion 46:54-47:00)

delicate4

David Yonge-Mallo

Peter Shor issued a challenge to the quantum computing community to write some poems. Below is my contribution.

Claimed a skeptic named Gil
“Quantum computers can never be built!”
So we showed him a Sycamore
But that just caused him to bicker more
“That device is too noisy still!”

Despite assurances evidential
Some disbelieved quantum’s potential
If to doubt you’re inclined
Please do keep in mind
Neven’s law is doubly exponential

There once were some Googlers quantum
Who made some qubits to flaunt them
But their paper got leaked
And rival IBM peeked
And wrote a blog post to taunt them

Skeptics say and doubters preach
Quantum computing is out of reach
But I know some nice folks
Who’ll convince you it’s no hoax
If you ever visit Venice Beach

Why don’t you try quantum annealing?
The promised speedups are quite appealing
But you’ve got to suppress those terrors
The Hamiltonian control errors
Or your speedups will hit a ceiling

I’m paying a huge electrical bill
To keep atoms at near zero chill
In a giant fridge with no door
And what is it all for?
I just want to impress John Preskill

Microsoft bet on fermions Majorana
Cuz it sounds cool and they wanna
But their critics sigh:
“Their hopes are too high
They might as well smoke—”

Wait, I’m stumped, what rhymes with “Majorana” and can be smoked?

(GK: I suppose that David refers to “cucumber”.)

My Anthem for the term HQCA

There is an interesting debate about the term “quantum supremacy.” I always did not like the term because of its connotations and also because supremacy refers to a large advantage over a large spectrum and here we are talking about a huge advantage for specific purposes. Since I don’t expect it to be demonstrated, the name will serve some educational purpose regarding other sort of supremacy. Anyway, I wanted to use my large influence on the QC community to propose the term HQCA (“Huge Quantum Computational Advantage”).

Here is a song in support of HQCA.

I said young friend, pick yourself from the ground
I said, young friend, ’cause you’re in a new town
There’s no need to be unhappy.

Young friend, there’s now a computer for you.
I said, young friend, when you’re short on CPU.
You can use it, and I’m sure you will find
Many ways to have a good time.

Its fun to have the H-Q-C-A
Its even fun to break the R–S-A

With entanglement at will, you can compute a quantum field
You can do chemistry as much as you feel

Its fun to have the H-Q-C-A
From NISQ up all the way

You can factor huge numbers, you can build a boson-sampler
You can defeat each and every scrambler

Young friend, are you listening to me?
I said, young friend, what do you want to be?
Never mind Gil, you can make your dreams real.…
But you got to know this one thing
NP-hard problems HQCA doesn’t compute by itself
I said, young friend, put your SAT back on the shelf
And just go there, to the H-Q-C-A
I’m sure they can help you today

“Young friend” was chosen for the sake of inclusiveness and diversity.

Dream a little dream: Ozzie Nelson; Wayne KingDoris DayElla Fitzgerald & Louis Armstrong; Anita HarrisRobbie Williams; JOAN CHAMORRO QUINTET & ANDREA MOTIS; FRANKIE LAINE; Lily Allen and Robbie Williams. Mama Cass Elliot.

YMCA: Village People; Just Dance 2014; Christopher on America’s Got Talent

Posted in Art, Music, Poetry, Quantum | Tagged | 3 Comments

To Cheer you up in difficult times 30: Irit Dinur, Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes Constructed Locally Testable Codes with Constant Rate, Distance, and Locality

The Simons Institute announces an October 6, 2021 lecture by Irit Dinur with the result in the title. This is a wonderful breakthrough. I am glad to mention that I have altogether 170 combined years of friendships with the authors. Here is the lecture announcement:

Breakthroughs — Locally Testable Codes with Constant Rate, Distance, and Locality

Oct 6, 2021 10:00 am – 11:00 am 

Speaker: 

Irit Dinur (Weizmann Institute of Science) 

A locally testable code (LTC) is an error-correcting code together with a property tester. The tester reads a few random bits in the received word and decides if the word is in the code. 

LTCs were initially studied as essential components of PCPs, and since then the topic has evolved on its own. High rate LTCs could be useful in practice: before attempting to decode a received word, one can save time by first quickly testing if it is close to the code. 

An outstanding open question has been whether there exist LTCs  that are “good” in the coding theory sense of having both constant relative distance and rate, and at the same time testable with a constant number of queries.

In this talk, Irit Dinur will describe a construction of such codes based on a new object which she and her collaborators call Square Cayley Complex. 

Joint work with Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes.


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

To cheer you up in difficult times 29: Free will, predictability and quantum computers

I wrote a paper, in Hebrew, entitled “Free will, predictability and quantum computers.” Click for the pdf file (Version of Nov. 25, 2021; orig. version). As you probably know, the free will problem is the apparent contradiction between the fact that the laws of nature are deterministic on the one hand, and the notion that people are making free choices that affect their future on the other hand. Here on my blog, I mentioned the free will problem twice: once, briefly, in connection with a lecture by Menachem Yaari (2008), and once in TYI 33 (2017) while conducting the “great free will poll” (see picture below for the outcomes). As for the paper, I hesitated whether to write it in Hebrew or in English; I finally chose Hebrew and I plan to prepare also an English version sometime in the fall.

Here is the abstract of my new paper.

תקציר: המאמר עוסק בקשר בין השאלות הנוגעות להיתכנות מחשבים קוונטיים, הפרדיקטביליות של מערכות קוונטיות מורכבות בטבע, והסתירה הקיימת לכאורה בין חוקי הטבע לבין רצון חופשי. נדון במקביל במחשב הקוונטי “סיקמור” בעל 12 יחידות חישוב (קיוביטים), ובאליס, שעל רצונה החופשי ננסה לתהות. התאוריה של המחבר העוסקת באי האפשרות של חישוב קוונטי, מצביעה באופן ישיר על אי האפשרות לנבא במדויק את מחשב הסיקמור, כמו גם את מוחה של אליס.  בניתוח מורכב יותר נראה, שאי האפשרות של חישוב קוונטי תומכת בגישה לפיה חוקי הטבע אינם שוללים בחירה חופשית. בבסיס הטיעון הזה עומדת עמימות בדרך שבה העתיד נקבע מהעבר ואשר איננה נעוצה באופי המתמטי של חוקי הפיסיקה (שהם לגמרי דטרמיניסטים), אלא בתיאור הפיסיקלי של העצמים שאנו דנים בהם. אנו דנים גם בהפרדה בין טענות לגבי העתיד שטמונות במארג הסיבתי הקיים בין העבר והעתיד, לבין טענות הנוגעות לעתיד ואשר אינן נמצאות במארג זה

Abstract: We study the connection between the possibility of quantum computers, the predictability of complex quantum systems in nature, and the free will problem. We consider in parallel two examples: the Sycamore quantum computer with 12 qubits (computing elements) and Alice, whose decisions and free will we try to question. The author’s theory that quantum computation is impossible (in principle) directly indicates that the future of both Alice’s brain and the Sycamore quantum computer cannot be predicted. A more involved analysis shows that failure of quantum computation supports the view that the laws of nature do not contradict free will. At the center of the argument is ambiguity in the way the future is determined by the past, not in terms of the mathematical laws of physics (which are fully deterministic) but in terms of the physical description of the objects we discuss. In addition, we discuss the separation between claims about the future that belong to the causal fabric of the past and the future, and claims that don’t belong to this fabric.

Two examples that we consider in parallel throughout the paper are “Alice”, whose free will we try to explore, and Google’s “Sycamore” quantum computer with 12 qubits. So, even if Google’s Sycamore does not lead to “quantum supremacy” (and I suspect it does not!) it could still be used in the pursuit of human free will 🙂 . Aram Harrow’s hypothetical quantum computer from our 2012 quantum debate (post 4) also plays a role in my paper.

My interest in the problem was provoked by Avishai Margalit in the mid 90s. Later I was engaged in a long email debate with Ron Aharoni following his 2009 (Hebrew) book on philosophy about this problem and related philosophical questions.  Since then, I have been following with interest writings on the problem by Scott Aaronson, Sabine Hossenfelder, Tzahi Gilboa, and others, and had brief discussions about free will with Bernard Chazelle and a few other friends. Writing the paper provided me an
immensely enjoyable opportunity to discuss the problem once again with
philosophers, friends and colleagues.

One question that I initially discussed but later left out is the following:

From the point of view of people in the mid 20th century, did quantum mechanics offer an opportunity for understanding the apparent contradiction between free will and the deterministic laws of nature? (Schrödinger himself wrote a paper where he was skeptical about this.)

My a priori intuition about the free will problem is in analogy with Zeno’s famous motions paradoxes. Zeno’s paradoxes offered an opportunity to re-examine the mathematics and physics of motion while not shaking the common sense understanding of motion. (In fact, the ancient Greeks knew enough about the mathematics and physics of motion to conclude that motion is possible and that Achilles will overtake the tortoise, and they could compute precisely when.)  Similarly, the question of free will is an opportunity to explore determinism and related issues, but probably not to challenge our basic understanding of human choice. 

Here are a few relevant links. Papers by Schrödinger (1936), Bohr (1937), and an essay by Einstein on free will (see picture below). Ron Aharoni’s paper (Hebrew) on Newcomb’s paradox published in “Iyun” from 1984 (Ron kindly agreed to explain his view on the FW problem in some future post.); A post by Scott Aaronson about his paper on the matter (related posts on SO (2021), (2012); Posts by Sabine Hossenfelder (2016), (2014), (2020), (2013), (2019), (2011), (2012) (and her paper on the matter); A post by Sean Carrol (2011); Itzhak Gilboa’s take; A paper by Neven, Read and Rees with a proposed engineering of conscious quantum animat that possesses agency and feelings; The World Without Quantum Computation with emphasis on Predictability and Free Will (click for the Power Point presentation). A lecture I gave on Aug 26, 2021 at the ML4Q Students’ & Postdocs’ Retreat 2021.

This post can be seen as my response to TTY33 for which Ori was eagerly waiting. The paper could be seen as a FW booster for Hebrew-speaking audience, and, as I said, I hope to produce a similar FW booster for English-speaking audience in the upcoming fall.

FW-pic

(Clockwise) The cover of Jennan Ismael’s 2016 book, Alice, the Sycamore computer, and a cartoon about free will.

FW-pic5

Three figures from the paper

FW-pic2

Einstein’s Essay on free will (left) and the outcomes of our 2017 great free will poll. (Einstein’s opening statement about the moon was inspired by Spinoza.)

Posted in Philosophy, Quantum | Tagged , | 6 Comments