Theory of Computing Report @theory.report

When is String Reconstruction using de Bruijn Graphs Hard? **Authors:** Ben Bals, Sebastiaan van Krieken, Solon P. Pissis, Leen Stougie, Hilde Verbeek The reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly. This reduction employs the notion of de Bruijn graph $G=(V,E)$ of order $k$ over an alphabet $\Sigma$. A single Eulerian trail in $G$ represents a candidate genome reconstruction. Bernardini et al. have also introduced the complementary idea in data privacy [ALENEX 2020] based on $z$-anonymity. The pressing question is: How hard is it to reconstruct a best string from a de Bruijn graph given a function that models domain knowledge? Such a function maps every length-$k$ string to an interval of positions where it may occur in the reconstructed string. By the above reduction to de Bruijn graphs, the latter function translates into a function $c$ mapping every edge to an interval where it may occur in an Eulerian trail. This gives rise to the following basic problem on graphs: Given an instance $(G,c)$, can we efficiently compute an Eulerian trail respecting $c$? Hannenhalli et al.~[CABIOS 1996] formalized this problem and showed that it is NP-complete. We focus on parametrization aiming to capture the quality of our domain knowledge in the complexity. Ben-Dor et al. developed an algorithm to solve the problem on de Bruijn graphs in $O(m \cdot w^{1.5} 4^{w})$ time, where $m=|E|$ and $w$ is the maximum interval length over all edges. Bumpus and Meeks [Algorithmica 2023] rediscovered the same algorithm on temporal graphs, highlighting the relevance of this problem in other contexts. We give combinatorial insights that lead to exponential-time improvements over the state-of-the-art. For the important class of de Bruijn graphs, we develop an algorithm parametrized by $w (\log w+1) /(k-1)$. Our improved algorithm shows that it is enough when the range of positions is small relative to $k$.

06.08.2025 00:00 — 👍 0 🔁 0 💬 0 📌 0

TR25-116 | Supercritical Tradeoff Between Size and Depth for Resolution over Parities | Dmitry Itsykson, Alexander Knop Alekseev and Itsykson (STOC 2025) proved the existence of an unsatisfiable CNF formula such that any resolution over parities (Res($\oplus$)) refutation must either have exponential size (in the formula size) or superlinear depth (in the number of variables). In this paper, we extend this result by constructing a formula with the same hardness properties, but which additionally admits a resolution refutation of quasi-polynomial size. This establishes a supercritical tradeoff between size and depth for resolution over parities. The proof builds on the framework of Alekseev and Itsykson and relies on a lifting argument applied to the supercritical tradeoff between width and depth in resolution, proposed by Buss and Thapen (IPL 2026).

05.08.2025 21:50 — 👍 0 🔁 0 💬 0 📌 0

Full professorship (W3) at Saarland University (apply by September 18, 2025) We seek candidates with a strong research record in theoretical computer science, with a focus on algorithms, computational complexity, algorithmic game theory, algorithms engineering or related areas. There are numerous opportunities for collaborative research with other institutes on campus, in particular with the algorithms and complexity group of the Max-Planck Institute. Website: https://www.uni-saarland.de/fileadmin/upload/verwaltung/stellen/Wissenschaftler/W2672_Professorship__W3__in_Algorithms_and_Complexity.pdf Email: mblaeser@cs.uni-saarland.de By shacharlovett

05.08.2025 09:22 — 👍 0 🔁 0 💬 0 📌 0

Facility Location and $k$-Median with Fair Outliers **Authors:** Rajni Dabas, Samir Khuller, Emilie Rivkin Classical clustering problems such as \emph{Facility Location} and \emph{$k$-Median} aim to efficiently serve a set of clients from a subset of facilities -- minimizing the total cost of facility openings and client assignments in Facility Location, and minimizing assignment (service) cost under a facility count constraint in $k$-Median. These problems are highly sensitive to outliers, and therefore researchers have studied variants that allow excluding a small number of clients as outliers to reduce cost. However, in many real-world settings, clients belong to different demographic or functional groups, and unconstrained outlier removal can disproportionately exclude certain groups, raising fairness concerns. We study \emph{Facility Location with Fair Outliers}, where each group is allowed a specified number of outliers, and the objective is to minimize total cost while respecting group-wise fairness constraints. We present a bicriteria approximation with a $O(1/\epsilon)$ approximation factor and $(1+ 2\epsilon)$ factor violation in outliers per group. For \emph{$k$-Median with Fair Outliers}, we design a bicriteria approximation with a $4(1+\omega/\epsilon)$ approximation factor and $(\omega + \epsilon)$ violation in outliers per group improving on prior work by avoiding dependence on $k$ in outlier violations. We also prove that the problems are W[1]-hard parameterized by $\omega$, assuming the Exponential Time Hypothesis. We complement our algorithmic contributions with a detailed empirical analysis, demonstrating that fairness can be achieved with negligible increase in cost and that the integrality gap of the standard LP is small in practice.

05.08.2025 00:00 — 👍 0 🔁 0 💬 0 📌 0

Some thoughts on journals, refereeing, and the P vs NP problem _A guest post by Eric Allender prompted by an_ _(incorrect) P ≠ NP proof_ _recently published in Springer Nature's Frontiers of Computer Science._ For a time, I served as Editor-in-Chief of ACM Transactions on Computation Theory, and in this role I had to deal regularly with submissions that claimed to resolve the P vs NP problem. Finding referees for these papers was sometimes challenging, so I frequently ended up reviewing them myself. Dealing with such submissions involves enough overhead that ToCT, J.ACM and ACM Transactions on Algorithms limit the frequency with which authors can submit work of this sort. But for every submission, on any topic, the overall process was the same: Find someone on the Editorial Board who has sufficient expertise to find referees and make knowledgeable use of their recommendations. If there was no such person on the Editorial Board, then it was always the case that the submission was out of scope for the journal. These thoughts are brought to mind by a recent case, where it seems to me that the editorial process broke down. Springer publishes several high-quality academic journals that deal with Theoretical Computer Science. One Springer journal, Frontiers of Computer Science, recently published an article entitled SAT Requires Exhaustive Search, where one of the authors is a Deputy Editor-in-Chief of the journal. The abstract of the article states that it proves a result that is stronger than P not equal to NP. The Editorial Board of the journal has some members who are expert in computational complexity theory. However, all the ones whom I know personally have asserted that they had no knowledge of this paper, and that they were not involved at all in handling the paper. When Ryan Williams and I learned about the publication of this article, we drafted a comment, which we sent to the Editor-in-Chief. We recommended that the paper be retracted, in which case there would be no need to publish our comment. However, the Editor-in-Chief declined to retract the article, saying that he could find no evidence of misconduct, and thus we have been assured that an edited version of our comment will appear in the journal. Our comment calls attention to some shortcomings in the proof of the main theorem (similar to shortcomings in several other failed attempts to separate P from NP). But we were able to say more. Often, when one is looking for bugs in a purported proof, one has to deal with the situation where the claimed theorem is probably true, and the only problem is that the proof is not convincing. However, the main theorem in their paper (Theorem 3.2) states that a particular constraint satisfaction problem requires time more than \$d^{cn}\$ for any constant \$c<1\$ (where \$d\$ is the domain size, and \$n\$ is the number of variables). In particular, their purported proof claims that this holds even when \$k=2\$ (meaning that each constraint has at most 2 variables). However, Ryan Williams presented an algorithm more than two decades ago that runs in time \$O(d^{(0.8)n})\$ in this special case, contradicting the lower bound claimed in the article. The article contains an appendix, with glowing testimonies from various researchers; the lead-in to the appendix also contains enthusiastic comments from Gregory Chaitin. I contacted Gregory Chaitin, and he asserts that he did not read the paper, and that he was quoted out of context. The edited version of the comment that Ryan Williams and I wrote, which will supposedly appear in Frontiers of Computer Science soon, differs from the version linked here (our original submission) primarily in one respect: Our closing paragraph was removed. Here is that paragraph: > Finally, it is our opinion that the publication of this article is a complete embarrassment to this journal and its publisher. We believe that, at the very least, the paper should be withdrawn, and Springer should conduct an investigation to understand how such a paper could have made it through the peer review process. By Lance Fortnow

04.08.2025 16:46 — 👍 0 🔁 0 💬 0 📌 0

Announcing The Irrational Decision I’ve mentioned it obliquely many times on the blog, and I’m excited to finally be able to announce that my book, _The Irrational Decision_ , is available for pre-order from Princeton University Press. (Preorder your copy here! Princeton, Bookshop, Amazon) As the title suggests, this book is about rationality. But it’s about a very particular kind of instrumental, mathematical rationality that seems to dominate our contemporary discourse, where everything is a risk analysis or a bet. It’s the mathematical rationality that is popular with people who spend too much time around computers, be they the hyper-online rationalists, public intellectuals like Nate Silver or Steven Pinker, or our oligarchical billionaires. It’s the rationality where everything is about maximizing ends by whatever means necessary. The word rational can mean a lot of things. Why did this rigid definition become so dominant among the tech set? It’s because the tech set _invented_ this form of rationality when they were first building computers in the wake of World War II. _The Irrational Decision_ traces how we came to believe that decisions in the face of uncertainty could be made through cold, mathematical calculation. As the title suggests, I think that conclusion is irrational, and the book explains how this formulation of mathematical rationality, while useful in many contexts, has always been known to be fundamentally limited, applicable only in particular sweet spots. The irrationality is the persistence that we can outsource everything to computers, despite decades of persistent evidence that this can’t work. If we want to make “rational” decisions by math, we have to transform the world we experience into a mathematical model. We have to equate everything unknown with a mathematical language, which is usually the language of probability. We need to put all goals on the same playing field by associating them with a universal currency (we could call it utilitycoin). Once you write the equations about randomness and profits, a rational agent assesses the probability of various futures and chooses its action to maximize its returns. Hence, the mathematical version of rationality reduces all decision-making to a statistical analysis of risk. According to the contemporary rationalists—if we take them at their word—the only truly rational agent is the actuary. A completely robotic, computational insurance agent. An actuarial android. A paranoid android. Life is not a matter of pricing annuities. Why would we call it rational to treat it this way? This question emerged _after_ I started this project. Initially, I just wanted to understand why we kept reinventing the wheel in machine learning. Why was it that after 50 years of innovation, we circled back to a somewhat fancy version of Rosenblatt’s Perceptron in the 2010s? Was the perceptron also just a rehash of something from the 1890s? To my surprise, the answer was no. The following technologies were all invented in the window between World War II and the IBM 701: * language models * information theory * linear programming * signal estimation theory * detection theory * game theory * stochastic gradient descent * neural networks * the randomized clinical trial I could go on, of course. We built computers to solve these problems and to systematize decision making. In building them, the designers of the modern computer baked in a particular mindset of what an ideal decision looked like. This ideal became a mirror in which we could see the imperfection of people. We decided people should make decisions like computers. The problem is, this decision was irrational. We can only optimize simple problems. Parlor games don’t describe how people behave. Most of these tabulatory, numerical tools are natural fits for regulatory bureaucracy, but not for running your life. Mathematical rationality helps frame simple, _small world_ decisions (see this excellent and excellently timed post by Max Raginsky). The vast majority of decisions can’t be outsourced to computers. While many people have written arguments to that effect before, _The Irrational Decision_ explores the thinking of the mathematicians and engineers who built the fundamental algorithmic backbone. I wrote this book as a participant observer in the subject area, having spent a career steeped in the practice of machine learning, optimization, and statistics. I leveraged my connections there, speaking with as many colleagues as I could to gather contemporary perspectives on the historical lineage. I explore the intellectual history of automated decision making, engaging with the technical work of the intellectuals who took us down this path. _The Irrational Decision_ will __ be out in early 2026. On the one hand, the slowness of book publishing drives me crazy. I’m very impatient, which is why I blog. But blogs are just first drafts of thoughts, and I know I put blog posts out faster than anyone else wants to read them. Blogging remains my process of writing practice and thought drafting. Lots of the ideas in the book __ were workshopped on here. That you all read it is a gift to me that I deeply appreciate. Books are immutable final drafts. The permanence is a mixed blessing, as I change my mind all the time. But I do think _The Irrational Decision_ compiles a specific web of stories that deserves a physical binding.1 It is a snapshot of the history of this technology and how it interfaces with our contemporary practices. It’s about how the same core ideas have been simmering for 80 years, continuously circled back to as we build progressively more powerful computing machines. I tried to make this history of the mathematical scaffolding of the computer age accessible to as many people as possible. I wrote the book for people who work in computer science or related computational fields (I suppose we call this “data science” now?). I’ve used the text in my machine learning classes, and I think parts could be assigned to undergrads. Contextualizing _why_ we do what we do is helpful to make sense of our current computing craze. The core intellectual idea of the latest AI bubble is taking the initial ideas from the 1940s and riding them to their logical conclusion. Either our tech overlords are right and they’ll build a superintelligence that enslaves humanity, or, even after covering the planet in data centers, there is still work to be done. I’m hoping this book points at ways to think about what we do if that second scenario plays out. I will further explore such alternatives in future projects, many of which you’ve seen seeds of on this blog. How we can conceptualize individual risk in non-probabilistic language. How we can stop the moral outsourcing of our choices to machines. How we can’t mechanism-design our way to utopia. _The Irrational Decision_ is chapter one. Stick around here as we draft chapter two. Subscribe now 1 I suppose I could have just thrown the book up on arxiv, but I’m excited to see where this more traditional publishing path takes me. By Ben Recht

04.08.2025 13:59 — 👍 0 🔁 0 💬 0 📌 0

Robust Model Reconstruction Based on the Topological Understanding of Point Clouds Using Persistent Homology **Authors:** Yu Chen, Hongwei Lin Reconstructing models from unorganized point clouds presents a significant challenge, especially when the models consist of multiple components represented by their surface point clouds. Such models often involve point clouds with noise that represent multiple closed surfaces with shared regions, making their automatic identification and separation inherently complex. In this paper, we propose an automatic method that uses the topological understanding provided by persistent homology, along with representative 2-cycles of persistent homology groups, to effectively distinguish and separate each closed surface. Furthermore, we employ Loop subdivision and least squares progressive iterative approximation (LSPIA) techniques to generate high-quality final surfaces and achieve complete model reconstruction. Our method is robust to noise in the point cloud, making it suitable for reconstructing models from such data. Experimental results demonstrate the effectiveness of our approach and highlight its potential for practical applications.

04.08.2025 00:00 — 👍 0 🔁 0 💬 0 📌 0

Generalized cluster algorithms for Potts lattice gauge theory **Authors:** Anthony E. Pizzimenti, Paul Duncan, Benjamin Schweinhart Monte Carlo algorithms, like the Swendsen-Wang and invaded-cluster, sample the Ising and Potts models asymptotically faster than single-spin Glauber dynamics do. Here, we generalize both algorithms to sample Potts lattice gauge theory by way of a $2$-dimensional cellular representation called the plaquette random-cluster model. The invaded-cluster algorithm targets Potts lattice gauge theory at criticality by implementing a stopping condition defined in terms of homological percolation, the emergence of spanning surfaces on the torus. Simulations for $\mathbb Z_2$ and $\mathbb Z_3$ lattice gauge theories on the cubical $4$-dimensional torus indicate that both generalized algorithms exhibit much faster autocorrelation decay than single-spin dynamics and allow for efficient sampling on $4$-dimensional tori of linear scale at least $40$.

21.07.2025 00:00 — 👍 0 🔁 0 💬 0 📌 0

TR25-101 | Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis | Yogesh Dahiya, Arkadev Chattopadhyay, Shachar Lovett A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the function, and the minimal degree of a real polynomial that point-wise approximates the function, are at most polynomially separated. Extending this result from degree to other complexity measures like sparsity of the polynomial representation, or total weight of the coefficients, remains poorly understood. In this work, we consider this problem in the De Morgan basis, and prove an analogous result for the sparsity of the polynomials at a logarithmic scale. Our result further implies that the exact $\ell_1$ norm and its approximate variant are also similarly related to each other at a log scale. This is in contrast to the Fourier basis, where the analog of our results are known to be false. Our proof is based on a novel random restriction method. Unlike most existing random restriction methods used in complexity theory, our random restriction process is adaptive and is based on how various complexity measures simplify during the restriction process.

20.07.2025 05:09 — 👍 0 🔁 0 💬 0 📌 0

TR25-100 | Equality is Far Weaker Than Constant-Cost Communication | Artur Riazanov, Mika Göös, Nathaniel Harms We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{\Omega(1)}$ deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of Hatami and Hatami (SIGACT News 2024). It also gives a significantly simpler and quantitatively superior proof of the main result of Fang, Göös, Harms, and Hatami (STOC 2025), that constant-cost communication does not reduce to the $k$-Hamming Distance hierarchy.

20.07.2025 05:08 — 👍 0 🔁 0 💬 0 📌 0

Twenty years of blogging I made my first post to this blog twenty years ago, on July 20, 2005. Initially, it was on LiveJournal, and consisted of a mix of longer-form postings with the sort of brief commentary on web links that, today, I would post as a Mastodon toot. The (lack of) focus has always been roughly the same: technical and arty stuff that interests me, research notes too small or preliminary to publish as a proper paper, open problems, announcements of new publications, conference reports, personal updates, and academic and technical politics. I started cross-posting to Google+ in 2011, stopped again soon after that over a new policy forbidding pseudonymous users, and returned in 2014 after this policy was rescinded. At that point I moved the brief links to Google+, shifting to a format where the blog itself contained only the longer posts and roundups of the links. LiveJournal was sold to a Russian company in 2007, and for many years after that it operated much as it had before, but gradually became more annoying about showing ads even to readers of my (paid and supposedly ad-free) account. In 2017 they imposed new terms of service with Russian legal restrictions (in particular, against LBGTQ+ advocacy) that I found unacceptable and refused to sign. Instead, I deleted my account and moved to GitHub Pages, including my old posts, almost all of which I had backed up before that became impossible. Under GitHub, everything is in a git repository that I keep local copies of, so it should be much easier to move again should I need to. The old posts were in html format and the posts after the move are in markdown format but fortunately it all works with the mix of formats. Later I slowly went through the old posts cleaning up some dubious markup, migrating image files to GitHub, and using vector graphic files when I still had them; that process is still not entirely complete. Using GitHub meant static content and no discussion threads, and I was already using Google+ for the shorter link posts, so I started using it to host discussion links for my posts as well. By the time Google cancelled Google+ in 2019, my posts included many links to Google+, most of which I was able to replace with copies on archive.org. Needing a new host for short posts and discussion links, I chose Mastodon and mathstodon.xyz. For once, my habit of choosing a technically better solution over a more popular solution paid off: I have never used Twitter, so I haven’t had to move again after recent events. And here I am now. Anyway, I thought at this anniversary it would be appropriate to make a roundup of twenty of my old posts that I found particularly memorable and maybe worth revisiting. Here they are, in chronological order: * Updated Python library: Repetitivity, Sudoku, July 20, 2005. My first post. It’s more telegraphic than I would write now, but I think otherwise it stands up well. It describes an open-source command-line Sudoku solver that I wrote, aimed at mimicking human deduction rather than doing what would be much easier for a computer, backtracking search, and an efficient algorithm for one of its deduction rules, based on finding the edges of a bipartite graph that cannot take part in a perfect matching. * Periodic coloring of tilings, September 11, 2006. For any periodic tiling of the plane (or, if you prefer, a periodic planar graph), you can 4-color the tiles or the vertices, by a combination of the 4-color theorem for finite graphs and the De Bruijn–Erdős theorem on coloring infinite graphs. But the coloring might not itself be periodic. If you ask for a periodic coloring with the same period as the original tiling, then it’s the same as coloring a graph on the torus and you might need six colors. But I still don’t know how many colors you need if you require periodicity but allow a bigger fundamental region. * The range-restricted Hamming problem, March 18, 2007. How to quickly solve a problem from ancient Mesopotamia: listing all \$\\{2,3,5\\}\$-smooth numbers in the range \$60^k,60^{k+1}]\$. With a diagram of these numbers closely related to the [Tonnetz of music theory. * Was sind und was sollen die Pseudogeraden?, August 3, 2007. Pretentious title aside, this is on choosing among multiple incompatible definitions for pseudolines, with more in a follow-up post. I think it continues to be relevant: as of this posting the Wikipedia pseudoline article still fails to adequately define a single pseudoline: it uses a definition that has the intended meaning only for arrangements of more than one pseudoline. * The many faces of the Nauru graph, December 12, 2007. This roundup of different drawing styles for the 24-vertex cubic symmetric graph gave it a name which has since caught on: Google Scholar now lists 80 publications containing the “Nauru graph” phrase. Follow-ups: a 3d ray-trace of its genus-four symmetric embedding and another drawing with lots of unnecessary crossings. * Parts assembly and the burr puzzle antimatroid, December 2, 2008. In how many orders can you take apart a six-piece burr puzzle? This is not the first post I made about antimatroids, but I think it is the first to make a point I have repeated multiple times since then. Despite the scary name, antimatroids formalize a simple and intuitive concept, that you are doing some things one at a time and that once a thing becomes available for you to do it stays available until you do it. In this case, the things you are doing are removing pieces from the puzzle. Later posts applied the same idea to rhyme schemes, course prerequisites, deductions in logic puzzles, quadtree mesh generation, and introductory computer programming. * Flat equilateral tori?, February 3, 2009. An easy-to-state unsolved problem: can you make a torus out of equilateral triangles meeting six to a vertex? Usually I draw vector graphics illustrations for my geometry posts but for this one I used photographs of snap-together plastic triangles. * Visualizing BFS as a spiral, May 16, 2009. When applied to the Calkin–Wilf tree this produces a sequence containing all positive rational numbers exactly once, with a simple formula for determining each successive number from the previous one that behaves the same everywhere in the spiral, regardless of jumps in level in the breadth-first search tree. * A mathematical model of conference acceptance rates, July 18, 2011. If program committees base their decisions on some combination of strength, fashion, and random factors, but the outcome you want is to accept all of the strongest papers, then you’re probably going to need higher acceptance rates and more acceptances of weaker papers than you might expect. But the “mathematical model” here is very unsophisticated and can probably be made much more realistic. * Stack-based graph traversal ≠ depth first search, December 17, 2013. A surprisingly common mistake in algorithm texts. It is possible to start with a form of BFS, replace the queue by a stack, and get DFS, but you have to be careful or you’ll get something else instead. See also xkcd on depth and breadth. * MathML considered harmful, August 4, 2015. Or, how the pursuit of an unrealistic ideal has harmed and continues to harm the legibility and editability of mathematical formulas on Wikipedia. * The shape of the Kresge Auditorium, April 30, 2016. A study of the geometry of MIT’s Kresge Auditorium, a curved triangle formed by projecting onto the plane an eighth of a sphere, comparing it with the Reuleaux triangle, a similar-looking but different curved triangle. This was the first of what became a series of posts on curved triangles that other people had called Reuleaux triangles, but that were not actually Reuleaux triangles. The latest full-length post in the series, on the shapes of triangular pencils, has links to the rest; I also made brief posts on the subject here and here. * Half a dimension short, October 21, 2017. Or, why 3d views of some bridges in Google Maps look so strange. * #MeToo in theoretical computer science, February 14, 2018. Guest post; trigger warning: rape. I recently joined the board of the Computational Geometry Society, one of whose main roles is to provide a legal framework to keep proven predators away from our conferences. This was one of multiple incidents (the others less public) convincing me that this role is still necessary and important. * One thousand women of STEM!, September 22, 2019. Since I started in 2005, I’ve spent a lot of time editing Wikipedia. Since 2008, one of the things I have been doing there has been creating biographies of women in STEM. By my rough estimate there were 1000 by this date and by my even rougher estimate it’s likely to be over 3000 by now. If I had to choose who I most want others to know about, it would be the first one listed in this post: Pandrosion of Alexandria, the first female mathematician that we know by name. * Gilbert tessellations from a cellular automaton, November 2, 2021. Long ago Stephen Wolfram described a four-way subdivision of the typical behaviors of cellular automata on random initial fields: they can die out, quickly form small stable or periodic structures, stay chaotic, or exhibit complex behaviors. This post points to an intermediate possibility: they can build walls that extend across space until they are blocked by other walls. Similar wall-building behavior was studied by Gilbert in the 1950s as a model of crack formation, and has appeared in some of my computational geometry papers under the heading of “motorcycle graphs”, named for the Tron light-cycle wall-building game. * Midsphere facts and fallacies, July 27, 2022. A midsphere is a sphere tangent to all edges of a polyhedron. All polyhedra have a combinatorially equivalent form with a midsphere. But contrary to what multiple sources state, the midsphere does not always touch the midpoints of the edges. It is not true that only the Platonic solids have all three of an insphere, midsphere, and circumsphere. When a polyhedron has all three, they might not be concentric nor even nested. The midsphere might not be the smallest sphere touching all the edges. I don’t know whether (when both exist) the inradius is always smaller than the midradius, or whether the midradius is always smaller than the circumradius. * Coloring the plane for generic norms, May 13, 2023. Many of my posts attempt to provide a more-accessible explanation of research from my own papers. This one is similar, but for a paper that is not mine, by Noga Alon, Matija Bucić and Lisa Sauermann on the problem of coloring the unit distance graph of the plane. For Euclidean distances the number of colors you need is 5, 6, or 7, but it remains a big open problem which one. Alon et al prove that for generic convex distance functions, the number of colors is exactly four, but finding a natural strictly-convex distance function for which this is true is another open problem. * Random perfection, May 8, 2024. Another Wikipedia editor asked me: how likely is it that a random graph is a perfect graph? It depends on the density of the graph, with two phase transitions between densities for which it is very likely and densities for which it is very unlikely, less sharp than the phase transitions for many other properties. My longest recent post, and maybe one of my most technical. * The ancient Greek mathematics of distorted airplane propeller photos, March 22, 2025. One of the things I particularly enjoy about Wikipedia editing, when it happens, is discovering unexpected connections between things I didn’t know were related. This one is on a connection between the distortions caused by rolling shutters and ancient Greek work on trisecting angles and squaring the circle. (Discuss on Mastodon) By David Eppstein

20.07.2025 00:01 — 👍 0 🔁 0 💬 0 📌 0

What is Intelligence? Architecture, Divergence, and Fiction _A computational anatomy of intelligence. How faculties interact, architectures diverge, and coherence emerges through self-constructed fictions_ > _“There is no single path into the forest.”_ — Yoruba proverb ### **Yo-Yo Ma and the Single Note** It was the winter of 2018 and the NeurIPS conference—one of the world’s premier gatherings on artificial intelligence—had descended on a snow-laced Montreal. Thousands of researchers, engineers, and students crisscrossed the vast convention center, sharing ideas about optimization tricks, new models, and the future of AI. Posters lined the walls of rooms steeped in the aroma of coffee, while outside, the city lay wrapped in cold, crisp silence. At one of the marquee panels, a senior executive from a major tech company presented their latest AI music generator—an advanced system trained on thousands of classical works, capable of composing coherent classical music in real time. The melodies were elegant and the timing _precise_. Then Yo-Yo Ma was invited to respond. He didn’t speak. He turned his chair, lifted his cello, and played a single note. Then he played it again. And again. Each time, the same note emerged differently _—tentative, bold, grieving, serene._ Each time, his breath shifted and his eyes drifted into a different world. The AI had captured form. _But Yo-Yo Ma, infusing his music with intention and feeling, captured the room._ That moment didn’t just expose AI’s limitations. It revealed a deeper truth: **Intelligence isn’t precision—it’s relation.** It does not reside in outputs alone, but in how systems tune themselves to the world: shaped by context, memory, attention, and intent. It is a dynamic interplay between perception and action, between internal models and external pressures. It arises wherever systems _engage their constraints creatively_ : whether through mycelial networks, migrating birds, musical phrases, or planetary motion. In the previous essay, we traced how intelligence emerges in nature: not as a fixed trait, but as a layered process—optimization in physics, adaptation in evolution, collective sensing in life before neurons. This second essay turns inward—from emergence to architecture. If the first asked _where_ intelligence comes from, this one asks: _what is it made of?_ We begin by identifying a set of core faculties: s**ensing, responding, memory, learning, attention, valuation, modeling, and reflection**. These faculties take many forms. **Sensing** may be chemical, tactile, social, or symbolic. **Memory** may be episodic, spatial, or associative. **Valuation** may be shaped by prediction error, pain, or narrative. And how they are configured—what is emphasized, suppressed, amplified, or ignored—depends not just on design, but on history: _evolutionary, developmental, experiential._ From these components and their interrelations, intelligence emerges—not as a single thread, but as a **weave** : recursive, plural, and at times, fictional. **This part of the essay unfolds in three movements:** * **Composition** : How core faculties combine to produce reasoning, language, and creativity—not through accumulation, but through tension, feedback, and reprogramming. * **Divergence** : Why there is no single blueprint for intelligence. We examine human cognitive diversity to understand the space of architectural variation. * **Fiction** : How intelligent systems—especially human ones—construct internal narratives to manage complexity, maintain coherence, and navigate meaning. This is not a final theory. It is a trace—a _computational lens_ on intelligence as it curves inward, reshapes itself, and constructs meaning under pressure. For those exploring AI not as an isolated artifact, but as part of a broader landscape of intelligence, this lens may offer new ways to rethink design and augmentation. And like a forest, this inquiry offers no fixed path—only branching terrain shaped by tension, memory, and choice. **Read the full essay by subscribing (for free) to _The Intelligence Loop_.** By nisheethvishnoi

19.07.2025 11:31 — 👍 0 🔁 0 💬 0 📌 0

Postdoctoral fellow position at University of Houston (apply by September 30, 2025) A postdoc is available in distributed and scalable machine learning, security, and fault tolerance in distributed computing at the CS department, Univ. of Houston. Prior publications in top conferences such as NeurIPS, ICML, SODA, FOCS, STOC, and PODC are desired. Candidates should send their CV, a research statement, and (request referees to forward) 3 letters to Prof. Gopal Pandurangan. Website: https://www2.cs.uh.edu/~gopal Email: gopalpandurangan@gmail.com By shacharlovett

18.07.2025 21:10 — 👍 0 🔁 0 💬 0 📌 0

TR25-099 | The Algebraic Cost of a Boolean Sum | Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression. We study the question of why the VNP-completeness proof of the permanent fails for the determinant. We isolate three fundamental properties that are sufficient to prove a polynomial sequence is VNP-hard, of which two are shared by both the permanent and the determinant. We proceed to show that the permanent satisfies the third property, which we refer to as the ``cost of a boolean sum," while the determinant does not, showcasing the fundamental difference between the polynomial families. We further note that this differentiation also applies in the border complexity setting and that our results apply for counting complexity.

18.07.2025 16:40 — 👍 0 🔁 0 💬 0 📌 0

2-round BFT in Simplex style Simplex is a recent partially synchronous Byzantine Fault Tolerant (BFT) protocol that is gaining popularity. We take this opportunity to rehash several classic results in the Simplex style. The first post explained the key difference between Simplex and Tendermint. This second post is on 2-round BFT. The next post will...

18.07.2025 04:00 — 👍 0 🔁 0 💬 0 📌 0

Ranking Vectors Clustering: Theory and Applications **Authors:** Ali Fattahi, Ali Eshragh, Babak Aslani, Meysam Rabiee We study the problem of clustering ranking vectors, where each vector represents preferences as an ordered list of distinct integers. Specifically, we focus on the k-centroids ranking vectors clustering problem (KRC), which aims to partition a set of ranking vectors into k clusters and identify the centroid of each cluster. Unlike classical k-means clustering (KMC), KRC constrains both the observations and centroids to be ranking vectors. We establish the NP-hardness of KRC and characterize its feasible set. For the single-cluster case, we derive a closed-form analytical solution for the optimal centroid, which can be computed in linear time. To address the computational challenges of KRC, we develop an efficient approximation algorithm, KRCA, which iteratively refines initial solutions from KMC, referred to as the baseline solution. Additionally, we introduce a branch-and-bound (BnB) algorithm for efficient cluster reconstruction within KRCA, leveraging a decision tree framework to reduce computational time while incorporating a controlling parameter to balance solution quality and efficiency. We establish theoretical error bounds for KRCA and BnB. Through extensive numerical experiments on synthetic and real-world datasets, we demonstrate that KRCA consistently outperforms baseline solutions, delivering significant improvements in solution quality with fast computational times. This work highlights the practical significance of KRC for personalization and large-scale decision making, offering methodological advancements and insights that can be built upon in future studies.

18.07.2025 00:00 — 👍 0 🔁 0 💬 0 📌 0

The unpredictability conundrum Scrolling through the deluge of people advertising their ICML papers on social media, I found myself bedeviled by a philosophical question about the logical reconstruction of machine learning. In the most famous machine learning papers, the central claims take the form: Y is predictable from X, and method M demonstrates a particular accuracy on this prediction problem. The AlexNet paper showed that ImageNet image classes were predictable from images, and a convolutional neural network achieved high accuracy. The GPT3 paper achieved high accuracy on a variety of natural language processing prediction problems with one-shot learning and transformer-based large language models. The Support Vector Network paper showed that support vector machines could recognize handwritten digits with high accuracy. In these descriptions, I am being vague today about what precisely “X” and “Y” are. “X” could be streams of text, images, or electronic health records. “Y” could be translations, image classes, or cancer diagnoses. How papers build up these constructs and concepts also bugs me, but I will leave a full logical reconstruction of machine learning for another blog post.1 Today, I am interested in understanding the papers that argue the negative claim and whether they ever provide useful evidence. That is, the papers that assert: Y is not predictable from X. I call claims of this form “unpredictability arguments.” Papers making unpredictability arguments can get a lot of temporary traction in machine learning discourse. They give fuel to the petty battles inside the community. In our current landscape, they give ammunition for lay critiques of industry. They can even help bring on AI Winters if people take them seriously enough. The problem is they are much harder to justify as stated. Unpredictability arguments can be purely theoretical. These might say something like “under this list of assumptions about how data is generated and this list of assumptions about how you build the prediction function, Y is not predictable from X.” Such arguments can be helpful for conceptualization, but they are too strongly tied to their assumptions. Yes, simple linear perceptrons can’t build an XOR of input bits. But simple multilayer perceptrons can. Moreover, if your prediction function is allowed to include simple numerical transformations of the input data, all of a sudden XOR is predictable by linear functions (that is, just add XOR as a feature.). Theory bounds are weak because practitioners (and theorists for that matter) can simply change the rules. Yes, you can tell me that under some very contrived scenario, I can’t build a particular computer program. But machine learning practice is the apotheosis of computer science, fully embracing a Feyerabendian zeal for _anything goes._ I can always disagree with your assessment of how data is collected, generated, and processed. And there are an infinite number of computer programs I can write in PyTorch to disprove your unpredictability assertion. Minsky and Papert’s arguments that I’m alluding to above—about whether perceptrons can compute parity—are a notable exception that proves the rule. No one really understands their arguments, and if you believed them without really digging into the details or trying some simple alternative prediction programs, you would have abandoned supervised learning for decades (oh wait, that’s actually what happened). Now, what about experimental bounds? If someone writes a paper saying, “I did procedure P and found transformers were really bad at predicting Y from X,” what does this tell us? I’ve seen a lot of papers make such claims concerning LLMs and transformers. You’ll have people saying, “See, LLMs are stochastic parrots,” or “See, LLMs just learn epicycles.” In these papers, the predictability of the Y value is supposed to be obvious to the reader, and we’re supposed to be shocked that some machine learning model can’t predict it. Sure, people can say all they want. As someone who wants better critiques of predictions, I’m never convinced by these papers, no matter how frequently they capture a viral zeitgeist. In the spirit of a Lakatosian offense, I can always counter by tweeting “your procedure is pretty arbitrary, my friend,” or “i don’t think that baseline is fair,” or “skill issue.” There is no reason to believe that the code shared in such papers is the only way for a method to predict Y from X. There is an infinite regress of hyperparameters, optimization variants, and so on. You only have so many forking paths you can explore in the garden before the conference deadline. Most people would find competitions to be more compelling evidence. Machine learning is built upon competitive testing, leading to breakthroughs in proving Y predictable from X. Everyone loves the ImageNet competition. Benchmark scores are a central part of how companies showcase their latest language models. Can competitive testing “prove” Y is unpredictable? What do we conclude when machine learning competitions fail? A notable example of failure is the Future of Families Challenge (formerly known as the Fragile Families Challenge). The goal here was to predict certain socioeconomic outcomes from complex, unstructured data recorded about a large birth cohort. After hundreds of researchers tried to predict the outcomes, the study concluded that the best predictions were not very accurate and were only slightly better than those from a simple benchmark model.” What should we conclude from this competition? We could conclude that the Ys in this paper (including “material hardship,” GPA, “grit,” and eviction) are not predictable from the Xs. I could also conclude that poor predictability arises because the data is far worse than advertised (e.g., there is _a lot_ of missing data in the dataset). I could conclude that the targets studied have poor construct validity. There’s a long line of objections that I can string together even when a competitive test fails to find predictability. In any event, I don’t have good answers for how to think about this aspect of the philosophy of machine learning yet. I’m very much thinking out loud today! But I’m posting because I’d love to hear your thoughts on what would constitute compelling evidence to prove the impossibility of prediction. Subscribe now 1 Really, it should be a paper. Let me know if you are soliciting invitations for special issues on the philosophy of engineering. By Ben Recht

17.07.2025 14:32 — 👍 0 🔁 0 💬 0 📌 0

TR25-098 | IPS Lower Bounds for Formulas and Sum of1 ROABPs | Utsab Ghosal, Prerona Chatterjee, Partha Mukhopadhyay, Amit Sinhababu We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is a central topic in algebraic proof complexity developed in the context of Nullstellensatz refutation (Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994) and simulates Extended Frege efficiently. Our main results are as follows. 1. mult-IPS_{Lin'}: We prove nearly quadratic-size formula lower bound for multilinear refutation (over the Boolean hypercube) of a variant of the subset-sum axiom polynomial. Extending this, we obtain a nearly matching qualitative statement for a constant degree target polynomial. 2. IPS_{Lin'}: Over the fields of characteristic zero, we prove exponential-size sum-of-ROABPs lower bound for the refutation of a variant of the subset-sum axiom polynomial. The result also extends over the fields of positive characteristics when the target polynomial is suitably modified. The modification is inspired by the recent results (Hakoniemi, Limaye, Tzameret, STOC 2024 and Behera, Limaye, Ramanathan, Srinivasan, ICALP 2025). The mult-IPS_{Lin'} lower bound result is obtained by combining the quadratic-size formula lower bound technique of Kalorkoti (SICOMP 1985) with some additional ideas. The proof technique of IPS_{Lin'} lower bound result is inspired by the recent lower bound result of Chatterjee, Kush, Saraf and Shpilka (CCC 2024).

17.07.2025 04:19 — 👍 0 🔁 0 💬 0 📌 0

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication **Authors:** Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan We show that for a randomly sampled unsatisfiable $O(\log n)$-CNF over $n$ variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in $n$.

17.07.2025 00:00 — 👍 0 🔁 0 💬 0 📌 0

TR25-097 | On the Limits of Computationally Sound IPPs in the Isolated Model | Hadar Strauss Interactive proofs of proximity (IPPs) are a relaxation of interactive proofs, analogous to property testing, in which soundness is required to hold only for inputs that are far from the property being verified. In such proof systems, the verifier has oracle access to the input, and it engages in two types of activities before making its decision: querying the input oracle and communicating with the prover. The main objective is to achieve protocols where both the query and communication complexities are extremely low. Of particular interest are IPPs in which the querying and the interacting activities are performed independently, with no information flow from one activity to the other. Such IPPs were systematically studied by Goldreich, Rothblum, and Skverer (ITCS 2023), who introduced two variants: the pre-coordinated model, where the querying and interacting activities may use a common source of randomness, and the isolated model, where the two activities are fully independent, each operating with a separate source of randomness. We focus on what is possible under these models when soundness is relaxed to computational soundness. Our previous work (ECCC, TR24-131) showed that the pre-coordinated model becomes significantly more powerful under this relaxation. In this work, we consider the isolated model under the same relaxation and show a separation between the two models. We consider a property that, by our previous work, has a computationally sound IPP in the pre-coordinated model with poly-logarithmic complexities (assuming the existence of collision-resistant hashing functions), and show that any computationally sound IPP in the isolated model for this property must have either query complexity or communication complexity that is $n^{\Omega(1)}$, where $n$ is the length of the input.

16.07.2025 20:26 — 👍 0 🔁 0 💬 0 📌 0

Turing, Wagner, Ruth Douglas Hofstadter first published Gödel, Escher, Bach: an Eternal Golden Braid in 1979 and my then high school self tried, and failed, to read though the entire book. It focused on the contradictions, with Kurt Gödel's incompleteness theorems, M. C. Escher's Drawing Hands and Johann Sebastian Bach's Canon a 2 per tonos, a piece that keeps rising until it ends a whole tone higher than it started. I'd prefer to focus less on the paradoxes and self-reference to the true beauty and complexity of computation. So now having had a long career in the field, who would I call on to capture the power and beauty of computing? It has to start with Alan Turing. His seminal paper On Computable Numbers, with an Application to the Entscheidungsproblem gives a clean model for computation and still the best argument (Section 9) for why this simple model captures everything computable. The Entscheidungsproblem, that you can't mechanize all of mathematics, comes as a consequence, not as a goal of the paper. In a much later paper, The Chemical Basis of Morphogenesis, he shows how the beauty of nature can emerge naturally from computation, which of course we now know much better arises from discrete DNA sequences. For music, instead of Bach's abstract works, I prefer to focus on the emotional power of music that still arises from a musical score that is not unlike a computer program in the way it lays out the composition. Take for example Richard Wagner's Prelude and Liebestod (the beginning and the end of his opera Tristan and Isolde). It captures the tension of the two lovers from the very first notes and keeps that tension going until it resolves at the very end. While soccer and basketball have mostly continuous play, I prefer that great American game of baseball that after each pitch has a very discrete state space that stadiums would capture with a few light bulbs (strikes, balls, outs), and yet could keep the excitement and tension on every one of those pitches. No one dominated the game more in his time than George Herman "Babe" Ruth, who I might have admittedly also chose to keep the same syllable cadence as Hofstadter. So let's thank Turing, Wagner, Ruth, and the many others that showed we can show how incredible complexity and beauty can arise in the simplicity of computation. So many stories to tell. By Lance Fortnow

16.07.2025 18:42 — 👍 0 🔁 0 💬 0 📌 0

TR25-096 | Searching for Falsified Clause in Random $(\log{n})$-CNFs is Hard for Randomized Communication | Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan We show that for a randomly sampled unsatisfiable $O(\log n)$-CNF over $n$ variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in $n$.

16.07.2025 12:14 — 👍 0 🔁 0 💬 0 📌 0

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games **Authors:** Vincent Cheval, Florian Horn, Soumyajit Paul, Mahsa Shirmohammadi A major open question in algorithmic game theory is whether normal-form correlated equilibria (NFCE) can be computed efficiently in succinct games such as extensive-form games [DFF+25,6PR24,FP23,HvS08,VSF08,PR08]. Motivated by this question, we study the associated Threshold problem: deciding whether there exists a correlated equilibrium whose value exceeds a given threshold. We prove that this problem is PSPACE-hard for NFCE in multiplayer extensive-form games with perfect recall, even for fixed thresholds. To contextualize this result, we also establish the complexity of the Threshold problem for Nash equilibria in this setting, showing it is ER-complete. These results uncover a surprising complexity reversal: while optimal correlated equilibria are computationally simpler than optimal Nash in normal-form games, the opposite holds in extensive-form games, where computing optimal correlated equilibria is provably harder. Building on this line of inquiry, we also address a related question by [VSF08], who introduced the notions of extensive-form correlated equilibrium (EFCE) and agent-form correlated equilibrium (AFCE). They asked how difficult the Threshold problem is for AFCE; we answer this question by proving that it is NP-hard, even in two-player games without chance nodes. Complementing our hardness results, we establish tight complexity classifications for the Threshold problem across several correlated equilibrium concepts - including EFCE, AFCE, normal-form coarse, extensive-form coarse, and agent-form coarse correlated equilibria. For each of these solution concepts in multiplayer stochastic extensive-form games with perfect recall, we prove NP-completeness by providing matching NP upper bounds to the previously known hardness results. Together, our results provide the most complete landscape to date for the complexity of optimal equilibrium computation in extensive-form games.

16.07.2025 00:00 — 👍 0 🔁 0 💬 0 📌 0

TR25-095 | Godel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness | Rahul Ilango A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. '94] shows that zero-knowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs --- namely perfect soundness (that no proof of a false statement exists) and non-interactivity (that a proof can be transmitted in a single message). Contrary to this impossibility, we show that zero-knowledge with perfect soundness and no interaction is effectively possible. We do so by defining and constructing a powerful new relaxation of zero-knowledge. Intuitively, while the classical zero-knowledge definition requires that an object called a simulator actually exists, our new definition only requires that one cannot rule out that a simulator exists (in a particular logical sense). Using this, we show that **every falsifiable security property of (classical) zero-knowledge can be achieved with no interaction, no setup, and perfect soundness.** This enables us to remove interaction and setup from (classical) zero-knowledge in essentially all of its applications in the literature, at the relatively mild cost that such applications now have security that is "game-based" instead of "simulation-based." Our construction builds on the work of Kuykendall and Zhandry [TCC '20] and relies on two central, longstanding, and well-studied assumptions that we show are also necessary. The first is the existence of non-interactive witness indistinguishable proofs, which follows from standard assumptions in cryptography. The second is Krajícek and Pudlak's 1989 conjecture that no optimal proof system exists. This is one of the main conjectures in the field of proof complexity and is the natural finitistic analogue of the impossibility of Hilbert's second problem (and, hence, also Gödel's incompleteness theorem). Our high-level idea is to use these assumptions to construct a prover and verifier where no simulator exists, but the non-existence of a simulator is independent (in the logical sense of unprovability) of an arbitrarily strong logical system. One such logical system is the standard axioms of mathematics: ZFC.

15.07.2025 18:51 — 👍 0 🔁 0 💬 0 📌 0

Joram’s seminar 2025: Hypercontractivity, Groups and Representations ### Joram’s seminar 2025 Here is my summary of the recent Joram’s seminar that took place on July 9 and 10 in Jerusalem. Much of the seminar was about the the paper Product Mixing in Compact Lie Groups by David Ellis, Guy Kindler, Noam Lifshitz, and Dor Minzer. ## Lecture I: Noam Lifshitz Noam Lifshitz (HUJI): Product mixing in groups (Special Colloquium) **Abstract:** Let be subsets of the special unitary group of Haar measure . Then . In fact, the product of random elements is equidistributed in This makes progress on a question that was posed independently by Gowers studying nonabelian variants of questions from additive combinatorics and settles a conjecture of physicists studying quantum communication complexity. To prove our results we introduce a tool known as ‘hypercontractivity’ to the study of high rank compact Lie groups. We then show that it synergies with their representation theory to obtain our result. My summary ### The Babai–Sós Problem In 1985, László Babai and Vera Sós posed the following question: _What is the largest possible size of a product-free subset of a finite group?_ For abelian groups, one can always find a sum-free set of positive density. However, the situation in the non-commutative case is quite different—and turns out to be very interesting. ### Gowers’ Work and the Sarnak–Xue–Gowers Lemma In his 2008 paper quasirandom groups, Tim Gowers proved that if the dimension of the smallest non-trivial representation of a finite group is , then any product-free subset has density at most for some constant . Gowers also obtained an analogous result for compact Lie groups, showing that the Haar measure of a product-free set is similarly bounded. For example, for the group , any product-free set has measure at most . Gowers’ argument relies (among other things) on ideas reminiscent of a 1991 result by Sarnak and Xue, which established a beautiful connection between spectral gaps and the dimensions of irreducible representations. ### “Gowers’s enemies are low dimensional representation” Improving on Gowers’ bound requires a more refined analysis of characteristic functions of sets, made possible by hypercontractive estimates. Hypercontractivity enables one to strengthen the upper bound for product-free sets from to . Further improvements might still be achievable—an intriguing open direction. However, for the stronger statement concerning the equidistribution of products, this new bound is sharp. ### One Clean Qubit Suffices Noam also described a related problem in quantum communication complexity, which was resolved using similar methods. This result appears in the paper _One Clean Qubit Suffices for Quantum Communication Advantage_ by Srinivasan Arunachalam, Uma Girish, and Noam Lifshitz. ### Hypercontractivity Noam concluded his talk by highlighting hypercontractivity—the key new ingredient in this line of work—and the associated -level inequalities. The proof of the main theorem, to be developed over four additional lectures, combines representation theory for with the establishment and use of hypercontractive estimates. ## Lecture II: Dor Minzer Dor Minzer (MIT): On CSPs, Inverse Theorems and Friends **Abstract:** Constraint satisfaction problems (CSPs in short) are among the most important computational problems studied in Theoretical Computer Science. In this talk we will discuss a recent line of study addressing the complexity of approximating satisfiable instances of CSPs. We will focus on connections to analytic inverse-type theorems for correlations that generalize the -Gowers norm, and show how these results can be used in other areas, such as property testing and extremal combinatorics. Based mostly on joint works with Amey Bhangale, Subhash Khot and Yang P. Liu. My summary: ### CSPs and the difference between 3LIN and 3SAT It is NP-hard to find a satisfying assignment for a 3-SAT instance—and even to satisfy a large fraction of clauses when a perfect assignment exists. The case of 3-LIN (systems of linear equations mod 2 with three variables per equation) is very different: here it is easy to find a satisfying assignment, but hard to find an assignment that satisfies _many_ equations. Both problems fall under the general framework of **constraint satisfaction problems (CSPs)**. Understanding the source of this difference is a deep and challenging question in computational complexity. Amey Bhangale, Subhash Khot, and Dor Minzer (recently joined by Yang P. Liu) have written a remarkable series of (so far) seven papers developing a theory to address this question; Here is a link to On Approximability of Satisfiable k-CSPs:VII. As it turns out, combinatorial objects like **combinatorial lines** are special cases of a much broader family of structures arising from CSPs. This connection works both ways: * The general theory applies to long-standing problems in additive combinatorics. * At the same time, advances in additive combinatorics—via more sophisticated mathematical tools—feed back into the general CSP theory. ### Better Bounds for Density Hales–Jewett Dor highlighted a striking application of this theory (we already mentioned it in this post): Reasonable Bounds for Combinatorial Lines of Length Three, by Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer The paper proves that any subset with contains a combinatorial line of length 3. This dramatically improves on the previous best bound of of D.H.J. Polymath, Ann. of Math. 2012] (DHJ[3] was the goal of the first [polymath project.) Dor also mentioned general algebraic norms in this theory, reminiscent of Gowers norms, as well as inverse theorems for these new norms. ## Lecture III: Nathan Keller Nathan Keller (BIU): Intersection theorems and improved covering results for the symmetric group, via hypercontractivity In this talk we describe two seemingly unrelated results on the symmetric group . A family of permutations is called _t_ -intersecting if any two permutations in _F_ agree on at least _t_ values. In 1977, Deza and Frankl conjectured that for all , the maximal size of a _t_ -intersecting subfamily of S_n is (n-t)!. Ellis, Friedgut and Pilpel (JAMS, 2011) proved the conjecture for all _n >exp(exp(t))_ and conjectured that it holds for all _n >2t_. We prove that the conjecture holds for all _n >ct_ for some constant _c_. A well-known problem asks for characterizing subsets _A_ of whose square contains (=”covers”) the alternating group . We show that if _A_ is a union of conjugacy classes of density at least then covers This extends a seminal result of Larsen and Shalev (Inventiones Math., 2008) who obtained the same with 1/4 in the double exponent. The two results boil down to the understanding of independent sets in certain Cayley graphs, and turn out to be related. We shall focus on the main new tool we use in the proof of both results – hypercontractive inequalities for global functions, developed by Keevash, Lifshitz, Long and Minzer (JAMS, 2024). The talk was based on joint works with Noam Lifshitz, Dor Minzer, and Ohad Sheinfeld. Nathan’s talk is based on these two papers: Improved covering results for conjugacy classes of symmetric groups via hypercontractivity, by Nathan Keller, Noam Lifshitz, and Ohad Sheinfeld On t-intersecting families of permutations by Nathan Keller, Noam Lifshitz, and Ohad Sheinfeld Nathan explained how Erdős–Ko–Rado-type problems about permutations in combinatorics and problems about products of conjugacy classes in group theory can both be formulated in terms of combinatorial properties of Cayley graphs of normal subsets (unions of conjugacy classes) in groups. (This explanation was quite stunning for me.) He then outlined how **hypercontractive inequalities for global functions** — (that we mentioned here and here) yield major advances in both of these areas. We discussed Ellis, Friedgut and Pilpel’s Erdős–Ko–Rado result for permutations in this 2009 post. ## ## Lectures IV,V,VI,VII: Guy Kindler and Noam Lifshitz Hypercontractivity and product mixing in compact Lie groups (Four lectures) Guy Kindler (HUJI) and Noam Lifshitz (HUJI) **Abstract:** The study of geometric properties of Cayley graphs associated with non-abelian groups is a rich area of research with wide ranging applications. Here, key questions concern properties such as expansion, mixing, diameter, etc. While remarkable progress was made in this area by applying deep results in character theory, such methods seem to be limited to the case of normal Cayley graphs (those generated by unions of conjugacy classes). In this mini-course we explore a recent approach which seems to sidestep such limitations. Inspired by techniques originally introduced in the study of the (abelian) Boolean Cube, we use a synergy between hypercontractive inequalities and dimensional lower bounds from representation theory to make progress on various problems. In particular, we will present a significant improvement of a bound of Gowers on the measure of product-free subsets in the unitary group SU(n). My comments: I will not give a detailed summary of the lectures by Guy and Noam. They described a subtle coupling method to prove hypercontractivity for and mentioned another method based on curvature. They got quite deeply into the representation theory of SU(n) and mentioned notions of “degree” (analogous to “Juntas” for Boolean functions) that plays a role. Related notions appeared in works of Shamgar Gurevich and Roger Howe (e.g. this paper) and of Bob Guralnik, Michael Larsen, and Pham Huu Tiep (e.g., this paper). The proof presented by Noam for bounding the eigenvalues was actually a simplification discovered right before the lecture! ## More ### On Joram Elon Lindenstrauss shared a few moving words about his father, emphasizing Joram’s deep commitment to the Israeli mathematical community. The format of Joram’s seminar—aiming not only to present high-level ideas but also to dive into the gory details of major mathematical advances—was something he greatly valued. I vividly recall a seminar Joram organized back in 1981 on the newly published book by Gromov, _Structures métriques pour les variétés riemanniennes_. (See also this post about Joram Lindenstrauss. Here is a link to previous seminars in the series.) ### David Ellis The fourth author of the paper, our dear friend David Ellis, visited Jerusalem in May. ### Videoes Videoes for the lectures are Lecture 1, lecture 2, lecture 3, lecture 4, lecture 5, lecture 6, lecture 7. (The links may not be stable). ### Kazhdan’s seminar on hypercontractivity – Spring 2026 Back in 2003–2004, David Kazhdan and I ran a seminar on **polytopes, toric varieties** , and related topics in combinatorics and algebra. (Much has happened since then—Karim Adiprasito even organized another Kazhdan seminar on a related theme in 2018.) In 2012, David and I thought it might be time to run a similar event in 2014 and perhaps start a tradition of a decennial joint seminar. This plan materialized only in 2019 when Leonid Polterovich, Dorit Aharonov, Guy Kindler, Michael Ben-Or, and I dedicated one of David’s Sunday seminars to **computation, quantumness, symplectic geometry, and information**. Now, we’re planning a **Kazhdan seminar on hypercontractivity** for **Spring 2026**. Since many of Kazhdan’s seminars focus on representation theory, the new connections between hypercontractivity and representations make this an especially natural fit. ### Plans for my blog I have plenty of material I’d love to share—from the Combinatorial Colloquium in London, the events of the Czech Learned Society in Prague, and several lectures and meetings in Israel. This summary of the very recent Joram seminar does _not_ mean I’ve abandoned plans to write about earlier events. Stay tuned! ### High-degree representations and physics. It is an interesting (meta) question why representations that occur in particle physics are (very) low dimensional. Is the Sarnak-Xue lemma related to this phenomenon? By Gil Kalai

15.07.2025 15:34 — 👍 0 🔁 0 💬 0 📌 0

Linkage * Dozens of the world’s most cited scientists stop falsely claiming to work in Saudi Arabia (\$\mathbb{M}\$). Perhaps relatedly, Clarivate has tightened its checks for fraudulent citation practices and removed a greatly expanded number of researchers from its highly cited researcher lists. * After learning about the existence of plesiohedra, Jim Propp wants to know about stegohedra, ankylohedra, and icthyohedra. One possibility for stegohedra: a polyhedron with triangular faces each of which has exactly one concave and two convex dihedrals. * A photograph of George Green? A case study in historical misconception (\$\mathbb{M}\$). Peter Rowlett does some sleuthing and discovers that a purported photo of the British mathematician is really of an American wagon maker and civil war soldier. * Research papers containing hidden prompts directing artificial intelligence tools to give them good reviews (\$\mathbb{M}\$, via). The prompts were “concealed from human readers using tricks such as white text or extremely small font sizes”. The link gives no explicit examples but some can be found in the comment thread. * Interpreting hat color puzzle states as orientations of hypercube graphs. * The most useless data visualisation ever (\$\mathbb{M}\$): a bar chart of US GDP by year that shows a single bar of a fixed size, with only the scale markings changing if you use a slider to view different years. * Hexagonal box (not actually hexagonal). * Measuring the impact of early-2025 AI on experienced open-source developer productivity (\$\mathbb{M}\$). METR ran a controlled experiment with 16 experienced open-source developers on 246 programming tasks. The developers predicted that the use of AI would speed up their work by 25%, and after the experiment judged that it had sped it up by 20%. But when actually measured, the use of AI slowed down their work by 19%. * Record lattice sphere packings discovered (\$\mathbb{M}\$). The proof “utilizes a stochastically evolving ellipsoid that accumulates lattice points on its boundary, while containing no lattice points in its interior”, reviving an old but abandonded idea of Minkowski. * BusyBeaver(6) is really quite large (\$\mathbb{M}\$, see also). The previous bound of roughly \$10\uparrow\uparrow 15\$ is improved to at least \$2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow9>2\uparrow\uparrow\uparrow 5\$, while \$BB(7)>2\uparrow^{11}2\uparrow^{11}3\$, as expressed in Knuth’s up-arrow notation. Meanwhile the smallest \$n\$ for which ZFC cannot determine \$BB(n)\$ has been reduced from 643 to 588, but there’s a lot more room for improvement. * Carleson’s theorem formalized in Lean (\$\mathbb{M}\$). This is the one about pointwise almost everywhere convergence of Fourier series of \$L^2\$ functions, for which Wikipedia states “there are still no easy proofs”. * The vigorous and long-running academic debate about precisely what shape the polyhedron depicted in Dürer’s _Melencolia I_ is (\$\mathbb{M}\$). For another one sort of like this, see the debate on whether the sphere in Da Vinci’s _Salvator Mundi_ is hollow or solid, and what it is made of. * The new diamond open access journal _Annals of Formalized Mathematics_ publishes its first issue (\$\mathbb{M}\$). I’m particularly interested in Karayel’s “Derandomization with pseudorandomness”. It looks like it will be an interesting journal. By David Eppstein

15.07.2025 15:32 — 👍 0 🔁 0 💬 0 📌 0

Metascience of pull requests Last week, I wrote two posts on a related theme, but didn’t fully connect them to my earlier thoughts on the topic. I have a particular drum I’ve been beating consistently on this blog since I moved to Substack (and I have even older posts on it, too): 1. Though machine learning is statistical prediction, classical inferential statistics has nothing interesting to say about the field. 2. In fact, lessons from classical inferential statistics have historically provided poor, misleading guidance for machine learning practice. 3. A culture of frictionless reproducibility has been the primary driver of machine learning progress. I use the term classical inferential statistics loosely here, and Siva Balakrishnan is going to get mad at me about it. He and I cannot agree on a term to describe the narrow statistical subfield that I want to call out: frequentist claims about out-of-sample behavior derived from laws of large numbers and the union bound. This includes statistical significance, null hypothesis significance testing, and error bars.1 I’ve decided to try out “classical” because Jessica Hullman used it in her blog post advocating for more statistics in machine learning. I always find Jessica thought-provoking, and she links to me and asks at the end of the post. > “But others refer to attempts to incentivize more thorough reporting of uncertainty in ML evaluation as “a weird obsession with statistics. What’s up with that, I wonder?” I’ll reply here, though most of what I wanted to say was already written in the comments under Jessica’s post by frequent stat modeling interlocutor Anoneuoid: * Mandating null hypothesis significance testing and related ideas is a fast way to stifle progress. * Systematic errors are more important than sampling errors. * Since everyone started deep learning, machine learning papers have been reduced to advertisements of pull requests. * You don’t need 90 pages of robustness checks or proofs, since you can simply try the code and decide for yourself whether to accept it. I swear I am not Anoneuoid. We just happen to strongly agree about everything. But yes, I have made the same arguments on the blog many times. If the machine learning community had listened to the guidelines from classical inferential statistics, nothing would have ever gotten built. Machine learning was largely developed without the use of classical inferential statistics. In fact, the influence has gone in the opposite direction: since 1960, statistically minded researchers have been trying to bootstrap a “statistical learning theory” by chasing practice. The problem is that theories derived by shoe-horning practice into classical statistical footwear haven’t been productive. Every time this narrow view of classical statistics is applied, it gives the wrong advice! It’s been actively harmful to the field. It makes incorrect predictions and obsesses about the wrong type of error. The part of practice that most resembles classical statistics is the train-test paradigm.2 Statistics doesn’t explain why this is successful at all! If anything, this has polarized me against other conclusions drawn from statistical theory. Indeed, it makes me believe that claims about the scientific detriment of p-hacking and uncorrected multiple hypothesis testing are wildly overstated. Another post critiquing statistics is all well and good, but I have a more important point to make here about what we might consider doing instead. Jessica writes to Anoneuoid: > “But I guess part of what I find confusing about dismissing attempts to hold people accountable for what they are claiming (like the crazy long NeurIPS checklist that the linked post complains about) is that in the absence of suggesting an alternative way to better align the claims and the evidence, it reads as though we’re saying all is ok as is and uncertainty can continue to be an afterthought when presenting evaluation results.” I often feel like the solutionist burden placed on critics is an easy way to wave off critique. But on this issue, I am actually proposing an alternative! Open models, open data, and open code are a clear, feasible alternative requirement. These are not major asks. As I said in a previous post, the only reason we don’t require these is that there are still a lot of corporate interests at the big machine learning conferences, and these places always have some argument for why they can’t release code and data. David Pfau noted on Twitter that this is rapidly changing with the LLM arms race, with the companies moving towards abandoning publishing altogether. He might be right, but that doesn’t mean we have to encourage their nefarious behavior by embracing their move to proprietary secrecy. Jessica admits the problem herself in her review of Weijie Su’s argument for more statistics in machine learning research. > "Something a bit cringey that becomes clearer when you see the various statistical challenges laid out like this is that sometimes they arise not just because LLMs are too complex for us to understand, but also because they are proprietary objects.” The frustration with most modern published LLM papers is industrial closedness reduces open research to ephemeral flailing. If you are taking a proprietary, closed model and doing some prompt engineering to elicit funny answers, you are doing HCI research on proprietary software. If you train a transformer model from scratch on the orbits of planets and don’t use all of the language on the internet, your result says _nothing_ about LLMs. Even if you are fine-tuning an open weights model, there’s only so much we can learn because you have no idea what the training corpus is. Machine learning has thrived in its embrace of frictionless reproducibility— Open, shareable data. The ability to re-execute code. Competitive Testing. These are powerful tools to mitigate uncertainty. I’ve written some thoughts about why this is, drawing analogies to distributed optimization. I still think this is an excellent direction for meta-scientific study. But for whatever reason, many in the orbit of machine learning seem more interested in developing more statistical tests than in understanding why exactly this practice works so well. Let me close with quoting Andrew Gelman, who replied to Jessica, > “On the other side, Recht presents a very reasonable engineering perspective that is anti-bureaucratic: we've already made a lot of progress and continue to do so, so don't tell us what to do. Or, to put it more carefully, you can tell us what to do for safety or public policy reasons, but it seems like a mistake to try to restrict researchers' freedom in the belief that this will improve research progress. This general position makes sense to me, and it is similar to many things I've said and written regarding science reform: I don't want to tell people what to do, and I also don't want criticism to be suppressed. That doesn't mean that science-reform proposals are necessarily bad. For example, I find preregistration to be valuable (for the science, not the p-values), but I wouldn't want it to be a requirement.” I agree strongly here with Andrew. Our mandates should be few and far between. I advocate for only one: stronger norms about openness in code, data, and models. Subscribe now 1 I’ll leave the Bayesians alone today because no one is yet proposing LDA to be on the NeurIPS checklist yet. 2 Though the train test paradigm was invented by practice, not by a careful application of statistics. By Ben Recht

15.07.2025 14:52 — 👍 0 🔁 0 💬 0 📌 0

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson **Authors:** Jungho Ahn, Ian DeHaan, Eun Jung Kim, Euiwoong Lee We present a polynomial-time $(\alpha_{GW} + \varepsilon)$-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $\alpha_{GW} \approx 0.878$ is the approximation guarantee of the Goemans-Williamson algorithm and $\varepsilon > 10^{-34}$ is a fixed constant. To attain this, we give an improved analysis of a slight modification of the Goemans-Williamson algorithm for graphs in which triangles can be packed into a constant fraction of their edges. We then pair this analysis with structural results showing that both interval graphs and split graphs either have such a triangle packing or have maximum cut close to their number of edges. We also show that, subject to the Small Set Expansion Hypothesis, there exists a constant $c > 0$ such that there is no polyomial-time $(1 - c)$-approximation for Maximum Cut on split graphs.

15.07.2025 00:00 — 👍 0 🔁 0 💬 0 📌 0

TR25-094 | Communication Complexity is NP-hard | Shuichi Hirahara, Rahul Ilango, Bruno Loff In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing $CC(f)$ (the 2-way communication complexity of a given function $f$) NP-complete?} The problem of deciding whether $CC(f) \le k$, when given the communication matrix for $f$ and a number $k$, is easily seen to be in NP. Kushilevitz and Weinreb have shown that this problem is cryptographically hard. Here we show it is NP-hard.

14.07.2025 18:55 — 👍 0 🔁 0 💬 0 📌 0

TR25-093 | Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications | Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan We consider random walks on "balanced multislices" of any "grid" that respects the "symmetries" of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form $\mathcal{S}^n$ for finite $\mathcal{S}$, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in $\mathcal{S}$. A walk respects symmetries if the probability of going from $u = (u_1,\ldots,u_n)$ to $v = (v_1,\ldots,v_n)$ is invariant under simultaneous permutations of the coordinates of $u$ and $v$.) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost $\mathcal{O}(1)$-wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound. We give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for $d$-junta-sums mapping an arbitrary grid $\mathcal{S}^n$ to an Abelian group, correcting from a near-optimal $(\frac{1}{|\mathcal{S}|^{d}} - \varepsilon)$ fraction of errors for every $\varepsilon > 0$, where a $d$-junta-sum is a sum of (arbitrarily many) $d$-juntas (and a $d$-junta is a function that depends on only $d$ of the $n$ variables). Our proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis.

14.07.2025 18:28 — 👍 0 🔁 0 💬 0 📌 0

Latest posts by theory.report on Bluesky