Theory of Computing Report (@theory.report)

Updates and Plans V: From Boise to Tel Aviv, Ceasefire, My 70th Birthday, Nostalgia, Problems, Outrageous Conjectures, Quantum, and AI <p>This is the fifth post of this type (<a href="https://gilkalai.wordpress.com/2008/08/13/plans-and-updates/">I (2008)</a>; <a href="https://gilkalai.wordpress.com/2011/06/14/tentative-plans-and-belated-updates-ii/">II(2011)</a>; <a href="https://gilkalai.wordpress.com/2015/08/14/updates-and-plans-iii/">III(2015)</a>; <a href="https://gilkalai.wordpress.com/2024/03/20/updates-and-plans-iv/">IV(2024</a><a href="https://gilkalai.wordpress.com/2024/03/20/updates-and-plans-iv/">)</a>).</p> <h2>Between Boise and Tel Aviv</h2> <p>During the summer we spent two months in the lovely city of Boise, Idaho. We stayed with my son Hagai and his husband Felix, their one-and-a-half-year-old son Yonatan, and—one week after our arrival—their second son, Rafael, was born. I was visiting Boise State University and was hosted by Zach Teitler, whom I first met many years ago at Texas A&M.</p> <p>Boise is a beautiful city with wonderful parks, and Mazi and I also devoted a week to visiting Yellowstone for the first time.</p> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/fam25.jpg"><img alt="" class="alignnone wp-image-31109" height="490" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/fam25.jpg?w=560" width="268" /></a></p> <p><span style="color: #ff0000;">On the flight back with Hagai, Rafael, Mazi, and Yonatan</span></p> <h2>Ceasefire in Gaza</h2> <p>On September 29, 2025, US president Donald Trump put forward a 21-point plan for a ceasefire in Gaza, as part of a broader initiative toward peace in the Middle East. The plan was endorsed by many world leaders, including Arab and Muslim leaders, as well as by the Israeli government headed by Benjamin Netanyahu. On October 9, an agreement was reached between Israel and Hamas on a ceasefire, a partial withdrawal of Israeli forces, and the release of kidnapped Israelis. On October 13, all living kidnapped Israelis were released. By January 27, 2026, all bodies of Israelis were returned.</p> <p>The end of this terrible war is certainly a source of relief and hope. Still, we are living in dangerous and tragic times, with much uncertainty.</p> <h2>My 70th Birthday</h2> <p>We landed back in Tel Aviv on October 1, the eve of Yom Kippur. The following day—somewhat to my surprise—was my 70th birthday. Two weeks later, on Simchat Torah (October 14), we gathered to celebrate the holiday, the birthday, the new family member, and the end of the war. Being 70 years old feels sort of strange. </p> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/img-20251018-wa00012.jpg"><img alt="" class="alignnone wp-image-31110" height="234" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/img-20251018-wa00012.jpg?w=640" width="508" /></a></p> <h2>Nostalgia Corner and Congratulations to Benjy Weiss</h2> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/wi-mo.png"><img alt="" class="alignnone wp-image-31177" height="286" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/wi-mo.png" width="177" /></a></p> <p><span style="color: #ff0000;">“secretly jubilant”</span> </p> <p>I recently found, in my sister’s home (where we both lived as children), a <em>Jerusalem Post</em> article from 1970 about the Israeli Mathematical Olympiad. In that competition I received a consolation prize, while my friend <a href="https://en.wikipedia.org/wiki/Ron_Donagi">Ron Donagi</a> received the first price. Here is a quote from the article: ” ‘The prize is much more than I expected,’ stated an apparently indifferent yet secretly jubilant Gil.”</p> <p>The reporter, Mark Daniel Sacks, also expressed his wish for similar encouragement for “those of us who are interested in literature, poetry, philosophy, and art.” I fully agree!</p> <p>A few months earlier, in the fall of 1969, I began attending Benjy Weiss’s year-long mathematics course for high-school students, together with 20–25 other students, including <a href="https://cee.technion.ac.il/en/members/agnon/">Yehuda Agnon</a>, <a href="http://www.cs.huji.ac.il/~benor/">Michael Ben-Or</a>, <a href="https://en-exact-sciences.tau.ac.il/profile/lehrer" rel="noopener" target="_blank" title="Ehud Lehrer">Ehud Lehrer</a>, <a href="https://www.bc.edu/bc-web/schools/morrissey/departments/economics/people/faculty-directory/uzi-segal.html">Uzi Segal</a> , <a href="https://en.wikipedia.org/wiki/Yonatan_Stern">Yonatan Stern</a>, and <a href="http://www.cs.huji.ac.il/~werman/" rel="noopener" target="_blank" title="Mike Werman">Mike Werman.</a> The course was an eye-opener for all of us.</p> <p>It has just been announced that our teacher, Benjy Weiss, has won the 2026 Israel Prize in Mathematics. Heartfelt congratulations, Benjy!</p> <h2>Problems, Problems </h2> <p>Over the years I have devoted quite a few posts—here, on other blogs, and on MathOverflow—to open problems. In 2013, at the <a href="http://www.renyi.hu/conferences/erdos100/">Erdős Centennial conference</a>, I gave a lecture on old and new problems, mainly in combinatorics and geometry (<a href="https://gilkalai.wordpress.com/wp-content/uploads/2013/07/erdos100-20.pdf">here are the slides</a>), where I presented twenty problems that are also listed in <a href="https://gilkalai.wordpress.com/2013/07/06/some-old-and-new-problems-in-combinatorics-and-geometry/">this post</a>. Since then, there has been substantial progress, and in some cases full solutions, for roughly 30% of them. </p> <p>I gradually plan, somewhat in Erdős’ tradition, to upgrade my problem posts and lectures into papers.</p> <p>So far, in 2015 I wrote <a href="https://arxiv.org/abs/1505.04952">a paper</a> around Borsuk’s problem. (Some of the problems appeared in <a href="https://gilkalai.wordpress.com/tag/borsuks-conjecture/">these posts</a>.) In 2022, Imre Barany and I wrote a survey article on <a href="https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://www.ams.org/bull/2022-59-04/S0273-0979-2021-01753-8/S0273-0979-2021-01753-8.pdf&ved=2ahUKEwi9gbaCtrGSAxURRqQEHRTAIrQQFnoECCkQAQ&usg=AOvVaw37HeOdq-BfeM6-WYkf7LYu">Helly-type problems</a>, which was nicely accepted. I am currently writing a paper about the diameter problem for graphs of polytopes. We devoted many posts—and <a href="https://gilkalai.wordpress.com/category/polymath3/">Polymath 3</a>—to this problem, and I plan to submit the paper to the new and splendid journal JOMP: <a href="https://jomprob.org/index.php/jomp">the Journal of Open Math Problems</a>.</p> <h3>Geometric Combinatorics</h3> <p>There are many open problems that I like—and quite a few that I myself posed—concerning the combinatorial theory of convex polytopes, face numbers of polytopes, and related cellular objects. <a href="https://gilkalai.wordpress.com/2008/05/07/five-open-problems-regarding-convex-polytopes/">This post</a> from 2008 lists five elementary problems and since then one problem was solved. One outstanding problem in the field that I like is whether triangulated spheres are determined from their dual graphs. This is known for simplicial polytopes (see <a href="https://gilkalai.wordpress.com/2009/01/16/telling-a-simple-polytope-from-its-graph/">this post</a> from 2009) and was recently proved for all shellable simplicial spheres by Yirong Yang in her paper <a href="https://arxiv.org/abs/2401.04220"><span class="search-hit mathjax">Reconstructing</span> a Shellable Sphere from its Facet-Ridge Graph</a>. </p> <p>Let me mention two problems from other areas of combinatorial geometry.</p> <p>Two triangles are called <em>almost disjoint</em> if they are either disjoint or their intersection consists of one common vertex. Let <em>f(n)</em> denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of <em>n</em> points in 3-space. How large can <em>f(n)</em> be? It is easy to see that <em>f(n)</em> is at most quadratic in <img alt="n" class="latex" src="https://s0.wp.com/latex.php?latex=n&bg=ffffff&fg=333333&s=0&c=20201002" /> and the <a href="http://chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://link.springer.com/content/pdf/10.1007/s00454-002-2888-z.pdf">best lower bound</a> from 2002 by Karolyi and Solmyosi is <img alt="f(n)=\Omega (n^{3/2})" class="latex" src="https://s0.wp.com/latex.php?latex=f%28n%29%3D%5COmega+%28n%5E%7B3%2F2%7D%29&bg=ffffff&fg=333333&s=0&c=20201002" />. There is a <a href="https://arxiv.org/abs/1705.01272">related work</a> from 2017 by Solmyosi and Wong. </p> <p>In 1995, Nati Linial and I conjectured that the kissing number for lattice sphere packings in <img alt="\mathbb R^n" class="latex" src="https://s0.wp.com/latex.php?latex=%5Cmathbb+R%5En&bg=ffffff&fg=333333&s=0&c=20201002" /> is subexponential in <img alt="n" class="latex" src="https://s0.wp.com/latex.php?latex=n&bg=ffffff&fg=333333&s=0&c=20201002" />. The highest known kissing number behaves like <img alt="n^{\log n}" class="latex" src="https://s0.wp.com/latex.php?latex=n%5E%7B%5Clog+n%7D&bg=ffffff&fg=333333&s=0&c=20201002" />. Our problem was related to the question of finding <em>upper bounds</em> for the density of sphere packings in high dimension. Recent <a href="https://gilkalai.wordpress.com/2025/04/09/boaz-klartag-striking-new-lower-bounds-for-sphere-packing-in-high-dimensions/">celebrated work</a> of Klartag shows an intriguing connection between kissing numbers and <em>lower bounds</em> on sphere-packing density.</p> <h3>Analysis of Boolean Functions and Probabilistic Combinatorics</h3> <p>In a <a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/fourier.pdf">draft paper from 2000</a> (which I mostly distributed privately), I listed 18 interesting phenomena and 23 problems around these phenomena related to Boolean functions and their Fourier expansion. Since then there were many developments in the analysis of Boolean functions. Here is a <a href="https://simons.berkeley.edu/sites/default/files/openprobsmerged.pdf">comprehensive list</a> of open problems from 2014. One problem in the list was <a href="https://arxiv.org/abs/2510.20013v1">recently solved</a> by GPT5. I myself posed quite a few problems in this area but let me mention today the still open Aaronson-Ambainis conjecture from 2008: for every function <img alt="f:\{-1,1\}^n\to [-1,1]" class="latex" src="https://s0.wp.com/latex.php?latex=f%3A%5C%7B-1%2C1%5C%7D%5En%5Cto+%5B-1%2C1%5D&bg=ffffff&fg=333333&s=0&c=20201002" /> of degree at most <img alt="k" class="latex" src="https://s0.wp.com/latex.php?latex=k&bg=ffffff&fg=333333&s=0&c=20201002" />, there exists a variable <img alt="k" class="latex" src="https://s0.wp.com/latex.php?latex=k&bg=ffffff&fg=333333&s=0&c=20201002" /> with influence at least <img alt="(V(f)/k)^C" class="latex" src="https://s0.wp.com/latex.php?latex=%28V%28f%29%2Fk%29%5EC&bg=ffffff&fg=333333&s=0&c=20201002" />, for some constant <img alt="C" class="latex" src="https://s0.wp.com/latex.php?latex=C&bg=ffffff&fg=333333&s=0&c=20201002" />. <img alt="V(f)" class="latex" src="https://s0.wp.com/latex.php?latex=V%28f%29&bg=ffffff&fg=333333&s=0&c=20201002" /> stands for the variance of <img alt="f" class="latex" src="https://s0.wp.com/latex.php?latex=f&bg=ffffff&fg=333333&s=0&c=20201002" />. </p> <p>In probabilistic combinatorics, the “Kahn-Kalai conjecture” from our 2006 paper has been <a href="https://arxiv.org/abs/2203.17207">famously solved</a> by Park and Pham and a second conjecture about graphs <a href="https://arxiv.org/abs/2508.14269">was settled</a> – up to <img alt="\log^2 n" class="latex" src="https://s0.wp.com/latex.php?latex=%5Clog%5E2+n&bg=ffffff&fg=333333&s=0&c=20201002" /> factor by Dubroff, Kahn, and Park. </p> <p>Jeff Kahn and I regarded the conjecture as outrageous—and likely false—but in that paper we formulated several specific conjectures (in the area of discrete isoperimetric inequalities) as part of a broader program for proving it. In spite of <a href="https://www.ams.org/journals/jams/2024-37-01/S0894-0347-2023-01027-6/">some substantial progress</a>, these conjecture remain largely open, although a few have been refuted. One of those conjectures is presented in <a href="https://mathoverflow.net/questions/10799/optimal-monotone-families-for-the-discrete-isoperimetric-inequality">this MO post</a>. In principle, the Kruskal-Katona theorem should suffice to settle this problem, but still we cannot solve it. </p> <h3>Extremal Combinatorics</h3> <p>One question I <a href="https://mathoverflow.net/questions/114646/intersecting-family-of-triangulations">asked</a>—independently also posed by Karen Meagher—concerned the independence numbers of intersection graphs of triangulations. This conjecture is still open and it admits a lovely <a href="https://arxiv.org/abs/1710.02518">generalization for a large class of polytopes</a>. Recently, Anton Molnar, Cosmin Pohoata, Michael Zheng, and Daniel G. Zhu raised the question of finding the chromatic number of the intersection graphs of triangulations—<a href="https://arxiv.org/abs/2510.27689">and solved it</a>! They showed that the Kneser graph of triangulations of a convex <em>n</em>-gon has chromatic number <img alt="n-2" class="latex" src="https://s0.wp.com/latex.php?latex=n-2&bg=ffffff&fg=333333&s=0&c=20201002" />.<span class="MathJax" id="MathJax-Element-2-Frame"><span class="math" id="MathJax-Span-4"> </span></span></p> <h3>Computation Complexity and Number Theory</h3> <p>Around 2010, I formulated several conjectures relating computational complexity and number theory, which led to some very nice developments. Together with Mrinal Kumar and Ben Lee Volk, I plan to write a paper with further problems connecting algebraic circuit complexity and number theory.</p> <h2>Two Outrageous Conjectures</h2> <p>Here are two very outrageous conjectures that may well admit simple refutations.(Comments are welcome; the right thing to do would be to devote a separate post to each of then, stay tuned.) </p> <p>The first outrageous conjecture is presented in this slide from a 2024 lecture. </p> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/zfc-nt.png"><img alt="" class="alignnone wp-image-31154" height="312" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/zfc-nt.png?w=640" width="541" /></a></p> <p>See also this <a href="https://mathoverflow.net/questions/135948/infinitely-many-primes-and-mobius-randomness-in-sparse-sets">MO question</a> and <a href="https://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable">this one</a>.</p> <p>The second vague and outrageous conjecture (already mentioned earlier in <a href="https://gilkalai.wordpress.com/2013/08/08/poznan-random-structures-and-algorithms-2013/">this post</a>) is about computational complexity and more precisely about Papadimitriou’s computational hierarchy for mathematical proofs. It asserts that theorems guaranteeing the existence (for sure, not just with high probability) of combinatorial structures and whose proofs are based on the probabilistic method, are accompanied by an efficient algorithm (possibly randomized) for finding this structures. (In other words, the probabilistic method does not lead to a new Papadimitriou class beyond <strong>P</strong>.)</p> <h2>Quantum Information and Quantum Physics</h2> <p>It is likely that the proportion of posts dealing with quantum computing and quantum physics will increase. So far, they account for about 8% of all posts since I began blogging. My interest in this area has branched into several related directions.</p> <h3>The Argument Against Quantum Computing</h3> <p>The direction closest to my heart is <a href="https://gilkalai.wordpress.com/2020/12/29/the-argument-against-quantum-computers-a-very-short-introduction/">the argument against quantum computing</a>. I have invested considerable effort in explaining and discussing my theory for why quantum computers are inherently impossible—through papers, lectures, debates, and blog posts. I try not to oversell the case, and I think that ultimately, experiments are likely to provide the clearest way to decide the matter.</p> <h3>Correlated Errors </h3> <p>A related but distinct issue concerns the modeling of correlated errors, which was central in my research between 2005 and 2012, and more generally the behavior (and modeling) of noisy quantum systems that do not exhibit quantum fault tolerance. Here too, experiments and simulations can provide significant insight, and my (admittedly bold) conjectures about error correlations could be tested directly.</p> <h3>Statistical Analysis of Experimental Data</h3> <p>Another topic is the statistical analysis of current experimental data. With my coauthors we devoted substantial effort to analyzing Google’s 2019 experiment, and I believe more can be done to clarify and explain the findings of our papers. Our long-going project is closely related to developing statistical tools for analyzing quantum measurements and modeling noise. A recent paper on this topic by another group is: <a href="https://arxiv.org/abs/2510.09919">How much can we learn from quantum random circuit sampling?</a> by Manole et al.</p> <h3>Quantum Puzzles</h3> <p>I also plan a series of posts devoted to quantum puzzles related to quantum information and computation. The <a href="https://gilkalai.wordpress.com/2025/02/21/majorana-zero-modes-and-topological-qubits/">first post</a> concerned Majorana zero modes. Whether Majorana zero modes can in fact be created remains a major mystery in physics, and I personally suspect the answer may be negative. (As with “quantum supremacy,” their realization has been claimed by several research groups.) Planned follow-up posts will address quantum cryptography and the time–energy uncertainty principle.</p> <h3>Free Will</h3> <p>I plan to return to the fascinating connections between quantum physics, computation, and free will. I wrote a paper on this topic in 2021, and we discussed it in <a href="https://gilkalai.wordpress.com/2021/08/18/to-cheer-you-up-in-difficult-times-29-free-will-predictability-and-quantum-computers/">this blog post</a>. Since then, I participated in two conferences in Nazareth, in 2022 and 2024, devoted to free will (here are the <a href="https://www.youtube.com/channel/UCakLAZnGwNU58VHd4AkUJeA/videos">videotaped lectures</a> – in Hebrew). Following these conference and my paper, I have had many stimulating discussions with colleagues from a wide variety of disciplines. </p> <h3>Is Quantum Computational Advantage Manifested by Nature? Has it been Achieved by Experiments?</h3> <p>This question lies at the heart of the matter and connects to all the topics above. In a recent lecture, <a href="https://phsites.technion.ac.il/avron/">Yosi Avron</a> mentioned an argument—possibly going back to Feynman—that quantum physics in Nature already exhibits “quantum supremacy”: computing the magnetic moments of the proton or neutron from first principles is extraordinarily difficult and yields estimates far from experimental values, yet protons and neutrons “compute” their magnetic moments effortlessly. In the same lecture, delivered at a celebratory meeting for the 100th anniversary of quantum mechanics at the Open University in Ra’anana, Yosi also argued that no country can afford to lag behind in quantum computation, drawing an analogy with nuclear capabilities.</p> <h2>Computers, AI and Mathematics</h2> <p>Like many others, I plan to experiment with modern AI tools in the hope of using them for meaningful mathematical research. I am cautiously optimistic—perhaps naïve. Let’s see how it goes.</p> <h2>Pictures</h2> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250818_102009.jpg"><img alt="" class="alignnone wp-image-31126" height="214" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250818_102009.jpg?w=640" width="286" /> </a><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250805_182317.jpg"><img alt="" class="alignnone wp-image-31135" height="210" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250805_182317.jpg?w=640" width="281" /></a></p> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250830_172855.jpg"><img alt="" class="alignnone wp-image-31127" height="203" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250830_172855.jpg?w=640" width="271" /> </a><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250830_150254.jpg"><img alt="" class="alignnone wp-image-31128" height="205" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250830_150254.jpg?w=640" width="274" /></a></p> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250901_102846.jpg"><img alt="" class="alignnone wp-image-31130" height="138" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250901_102846.jpg?w=640" width="299" /> </a><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250901_111019.jpg"><img alt="" class="alignnone wp-image-31129" height="137" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250901_111019.jpg?w=640" width="297" /></a></p> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250902_122042.jpg"><img alt="" class="alignnone wp-image-31131" height="130" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250902_122042.jpg?w=640" width="282" /> </a><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/screenshot_20250902_103045_gallery.jpg"><img alt="" class="alignnone wp-image-31132" height="132" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/screenshot_20250902_103045_gallery.jpg?w=640" width="286" /></a></p> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/artpoint1.png"><img alt="" class="alignnone wp-image-31159" height="138" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/artpoint1.png?w=640" width="283" /> </a><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250901_091848.jpg"><img alt="" class="alignnone wp-image-31160" height="135" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250901_091848.jpg?w=640" width="293" /></a></p> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250824_114037.jpg"><img alt="" class="alignnone wp-image-31134" height="177" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/20250824_114037.jpg?w=640" width="237" /> </a><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/rabbit.png"><img alt="" class="alignnone wp-image-31136" height="174" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/rabbit.png?w=640" width="296" /></a></p> <p><a href="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/img-20260127-wa0009.jpg"><img alt="" class="alignnone wp-image-31138" height="179" src="https://gilkalai.wordpress.com/wp-content/uploads/2026/01/img-20260127-wa0009.jpg?w=640" width="388" /></a></p> <p><span style="color: #ff0000;">Top row: Boise with Zach Teitler, Alexander Woo and Bruce Sagan’s classical book, and with local convex polytopes. Second row: sightseeing near Boise. Third, fourth, and fifth rows: Yellowstone. Sixth row: Yonatan in Boise. Seventh row: Mazi and I with Ilan and Yoav in Tel Aviv. </span></p> <p> </p> <p> </p> <p class="wp-block-paragraph"></p> <p class="authors">By Gil Kalai</p> https://gilkalai.wordpress.com/2026/02/03/updates-and-plans-v-from-boise-to-tel-aviv-ceasefire-my-70th-birthday-nostalgia-problems-outrageous-conjectures-quantum-and-ai/