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

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

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 Aug. 24, 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 , | 5 Comments

Alef’s corner: Mathematical research

alefMR2

Posted in Art, What is Mathematics | Tagged | Leave a comment

Let me tell you about three of my recent papers

michaelrabin

 

Let me tell you briefly about three of my papers that were recently accepted for publication. Relative Leray numbers via spectral sequences with Roy Meshulam, Helly-type problems with Imre Bárány, and Statistical aspects of quantum supremacy experiments with Yosi Rinott and Tomer Shoham.

Relative Leray numbers via spectral sequences

We extend the topological colorful Helly theorem to the relative setting. Our main tool is a spectral sequence for the intersection of complexes indexed by a geometric lattice. 

Roy and I have a long term project of studying topological Helly type theorems. Often, results from convexity give a simple and strong manifestation of theorems from topology: For example, Helly’s theorem manifests the nerve theorem from algebraic topology, and Radon’s theorem can be regarded as an early “linear” version of the Borsuk–Ulam theorem. We have a few more “linear” theorems in need of topologizing on our list. Actually the paper already appeared in Mathematika on June 26, 2021. It is dedicated to our dear teacher, colleague and friend  Michael O. Rabin. 

Dedicated to Michael O. Rabin, a trailblazing mathematician and computer scientist

Helly type problems, to appear in the Bulletin of the American Mathematical Society 

We present a variety of problems in the interface between combinatorics and geometry around the theorems of Helly, Radon, Carath ́eodory, and Tverberg. Through these problems we describe the fascinating area of Helly-type theorems, and explain some of its main themes and goals.

Imre and I have long term common interest in Helly-type problems and often discussed it since we first met in 1982.  We wrote a first joint paper in 2016 and last year we wrote two additional papers with Attila Por.  Last year Imre wrote a great book  “Combinatorial convexity” (AMS, 2021, in press) largely devoted to Helly-type theorems. As for me, I plan on gradually writing on open problems related to my areas of interest. (See these slides for some problems.)   

Statistical aspects of quantum supremacy experiments

Yosi Rinott, Tomer Shoham and I started this project about a year an a half ago. Our paper have now been accepted to Statistical Science where you can download the accepted version along many other future papers. This is my second paper in Statistical Science. The first one was “Solving the bible code puzzle” with Brendan McKay, Dror Bar-Nathan and Maya Bar-Hillel, that appeared in 1999.     

In quantum computing, a demonstration of quantum supremacy (or quantum advantage) consists of presenting a task, possibly of no practical value, whose computation is feasible on a quantum device, but cannot be performed by classical computers in any feasible amount of time. The notable claim of quantum supremacy presented by Google’s team in 2019 consists of demonstrating the ability of a quantum circuit to generate, albeit with considerable noise, bitstrings from a distribution that is considered hard to simulate on classical computers. Very recently, in 2020, a quantum supremacy claim was presented by a group from the University of Science and Technology of China, using a different technology and generating a different distribution, but sharing some statistical principles with Google’s demonstration.

Verifying that the generated data is indeed from the claimed distribution and assessing the circuit’s noise level and its fidelity is a statistical undertaking. The objective of this paper is to explain the relations between quantum computing and some of the statistical aspects involved in demonstrating quantum supremacy in terms that are accessible to statisticians, computer scientists, and mathematicians. Starting with the statistical modeling and analysis in Google’s demonstration, which we explain, we study various estimators of the fidelity, and different approaches to testing the distributions generated by the quantum computer. We propose different noise models, and discuss their implications. A preliminary study of the Google data, focusing mostly on circuits of 12 and 14 qubits is given in different parts of the paper

Posted in Combinatorics, Convexity, Geometry, Quantum, Statistics | Tagged , , , , | Leave a comment

Mathematical news to cheer you up

Anna-Kiesenhofer-Olympics-2021-930x620

1.  Anna Kiesenhofer, a PhD mathematician researching PDEs at Ecole Polytechnique Federale Lausanne (EPFL), won the gold medal in the women’s bicycle road race at the Olympics.

Here are two trivia question: a) Which hero of a recent post over here is related to Kiesenhofer’s mathematical side? b) Name another famous connection between EPFL-mathematics and sport.

2. János Nagy and Péter Pál Pach proved the Alon-Jaeger-Tarsi conjecture via group ring identities

The abstract says it all: In this paper we resolve the Alon-Jaeger-Tarsi conjecture for sufficiently large primes. Namely, we show that for any finite field F of size 61<|F|79 and any nonsingular matrix M over F there exists a vector x such that neither x nor Ax has a 0 component.

3. Michael Simkin asymptotically solved the n-queens problem! (We mentioned this classic problem and earlier progress by Zur Luria in this post.)

Abstract: The n-queens problem is to determine {\mathcal Q}(n), the number of ways to place n mutually non-threatening queens on an n \times n board. We show that there exists a constant α=1.942±3×10-3 such that {\mathcal Q}(n)=((1 \pm o(1))n e ^{-\alpha})^n. The constant α is characterized as the solution to a convex optimization problem in {\mathcal P}([−1/2,1/2]2), the space of Borel probability measures on the square. The chief innovation is the introduction of limit objects for n-queens configurations, which we call “queenons”. These are a convex set in \mathcal P([−1/2,1/2]2). We define an entropy function that counts the number of n-queens configurations that approximate a given queenon. The upper bound uses the entropy method. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queen on and whose entropy matches that found in the upper bound. The enumeration of n-queens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons. Along the way we prove a large deviations principle for n-queens configurations that can be used to study their typical structure.

sun

Intermission: the sun over Tel Aviv sea

4. Boris Bukh demonstrated Extremal graphs without exponentially-small bicliques

Abstract: The Turán problem asks for the largest number of edges in an $latex n$-vertex graph not containing a fixed forbidden subgraph F. We construct a new family of graphs not containing K_{s,t}, for t=C^s, with  \Omega (n^{2-1/s}) edges matching the upper bound of Kövári, Sós and Turán. 

5. Michael Capalbo, Explicit 𝑁-vertex graphs with maximum degree 𝐾 and diameter [1+𝑜(1)]log𝐾-1 𝑁 for each 𝐾-1 a prime power,

Abstract:   Here we first present the solution of a long-standing open question–the explicit construction of an infinite family of N-vertex cubic graphs that have diameter [1+o(1)]log2 N. We then extend the techniques to construct, for each K of the form 2s+1 or K=ps+1; s an integer and p a prime, an infinite family of K-regular graphs on N vertices with diameter [1+o(1)]logK−1 N.

I missed this breakthrough in STOC 2019 but now it appeared in Combinatorica, and Nati told me about it.

6.  A beautiful survey article: Intersection Problems in Extremal Combinatorics: Theorems, Techniques and Questions Old and New, by David Ellis,

Abstract: The study of intersection problems in Extremal Combinatorics dates back perhaps to 1938, when Paul Erdős, Chao Ko and Richard Rado proved the (first) `Erdős-Ko-Rado theorem’ on the maximum possible size of an intersecting family of k-element subsets of a finite set. Since then, a plethora of results of a similar flavour have been proved, for a range of different mathematical structures, using a wide variety of different methods. Structures studied in this context have included families of vector subspaces, families of graphs, subsets of finite groups with given group actions, and of course uniform hypergraphs with stronger or weaker intersection conditions imposed. The methods used have included purely combinatorial ones such as shifting/compressions, algebraic methods (including linear-algebraic, Fourier analytic and representation-theoretic), and more recently, analytic, probabilistic and regularity-type methods. As well as being natural problems in their own right, intersection problems have connections with many other parts of Combinatorics and with Theoretical Computer Science (and indeed with many other parts of Mathematics), both through the results themselves, and the methods used. In this survey paper, we discuss both old and new results (and both old and new methods), in the field of intersection problems. Many interesting open problems remain; we will discuss several. For expositional and pedagogical purposes, we also take this opportunity to give slightly streamlined versions of proofs (due to others) of several classical results in the area. This survey is intended to be useful to PhD students, as well as to more established researchers. It is a personal perspective on the field, and is not intended to be exhaustive; we apologise for any omissions. It is an expanded version of a paper that will appear in the Proceedings of the 29th British Combinatorial Conference.

7.  An interview with me; interviewer Toufik Mansour.

 

 
 

Posted in Combinatorics, Sport, Uncategorized, Updates | 5 Comments

To Cheer You Up in Difficult Times 28: Math On the Beach (Alef’s Corner)

math-on-the-beach

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

To cheer you up in difficult times 27: A major recent “Lean” proof verification

Lean is a functional programming language that makes it easy to write correct and maintainable code. You can also use Lean as an interactive theorem prover.” (See Lean’s homepage and see here for an introduction to lean.)

Kevin Buzzard’s blog XENA is largely devoted to lean. “The Xena project is an attempt to show young mathematicians that essentially all of the questions which show up in their undergraduate courses in pure mathematics can be turned into levels of a computer game called Lean.” (Perhaps this could also appeal to old mathematicians especially those interested in computer games 🙂 .)

Six months ago Peter Scholze proposed over XENA a project of verifying using Lean a certain involved proof he had (and was not even sure about), a few weeks ago he reported on an amazing progress that was achieved. This is great news! (I thank Tammy Ziegler for telling me about it.) For more on Lean see this Quanta Magazine article by Kevin Hartnett, and this GLL post. As a form of celebration, I posted an MO question on experimental mathematics (that renewed my older MO question).



KBPS

Kevin Buzzard and Peter Scholze

Posted in Algebra, Updates, What is Mathematics | Tagged , , | 4 Comments

To cheer you up in difficult times 26: Two real-life lectures yesterday at the Technion

After 16 months without lecturing to an audience in my same location, I gave yesterday two lectures at the Technion in front of a live audience (and some additional audience in remote locations). The main lecture was in COMSOC 2021, an international conference on computational social choice,  and earlier I gave a guest lecture in Roy Meshulam’s class about simple polytopes. I also met many friends. 

Reshef Meir who organized (with Bill Zwicker) COMSOC 2021 wrote:

Hi all, 
today was beyond expectations – the first feeling of a real actual conference after almost a year and a half!  We had about 40 people attending, viewing posters, and listening to talks. I truly hope this will return to be a common scene and that we can all meet face to face soon.
 

In my COMSOC lecture I talked about some earlier ideas and results in my work on social choice, starting with my paper with Ariel Rubinstein and Rani Spiegler on rationalizing individual choice by multiple rationals, and my subsequent attempt to use learnability as a tool for understanding choices of economic agents. This led to interesting questions on social choice that are discussed in this 2009 post.

In Roy’s course I explained h-vectors of polytopes and the Dehn-Sommerville relations based on counting outdegrees of the graph of the polytope when we direct its edges based on a generic abstract objective function. I moved on to present a proof of Blind-Mani’s theorem that the graph of the polytope determines the full combinatorics. This proof is probably the one proof I presented the most and it is given in this 2009 post.

sc1

In my  COMSOC lecture I described how to fill the two question marks in the table above.

sc2

Posted in Combinatorics, Convex polytopes, Economics, Games, Rationality | Tagged | Leave a comment