Some News from a Seminar in Cambridge

On an old problems of Erdős

(h/t Michael Simkin and Nati Linial)

Here is a somewhat mysterious announcement for a combinatorics seminar lecture at Cambridge.

Which old problems of Erdős are we talking about? Here is a picture from the seminar itself.

 

Stay tuned (or try to test your intuition or guess in the comment section.)

Subspace Designs, Unit and Distinct Distances, and Piercing Standard Boxes.

A lot of things are happening and let me briefly report on three major advancements in combinatorics.

1. Peter Keevash, Ashwin Sah and Mehtaab Sawhney proved the existence of subspace designs with any given parameters, provided that the dimension of the underlying space is sufficiently large in terms of the other parameters of the design and satisfies the obvious necessary divisibility conditions.  Here is the link to the paper: The existence of subspace designs.
2. Noga Alon, Matija Bucić, and Lisa Sauermann made an important advance on the study of unit distances and distinct distances in arbitrary normed space. Here is a link to the paper: Unit and distinct distances in typical norms. The unit distance and distinct distances problems for Euclidean geometry are old and famous, and much attention has been given to the question of what happens to these problems if one considers normed spaces other than the Euclidean plane. Alon, Bucić, and Sauermann give an essentially tight answer to both questions for almost all norms on , in a certain Baire categoric sense.
3. István Tomon’s paper: Lower bounds for piercing and coloring boxes. Here is Tomon’s abstract from his recent Copenhagen-Jerusalem seminar: Configurations of axis-parallel boxes in are extensively studied in combinatorial and computational geometry. Despite their innocent appearance, there are many old problems involving their structure that are still not well understood. I will talk about a construction, which addresses several of these problems, and shows that configurations of boxes may be more complex than people conjectured.

Subspace designs and q-analogs

We talked about subspace designs in this post  and in particular about the 2016 paper of Michael  Braun, Tuvi Etzion , Patric R. J. Östergard , Alexander Vardy,  and Alfred Wasserman. While preparing this post I learned the sad news that Alexander Vardy, a prominent coding theorist, had passed away a year ago at the young age of 58.

The theme of finding -analogs to combinatorial results and problems is important both in enumerative and algebraic combinatorics and in extremal combinatorics and it will be interesting to discuss it in some future post. While preparing for that I recalled the famous –Dyson conjecture that had been settled by Zeilberger and Bressoud in 1995. I learned that by now there are simpler proofs:  “A shorter proof, using formal Laurent series, was given in 2004 by Ira Gessel and Guoce Xin, and an even shorter proof, using a quantitative form, due to Karasev and Petrov, and independently to Lason, of Noga Alon’s Combinatorial Nullstellensatz, was given in 2012 by Gyula Karolyi and Zoltan Lorant Nagy. The latter method was extended, in 2013, by Shalosh B. Ekhad and Doron Zeilberger to derive explicit expressions of any specific coefficient.” (Wikipedia.)

Unit and distinct distances

Here is the abstract of the paper by Alon, Bucić, and Sauermann:

Erdős’ unit distance problem and Erdős’ distinct distances problem are among the most classical and well-known open problems in all of discrete mathematics. They ask for the maximum number of unit distances, or the minimum number of distinct distances, respectively, determined by $latex n$ points in the Euclidean plane. The question of what happens in these problems if one considers normed spaces other than the Euclidean plane has been raised in the 1980s by Ulam and Erdős and attracted a lot of attention over the years. We give an essentially tight answer to both questions for almost all norms on , in a certain Baire categoric sense.

For the unit distance problem we prove that for almost all norms ||.|| on , any set of points defines at most unit distances according to ||.||. We also show that this is essentially tight, by proving that for every norm ||.|| on , for any large , we can find $latex n$ points defining at least unit distances according to ||.||.

For the distinct distances problem, we prove that for almost all norms ||.|| on any set of points defines at least $latex (1−o(1))n$ distinct distances according to ||.||. This is clearly tight up to the $latex o(1)$ term.

Our results settle, in a strong and somewhat surprising form, problems and conjectures of Brass, of Matoušek, and of Brass-Moser-Pach. The proofs combine combinatorial and geometric ideas with tools from Linear Algebra, Topology and Algebraic Geometry.

We discussed the unit distances and distinct distances in many posts over here, and they are also related to problems around Borsuk’s problem (see also my survey paper Some old and new problems in combinatorial geometry I: Around Borsuk’s problem).

Standard boxes

Here is the abstract of Tomon’s paper.

We discussed the intersection pattern of (standard) boxes on several occasions such as this post about Jurgen Eckhoff.

Greg Kuperberg @ Tel Aviv University

Greg Kuperberg is on a short visit in Israel and yesterday he gave a fantastic lecture on an improved bound for the Solovay-Kitaev theorem. Here is a videotaped lecture of Greg on the same topic in QIP2023.

The Solovay-Kitaev theorem from 1995 (in a stronger version by Kitaev-Shen-Viyalyi) asserts that

Theorem:  If is a finite subset of  that densely generates with the property that , then there is an efficient algorithm to -approximate every element by a word   of length

where we can take , for every .

Greg mentioned several improvements and related results shown over the years, and he addressed the question of improving . His result, which gave the first known improvement (using two separate ideas) takes down from to 1.44042…

(I told Greg that the mathematicians’ labor unions frown upon such drastic advances in a single paper.)

You can test your intuition for what 1.44042… stands for.

Israel AGT Day, Reichman University, March 5, 2023

We are running tomorrow the annual Israeli workshop in algorithmic game theory.

Where: Reichman University. The conference will take place in room EL03, Adelson building. 

Program: here.

Registration: here (free).

Main speakers: Moshe Babaioff (Microsoft Research), Gil Kalai (Reichman University and The Hebrew University of Jerusalem), Divyarthi Mohan (Tel Aviv University), Rebecca Reiffenhäuser (University of Amsterdam), Nir Rosenfeld (Technion). (See below for the full program.)

Organizers: Alon Eden, Michal Feldman, Gil Kalai and Tami Tamir.

Previous editions of the AGT day: 2018, 2019, 2020  (we had a break for a few years due to the epidemic, and then we had a Zoom international seminar.)

Program

09:00 – 09:30    Gathering

09:30 – 10:00    Nir Rosenfeld (Technion)

Strategic Classification: Learning in Face of Strategic Behavior

10:00 – 10:40    Lightning Talks Session 1:

Yoav Kolumbus (The Hebrew University) 

Simon Mauras (Tel Aviv University) 

Rotem Torkan (The Technion) 

Shaul Rosner (Reichman University) 

Aditya Aradhye (Tel Aviv University) 

Ariel Shaulker (Weizmann) 

Omer Madmon (The Technion)

10:40 – 11:10    Coffee

11:10 – 11:40    Moshe Babaioff (Microsoft Research)

Making Auctions Robust to Aftermarkets

11:40 – 12:20    Lightning Talks Session 2:

Yotam Gafni (The Technion) 

Hodaya Barr (Bar-Ilan University)

Samuel Bismuth (Ariel University)

Suman Sadhukhan (Haifa University) 

Tal Alon (The Technion)

Uri Sherman (Tel Aviv University)

12:20 – 13:50     Lunch

13:50 – 14:20    Rebecca Reiffenhäuser (University of Amsterdam)

Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria (or how to be fair to deceptive egoists.)

14:20 – 15:00    Lightning Talks Session 3:

Konstantin Zabarnyi (The Technion)

Xin Huang (The Technion)

Shiri Ron (Weizmann)

Vishnu V. Narayan (Tel Aviv University)

Tomasz Ponitka (Tel Aviv University)

Yehonatan Mizrahi (The Hebrew University)

15:00 – 15:30    Coffee

15:40-16:25      Gil Kalai (Reichman University and The Hebrew University)

Noise sensitivity and stability: social choice, and beyond

16:25 – 17:00    Divyarthi Mohan (Tel Aviv University)

Approximately Efficient Auctions with Private Interdependent Valuations

Alef’s Corner: Democracy (Israel, 2023)

Democracy in Hebrew is דמוקרטיה represented by the letter “dalet” ד

 

Absolutely Sensational Morning News – Zander Kelley and Raghu Meka proved Behrend-type bounds for 3APs

What is the density of a subset of that guarantees that contains a 3-term arithmetic progression? And, more generally, if the density of is what is the minimum number of 3-terms AP that contains?

These problems and the more general problems for -term AP, are very exciting and mathematicians worked on them extensively in the last century. (We devoted several  posts to earlier breakthroughs.)

This morning. a striking new paper by Zander Kelley and Raghu Meka appeared on the arXiv describing an absolutely amazing breakthrough. (I am thankful to Ryan Alweiss for telling me about it.) Here is the link to the paper

Strong Bounds for 3-Progressions, by Zander Kelley and Raghu Meka

Abstract: We show that for some constant β>0, any subset A of integers {1,…,N} of size at least

contains a non-trivial three-term arithmetic progression. Previously, three-term arithmetic progressions were known to exist only for sets of size at least for a constant .

Our approach is first to develop new analytic techniques for addressing some related questions in the finite-field setting and then to apply some analogous variants of these same techniques, suitably adapted for the more complicated setting of integers.

Huge congratulations to Zander Kelley and Raghu Meka, and to the mathematical community.

AI generated image showing arithmetic progression by shutterstock.

An earlier 2020 post on 3-term AP and related problems with much bacground on the problem: To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth’s theorem!;

I apologize for misspelling the authors’ names in the early version.

Updates: A few words about the proof; The proof is based on Fourier methods. The argument applies first for the case of and then transfer the argument (with some difficulties and complications) to . An account of the Kelley–Meka proof, with some modifications of the second part is given by Bloom and Sisask at https://arxiv.org/abs/2302.07211.

The Trifference Problem

Anurag Bishnoi wrote this beautiful post on a problem going back to a 1988 paper of Körner and Marton, and on a recent lovely paper by Anurag Bishnoi, Jozefien D’haeseleer, Dion Gijswijt, and Aditya Potukuchi, Blocking sets, minimal codes and trifferent codes.

Anurag's Math Blog

What is the largest possible size of a set $latex C$ of ternary strings of length $latex n$, with the property that for any three distinct strings in $latex C$, there is a position where they all differ?

Let $latex T(n)$ denote this largest size. Trivially, $latex T(1) = 3^1 = 3$, and after some playing around you can perhaps prove that $latex T(2) = 4$ (I encourage you to try it so that you understand the problem). With a bit more effort, and perhaps the help of a computer, you might also be able to show that $latex T(3) = 6$, and $latex T(4) = 9$. For example, here is a set of nine ternary strings showing that $latex T(4) geq 9$: $latex 0000, 0111, 2012, 2201, 2120, 0111, 1012, 1101, 1210$. You should check that for any three strings from these nine, there is at least one position…

View original post 872 more words

Greatest Hits 2015-2022, Part II

This is the second part of Greatest Hits 2015-2022, Part I. Here are popular and favorite posts published in 2019-2022.

2019 Supremacy and Sensitivity (and Sunflowers)

Test your intuition 38 was contributed in March 2019 by my youngest son Lior. TYI38 Lior Kalai: Monty Hall Meets Survivor. Aside from the problem itself, the post contained beautiful pictures of my family, and, two days after the post was published, I added the startling breaking news about Karen Uhlenbeck being awarded the Abel Prize.

Also in March 2019, the post 10 Milestones in the History of Mathematics according to Nati and Me drew many views and many comments. And in April 2019 I made an unusual invitation:  An Invitation to a Conference: Visions in Mathematics towards 2000, with links to videos and many pictures of us 20 years younger.  This followed by a post discussing a bold statement made at the conference by Misha Gromov Are Natural Mathematical Problems Bad Problems?

Quantum supremacy

In August 2019 I presented a new paper and a CERN colloquium:  The Argument against Quantum Computers – a CERN Colloquium and a New Paper, a month later on September 22, 2019, a paper by a team from Google was leaked with a demonstration of quantum supremacy, which, if true, would refute my argument. I found the leaked paper rather unconvincing and raised some concerns about it in this post: Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google).

Two weeks later I wrote The story of Poincaré and his friend the baker, where I raised another concern regarding the calibration process of the paper, and this concern was amply discussed in the comment section.  Following the appearance of the Google paper itself on October 21, 2019, and some responses from the Google team,  I wrote on November 11, 2019 a new post Gil’s Collegial Quantum Supremacy Skepticism FAQ. Some further updates and discussion can be found in the Dec. 27 post The Google Quantum Supremacy Demo and the Jerusalem HQCA debate.

2019 mathematical news

The mathematical news that was most exciting to me in 2019 was reported in August. Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture. This was a problem I had first heard about as an undergraduate, I thought about it over the years, and we ran polymath 10 for attacking it. I also was excited about other possible applications, but did not imagine it would be related to Jeff Kahn and mine expectation threshold conjecture. But indeed it was related: Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectation-thresholds;

Other great results were: Amazing: Hao Huang Proved the Sensitivity Conjecture! (July);  A sensation in the morning news – Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture (May); Another sensation – Annika Heckel: Non-concentration of the chromatic number of a random graph (June); Konstantin Tikhomirov: The Probability that a Bernoulli Matrix is Singular (February); Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube; Matan Harel, Frank Mousset, and Wojciech Samotij and the “the infamous upper tail” problem; Attila Por’s Universality Result for Tverberg Partitions; Isabella Novik and Hailun Zheng: Neighborly centrally symmetric spheres exist in all dimensions!; Danny Nguyen and Igor Pak: Presburger Arithmetic Problem Solved! And in number theory 8866128975287528³+(-8778405442862239)³+(-2736111468807040)³;

We had two great guest posts: Dan Romik on the Riemann zeta function, and Imre Bárány: Limit shape.

In 2019 I also wrote about Jean Bourgain and about The last paper of Catherine Rényi and Alfréd Rényi: Counting k-Trees.

A drawing explaining Attila Por’s construction

Jean Bourgain and Joram Lindenstrauss

2020 To cheer you up in difficult times

Mathematical news

The post about mathematical news that excited both the readers and me the most appeared in January: Amazing: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP* = RE and thus disproved Connes 1976 Embedding Conjecture, and provided a negative answer to Tsirelson’s problem. My final correspondence with Boris Tsirelson was about this breakthrough and I wrote about him in this post Trees not Cubes! Memories of Boris Tsirelson.

Two other exciting and popular posts with 2020 major mathematical news came in July and December. The July post was To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth’s theorem!; And in December To Cheer You Up in Difficult Times 15: Yuansi Chen Achieved a Major Breakthrough on Bourgain’s Slicing Problem and the Kannan, Lovász and Simonovits Conjecture

To cheer you up in difficult times (Math news, and fun)

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; To cheer you up in difficult times 5: A New Elementary Proof of the Prime Number Theorem by Florian K. Richter; To cheer you up in difficult times 6: Play Rani Sharim’s two-player games of life, read Maya Bar-Hillel presentation on catching lies with statistics, and more.;To Cheer you up in Difficult Times 8: Nathan Keller and Ohad Klein Proved Tomaszewski’s Conjecture on Randomly Signed Sums;  To cheer you up in difficult times 9: Alexey Pokrovskiy proved that Rota’s Basis Conjecture holds asymptotically; To cheer you up in difficult times 12: Asaf Ferber and David Conlon found new lower bounds for diagonal Ramsey numbers; Three games to cheer you up.

The first post which explicitly aimed cheering up our readers was from mid-March when it had become clear that the Corvid outbreak is going to overshadow our lives. To cheer you up in complicated times – A book proof by Rom Pinchasi and Alexandr Polyanskii for a 1978 Conjecture by Erdős and Purdy!

Other mathematical news from 2019 were Ringel Conjecture, Solved! Congratulations to Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov; In February Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand; Kelman, Kindler, Lifshitz, Minzer, and Safra: Towards the Entropy-Influence Conjecture; Noam Lifshitz: A new hypercontractivity inequality — The proof!

Quantum news and matters

In December 2020 I wrote about an attempt to establish quantum supremacy using a photonic device: Photonic Huge Quantum Advantage ???, This time, an algorithm from a 2014 paper by Guy Kindler and me sufficed to refute the fantastic claims. A few days later I wrote The Argument Against Quantum Computers – A Very Short Introduction, which has become one of the blog’s blockbusters.

2021 Erdős-Faber-Lovász and Diverse Matters

Discussion about Diversity: the post To Cheer You Up in Difficult Times 31: Federico Ardila’s Four Axioms for Cultivating Diversity, led to heated discussions mainly on Facebook.

Celebrations and discussions: The post Cheerful News in Difficult Times: The Abel Prize is Awarded to László Lovász and Avi Wigderson, contains a lot of pictures of Avi and Laci and their families (and in a few cases of my family), and it was followed by the most viewed 2021 post presenting a debate between Avi Wigderson and me, which goes deeply into the connection between (computer science) theory, practice, and mathematics: The probabilistic proof that 2^400-593 is a prime: a revolutionary new type of mathematical proof, or not a proof at all?

Mathematical news from 2021: To cheer you up in difficult times 17: Amazing! The Erdős-Faber-Lovász conjecture (for large n) was proved by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus!; To cheer you up in difficult times 20: Ben Green presents super-polynomial lower bounds for off-diagonal van der Waerden numbers W(3,k);To cheer you up in difficult times 21: Giles Gardam lecture and new result on Kaplansky’s conjectures; 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. To cheer you up in difficult times 34: Ringel Circle Problem solved by James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak; Amazing: Simpler and more general proofs for the g-theorem by Stavros Argyrios Papadakis and Vasiliki Petrotou, and by Karim Adiprasito, Stavros Argyrios Papadakis, and Vasiliki Petrotou.

Two collections of startling mathematical news: To cheer you up in difficult times 25: some mathematical news! (Part 2) and To cheer you up in difficult times 22: some mathematical news! (Part 1)

Memorabilia: Nostalgia corner: John Riordan’s referee report of my first paper;  To cheer you up in difficult times 23: the original hand-written slides of Terry Tao’s 2015 Einstein Lecture in Jerusalem

Quantum matters:  Amazing: Feng Pan and Pan Zhang Announced a Way to “Spoof” (Classically Simulate) the Google’s Quantum Supremacy Circuit!; This work and several related works largely (but not fully) refuted  Google’s 2019 quantum supremacy claim.

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

A post about my papers:  Let me tell you about three of my recent papers;

Open problems: The 3ᵈ problem; Turan type theorems for simplicial complexes.

Are we up for a new polymath project?: Possible future Polymath projects (2009, 2021)

2022 The expectation threshold conjecture

Blogging from ICM 2022:  I slowly blogged about various events and lectures from ICM 2022. The most popular post about ICM2022 was about verifying mathematical proofs using computers and especially LEAN: ICM 2022. Kevin Buzzard: The Rise of Formalism in Mathematics. I attempted to report on ICM 2022: Langlands Day which I followed on Zoom, and I gave a live report from Helsinki on ICM 2022 awarding ceremonies (1).

Because of Russia’s invasion of Ukraine, the ICM originally planned for St. Petersburg turned into a virtual event, but the opening ceremonies and lectures of the medalists took place with live audience in Helsinki.

The Israeli delegation to the 2022 general assembly of the IMU. With Tammy Ziegler and Mina Teicher.

The mathematical news that caught most attention:  A conjecture of Jeff Kahn and me is now fully resolved: Amazing: Jinyoung Park and Huy Tuan Pham settled the expectation threshold conjecture!  … and major progress on Frankl’s conjecture: Amazing: Justin Gilmer gave a constant lower bound for the union-closed sets conjecture

Other news:  Oliver Janzer and Benny Sudakov Settled the Erdős-Sauer Problem; Bo’az Klartag and Joseph Lehec: The Slice Conjecture Up to Polylogarithmic Factor! ;

News about polytopes and combinatorial geometry: Joshua Hinman proved Bárány’s conjecture on face numbers of polytopes, and Lei Xue proved a lower bound conjecture by Grünbaum; James Davies: Every finite colouring of the plane contains a monochromatic pair of points at an odd distance from each other.; Chaim Even-Zohar, Tsviqa Lakrec, and Ran Tessler present: The Amplituhedron BCFW Triangulation; Alexander A. Gaifullin: Many 27-vertex Triangulations of Manifolds Like the Octonionic Projective Plane (Not Even One Was Known Before).

Quantum matters:  Inaugural address at the Hungarian Academy of Science: The Quantum Computer – A Miracle or Mirage;

Greatest Hits 2015-2022, Part I

In February 2015 I wrote a post on the blog’s greatest hits in the first seven years, and its time to write a similar post for the eight years that followed.

Quick updates: In recent months I took part in two unusual conferences (for me). One conference in the city of Nazareth was about “free will” and the participants included neurologists, brain scientists, biologists, philosophers, psychologists, physicists, and experts in law and ethics. The other conference was at Tel Aviv about the Many Worlds Interpretation to quantum mechanics with a variety of researchers interested in the foundations of physics. In the last few weeks I gave (by Zoom) two physics colloquiums, one in Rutgers University and one in the Perimeter Institute at Waterloo, and in both cases the lecture was followed by very nice discussions. The lecture and discussion at the Perimeter Institute was videotaped and uploaded to PIRSA (Perimeter Institute Recorded Seminars Archive) and can be found in this link. The very interesting discussion included Ray Laflamme, Lee Smolin, Debbie Leung, Latham Boyle (my host, who, against all odds, perfectly pronounced my name 🙂 ) and Dominique.

Here is a link to the (Hebrew) lectures and discussions from the Free Will conference. I gave there a short response to Yakir Aharonov’s lecture. And here is the You Tube link to the Many worlds interpretation conference.

Before we start: Happy new year 2023 to all!   

2015-2022: The blockbusters

Not many great hits in 2015 (since March) and the most viewed post from 2015 was the opening post for Polymath10: Polymath10: The Erdos Rado Delta System Conjecture.

The most viewed post from 2016 and one of the most viewed posts ever was A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24.

The most popular post in 2017 (and among the most popular ever) was Elchanan Mossel’s Amazing Dice Paradox (your answers to TYI 30). (The post posing the question was also very popular.)

2018’s blockbuster was: Aubrey de Grey: The chromatic number of the plane is at least 5. A 2018/2019 blockbuster was Amazing: Karim Adiprasito proved the g-conjecture for spheres!

2019 was the year with maximum views ever. There were many posts with news about breakthroughs, and the most popular one was Amazing: Hao Huang Proved the Sensitivity Conjecture! Another hit was my first post about Google’s quantum supremacy claims: Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google).

The most popular post in 2020 was also about quantum computers  The Argument Against Quantum Computers – A Very Short Introduction. In April 2020 we introduced a new corner “To cheer you up in difficult times”.

The 2021 post with most views was a little debate between Avi Wigderson and me The probabilistic proof that 2^400-593 is a prime: a revolutionary new type of mathematical proof, or not a proof at all?

The most viewed post in 2022 was: Amazing: Jinyoung Park and Huy Tuan Pham settled the expectation threshold conjecture!

Here are other popular and favorite posts 2015-2018,  the second part will be devoted to 2019-2022.

2015 – polymath10, Israeli politics

The post Updates and plans III, contains a lot of startling mathematical and personal news. Among the mathematical news was the Adiprasito-Huh-Katz solution to the Heron-Rota conjecture. On the personal side are pictures from my 60th birthday conference.

The most viewed post from 2015 was the opening post for Polymath10: Polymath10: The Erdos Rado Delta System Conjecture, Polymath10, which started on November 2017 and was concluded in January 2017. In the second post Polymath10, Post 2: Homological Approach, I proposed a homological approach to the conjecture and we discussed (and improved) it, among other things, in several subsequent posts.

Another popular post was NogaFest, NogaFormulas, and Amazing Cash Prizes announcing Noga’s birthday conference.

For the first (and last) time I used the blog as a political platform:  I wrote a few posts in Hebrew criticizing our (then) prime minister Netanyahu and endorsing the labor opposition party for the 2015 elections. There were interesting comments (mostly negative).

I reported about several advances in combinatorics and computer science. Choongbum Lee proved the Burr-Erdős conjecture, More Reasons for Small Influence, New Isoperimetric Results for Testing Monotonicity, and The Simplex, the Cyclic polytope, the Positroidron, the Amplituhedron, and Beyond.  The last three posts are a mixture of reporting new results, explaining some classical results and raising some ideas of my own. Also in 2015 was a detailed report on Midrasha Mathematicae #18: In And Around Combinatorics, and a celebration following the solution of Erdos discrepancy problem EDP Reflections and Celebrations.

On the skeptical side we had a post with Angry Birds Update

In 2015, my beloved mother Carmela Kalai passed away and I devoted a post to her and her art.

2016 – Densest packing in dimensions 8 and 16, and the polynomial method

The most viewed post from 2016 and one of the most viewed posts ever was A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24. The second most popular post in 2016 involved the US elections, influence, noise sensitivity, social choice and Hex. The US Elections and Nate Silver: Information Aggregation, Noise Sensitivity, HEX, and Quantum Elections.

The startling news on the cup set problem came in 2016. Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem! Dion Gijswijt also reached the same result. This post followed an earlier one: More Math from Facebook where we talked about Croot, Lev and Pach’s paper and other results. In December 2016 Jordan and I ran a Polynomial Method Workshop in Jerusalem. Also in 2016: The Erdős Szekeres polygon problem – Solved asymptotically by Andrew Suk.

Also in 2016, a beautiful guest post Stefan Steinerberger: The Ulam Sequence, and a report on my Notices paper The Quantum Computer Puzzle @ Notices of the AMS. Imre Barany’s beautiful presentation on Jiří Matoušek is given in Jirka.

2017 – Elchanan Mossel’s dice problem and lovely mathematical proofs

2017 marked new attempts for humorous stories. Layish – a true story from 1995 about Avi W. and me. Proofs that will make you smile: The seventeen camels riddle, and Noga Alon’s camel proof and algorithms; From camels to lice: Micha A. Perles’ Proof By Lice!; Touching Simplices and Polytopes: Perles’ argument (with additional mathematical fantasies and humor);  Micha Perles’ Geometric Proof of the Erdos-Sos Conjecture for Caterpillars; Test Your Intuition 33: The Great Free Will Poll; and a humorous quantum cartoons post: If Quantum Computers are not Possible Why are Classical Computers Possible?

A favorite post of mine was: The World of Michael Burt: When Architecture, Mathematics, and Art meet. As already mentioned the most popular posts featured Elchanan Mossel’s dice problem. 2017’s most viewed mathematical news was R(5,5) ≤ 48.  Also popular was a thorough discussion Around the Garsia-Stanley’s Partitioning Conjecture. We discussed the question Is Heads-Up Poker in P? And here is a post on Edmund Landau and the Early Days of the Hebrew University of Jerusalem.

The post Where were we? described several updates including, most excitingly, a nice personal greeting by Benjamin Netanyahu (Israeli PM in 2017) to a talk I gave in the Technion. Another nice eclectic mathematical update was Updates (belated) Between New Haven, Jerusalem, and Tel-Aviv.

2018 The g-conjecture; Rio ICM2018

Many startling mathematical news: In December 2018 definite progress on the problem I worked the most:  Amazing: Karim Adiprasito proved the g-conjecture for spheres! In January, Subhash Khot, Dor Minzer and Muli Safra completed the proof of the 2-to-2 Games Conjecture, Also in January, Cody Murray and Ryan Williams’ new ACC breakthrough: Updates from Oded Goldreich’s Choices. In February Serge Vlăduţ : Lattices with exponentially large kissing numbers. In April, Aubrey de Grey: The chromatic number of the plane is at least 5. Also in April,  Cohen, Haeupler, and Schulman: Explicit Binary Tree-Codes & Cancellations, and Nathan Rubin Improved the Bound for Planar Weak ε-Nets and Other News From Ein-Gedi;  In May, Duncan Dauvergne and Bálint Virág Settled the Random Sorting Networks Conjectures, and Zur Luria on the n-Queens Problem. Also in December, Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids!

Toward the g-conjecture announcement I wrote about “what’s next”: Beyond the g-conjecture – algebraic combinatorics of cellular spaces I. I wrote another related post A Mysterious Duality Relation for 4-dimensional Polytopes.

Blogging from ICM 2018 Rio: I gave a plenary lecture at ICM 2018, and I was not the only Kalai in the congress: Yael Tauman Kalai’s ICM2018 Paper, My Paper, and Cryptography. I also slowly blogged about various events and lectures from the Rio congress. The most popular post from Rio was ICM 2018 Rio (3) – Coifman, Goldstein, Kronheimer and Mrowka, and the Four Color Theorem. I devoted much effort writing ICM 2018 Rio (4): Huh; Balog & Morris; Wormald.

Also in 2018, Ricky and Branko was an obituary to Ricky Pollack and Branko Grünbaum, and Coloring Problems for Arrangements of Circles (and Pseudocircles), was a post much in Ricky and Branko’s spirit.

2018 was the year of the first post in Alef’s corner: Alef’s Corner: There is Still a Small Gap in the Proof. Other popular posts were: Test Your Intuition 35: What is the Limiting Distance?; Conference in Singapore, Vietnam, Appeasement, Restorative Justice, Laws of History, and Neutrinos

Tel Aviv University Theory Fest is Starting Tomorrow

Same crawling tree — looking over the canyon. Taken from within another tree, which happens to point somewhere

Tel Aviv University Theory Fest, December 26-December 28 2022.

Cryptography workshop @ TAU TheoryFest December 29, 2022

TAU 2022 TheoryFest, December 26-28, 2022

The Theory of Computing was born as a purely mathematical investigation into the notion of computation. From the start, it has been a cornerstone of computer science and has been used to tackle fundamental computing research problems. It was soon recognized as a useful paradigm of thought that facilitates research in other disciplines as well, such as economics and biology.

The purpose of the conference is to present current research in The Theory of Computing as well as to discuss its future in many areas. These include complexity-theory, Boolean-functions, cryptography, learning, algorithmic game-theory and discrete mathematics.

Eitan Bachmat : An old disk scheduling algorithm revisited

Michal Feldman: Algorithmic Contract Design

Yael Tauman Kalai: Recent Advancement in SNARGs

Pravesh Kothari : The Kikuchi Matrix Method

 

Noam Lifshitz: Product free sets in the alternating group

 

Shachar Lovett: The monomial structure of Boolean function

Assaf Naor: Reverse isoperimetry

Aviad Rubinstein: Approximate maximum matching, and fantasies about SETH, obfuscation, and you

Amir Yehudayoff: Characterizations of Learnability

Cryptography seminar @TAU TheoryFest December 29, 2022

Shafi Goldwasser: The Right to Deny

Alon Rosen: Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

Ran Canetti: On the Computational Hardness Needed for Quantum Cryptography

Moni Naor (Weizmann): Timing Attacks on Cryptographic and Privacy Preserving Schemes: Revisiting the Resistance

Links to previous events:

TAU Theory Fest 2019

PCP Fest 2018