Our press release this month features ten papers, making this one of the more crowded editions of PTRview. The lineup takes us through distribution-free testing, shortest paths, hypergraphs, numerical linear algebra, streaming, and a few other corners of sublinear algorithms. Before we get started, let me make a small aside. I think it is worth acknowledging the increasingly rapid progress of AI in mathematics. There is clearly a lot to be excited about, but I also find some of the implications rather concerning, and I share some of Terry Tao’s caution on where this may be taking mathematical research. This is perhaps a conversation for another day—and certainly not one I want to turn this month’s PTRview into—but I do think it is something our community should be talking about. With that out of the way, let us take a look at our spread. **Distribution-Free Halfspace Testing with Samples** by Xi Chen, Renato Ferreira Pinto Jr., Nathaniel Harms, Shyamal Patel, Rocco A. Servedio (arXiv) This featured paper confronts an old classic from the learning theory literature and, as the authors colorfully put it, attempts to understand just “when is the simplest and most trivial property testing algorithm also optimal, thereby justifying our laziness and ineptitude in algorithm design”. The classic problem they explore is learning halfspaces with respect to an unknown distribution. Let us consider the property testing analog of this task. So, you will work in the distribution-free model. Unpacking, I have an unknown distribution supported over \\(\mathbb{R}^n\\) and, according to some function \\(f\\), I tell you for any sample \\(x \in \mathbb{R}^n\\) whether \\(f(x) = 1\\) or \\(f(x) = 0\\). You want to answer whether \\(f\\) is consistent with some halfspace, or whether it is \\(\varepsilon\\)-far according to the unknown distribution from all halfspaces. Staying true to their colorful promise, the paper proves in Theorem 1.1 that yes, we should be happy that we were not able to cook up some super sample-efficient algorithm for this problem—because none exists! The paper gives two proofs of this result—one is human-generated (delegated to the appendix), and the other, which is AI-generated (with a human exposition), is provided in Section 2. The paper emphasizes that the AI proof also works when the domain is restricted to the Boolean hypercube. The proof proceeds via an application of Yao’s lemma. From a cursory glance, it appears that the construction of the YES and NO distributions is fairly elegant and allows for a slick lower-bound proof (which spans, with all the scaffolding in Section 2, a total of four pages). **Instance-Optimality of Bidirectional Dijkstra on Simple Graphs** by Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup, Hanzhi Wang, Shuyi Yan (arXiv). To understand what this paper is doing in PTReview reports, let us first recall a recent result of Haeupler, Hladík, Rozhoň, Tarjan and Tětek. As covered on Quanta, this paper showed that a carefully implemented version of bidirectional Dijkstra is _**instance-optimal**_ for finding shortest paths in weighted multigraphs. But what the hell do we mean by **instance-optimal**? To understand this, let us fix a particular graph \\(G\\) and a source-destination pair \\((s,t)\\), and consider algorithms that discover the graph by querying edges. An algorithm is instance-optimal if, on this particular instance, its number of queries is within a constant factor of the number of queries made by the best possible algorithm that accesses \\(G\\) only through the same query model. In particular, this is much stronger than a worst-case guarantee: we are saying that, on every individual instance, there is essentially no algorithm that can get away with substantially fewer queries. This is exactly the sort of phenomenon one hopes to exploit in sublinear algorithms—perhaps the shortest path can be found without even looking at most of the graph! But there is a small wrinkle. The HHRTT result applies to **multigraphs** , whereas the canonical shortest-path problem is usually formulated on **simple graphs**. So the natural question is: does bidirectional Dijkstra remain instance-optimal on simple weighted graphs? The featured paper answers this question, although the answer is not a simple yes or no. For simple **undirected unweighted** graphs, bidirectional Dijkstra is indeed instance-optimal when the edges are presented in a random order. On the other hand, the paper gives separations showing that instance-optimality can fail for other combinations of directed/undirected graphs, edge orderings, and access models. **A simple and practical \\(o(\sqrt n)\\)-time algorithm for shortest paths in power law graphs** by Jiaqi Mao (arXiv) This paper presents a shortest-path algorithm designed specifically for power-law graphs. I will paraphrase the abstract. One contribution of this work is a simple algorithm called _Pruned Bidirectional Search_ (PBS), which does not require any preprocessing and runs in time \(O\left(n^{(1-1/\log\log n)/2}\right)\), which is \(o(\sqrt{n})\). With high probability, the algorithm returns a path whose length is within a factor of \(41/32\) of the shortest path. If one is willing to pay for a preprocessing step of \(n^{\Theta(2-1/\log\log n)}\) time, the query time improves further to \(n^{\Theta(1/\log\log n)}\). The paper also reports experiments on real-world and synthetic power-law graphs, where PBS is \(1.84\)--\(7.76\) times faster than existing alternatives, while achieving an approximation ratio of at most \(1.05\). **A Tight Scale-Locality Bound for Partial Detection in Non-Adaptive Group Testing** by Nader H. Bshouty (arXiv) Alright, so here is a group testing problem. We have \\(n\\) items, of which an unknown number \\(d\\) are defective, and our goal is only to find \\(\ell\\) defective items. The paper considers the non-adaptive setting where \\(d\\) is unknown, and proves a tight bound of \\(\Theta(\ell\log^2(n/\ell))\\) tests. The lower bound comes from a neat “scale-locality” argument (throwback to the title): if we knew \\(d\\), finding \\(\ell\\) defectives requires about \\(\ell\log(n/d)\\) bits of information. But a fixed group test is informative only when its size is somehow compatible with \\(d\\), and hence is useful at only \\(O(1)\\) of the logarithmically many possible scales. Summing this information requirement over all scales gives the lower bound. The paper also gives a matching upper bound by running the known-$d$ algorithm in parallel over dyadic guesses for \\(d\\). **Sublinear Algorithms for Estimating the Number of Hyperedges in Arbitrary Hypergraphs** by Deeparnab Chakrabarty, Cooper LaPorte, (and our very own) C. Seshadhri (arXiv). Alright, now time for a hypergraph problem! Regular PTRview readers are no stranger to estimating the number of edges in graphs under various access models. The featured paper considers the challenge of estimating the number of hyperedges in an arbitrary \\(n\\)-vertex hypergraph using a sublinear in \\(n\\) number of queries. The paper notes that in the standard access model (which allows sampling random vertices, querying vertex degrees, and accessing incident hyperedges), there are simple lower bounds that rule out strongly sublinear algorithms for arbitrary, non-uniform hypergraphs. So, the paper instead considers a different access model motivated by a natural way to represent a hypergraph \\(H\\) as a bipartite incidence graph, with hyperedges on the right and vertices on the left. You connect a hyperedge to all the vertices it contains. The natural access model associated with this picture allows you to sample a random hyperedge (via its ID) as well as a random vertex. Additionally, you can query the arity of a hyperedge and obtain a random vertex incident to a hyperedge. The paper calls this the _dual access model_. In this model, the paper obtains a \\((1+\varepsilon)\\) approximation to the number \\(m\\) of hyperedges using \\(\approx \sqrt n \cdot \log n\\) queries. The paper also proves a nearly matching \\(\Omega(\sqrt n)\\) lower bound for obtaining even a constant-factor approximation. **Fast Length-Squared Sampling for Positive-Semidefinite Matrices** by Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian (arXiv) Alright, here is a numerical linear-algebra primitive that most of us have probably taken for granted. Consider the task of Length-squared sampling, i.e., you want to sample a column \\(i\\) with probability proportional to its squared \\(\ell_2\\)-norm, i.e., with probability \\(|A_{*,i}|_2^2/|A|_F^2\\). This is a standard primitive behind a number of randomized numerical-linear-algebra algorithms, including low-rank approximation and approximate matrix multiplication. The catch is that if all you have is entry-query access to an \\(n\times n\\) matrix, even computing the norm of a single column costs \\(n\\) queries. The featured paper shows that for PSD matrices, we can nevertheless perform this exact sampling in only \\(O(n)\\) expected time — which is optimal. The algorithm is a rather cute rejection-sampling scheme based on the PSD inequality \\(A_{ij}^2\leq A_{ii}A_{jj}\\). First sample two indices according to the “diagonal distribution”—which returns a diagonal entry with probability proportional to the entry, and then you use \\(A_{ij}\\) to decide whether to accept. Somehow, this gives exactly the desired length-squared distribution. The paper also gives applications of this primitive to estimating the Frobenius norm and other numerical linear-algebra tasks. **Streaming Algorithms for Monotonicity Testing** by Amir Azarmehr, Soheil Behnezhad, Lily Chung, Alma Ghafari, Jane Lange, Ronitt Rubinfeld (arXiv) This paper takes a streaming take on a classic property testing problem. Consider an \\(n\\)-vertex DAG \\(G\\) and a Boolean function \\(f\\) on its vertices. We say \\(f\\) is monotone if \\(f(u)\leq f(v)\\) whenever there is a directed edge from \\(u\\) to \\(v\\). The paper asks how well we can estimate the distance of \\(f\\) to monotonicity when the edges of \\(G\\) arrive in an arbitrary order and we are only allowed \\(\widetilde O(n)\\) space. The main result is a \\((1+\varepsilon)\\)-approximation using \\(\sqrt{n}^{1+o(1)}\\) passes, which is essentially optimal: any constant-factor approximation with fewer passes would imply a faster streaming algorithm for \\(st\\)-reachability. I find the main technical idea cool. The distance to monotonicity is exactly the size of a maximum matching in the _violation graph_ of \\(f\\). So the problem becomes one of estimating maximum matching size in a graph that we only have implicit access to through the original DAG. The paper connects this to sublinear-time algorithms for maximum matching, introducing stronger _vertex_ and _subset_ query models that can be implemented efficiently in the streaming setting. In particular, only polylogarithmically many subset queries are needed for a constant-factor approximation of maximum matching, which is what ultimately gives the \\(\sqrt{n}^{1+o(1)}\\) pass bound. **Ranked spreadness and sample-based testing** by Gaia Carenini (arXiv) Let us start the story from our News for April 2015 where we covered a paper by Fischer-Lachish-Vasudev which tried to understand the properties we could test when given only sample access to a combinatorial object. The main result of the paper showed that one can simulate a \\(q\\)-query (think \\(q = O(1)\\)), non-adaptive tester for an abstract property by a sample-based tester which used \\(O(n^{1-1/q^2})\\) samples. The featured paper presents a simulation that uses only \\(O(n^{1-1/q})\\) samples which was the bound conjectured in the preceding work. This is achieved via a suitable notion of _rank-spreadness_ , a pseudorandom notion inspired from the pseudorandom style notions which were used to improve bounds on sunflower lemma. **A quantitative container characterization of one-sided testability** by Gaia Carenini, Cameron Seth, Yuichi Yoshida (arXiv) So, containers strike again! Regular PTRview readers may remember our News for March 2024, where we covered another paper using the hypergraph container method in property testing. For those who missed it, let me briefly recall the basic idea: containers are a way of covering a complicated family of combinatorial objects by a much smaller collection of simpler objects. In the featured paper, the containers are used to characterize one-sided testability of hereditary graph properties. Roughly speaking, the paper shows that a hereditary graph property is one-sided testable if and only if a suitable family of associated hypergraphs admits an appropriate container structure. In short, the containers are back—and apparently they have not finished carrying things yet. **Sublinear Time Eigenvector Approximation via Column Sampling** by Rajarshi Bhattacharjee, Cameron Musco, Dominic Rutkowski (arXiv) We close with another problem from numerical linear-algebra with a sublinear twist. Given a symmetric matrix \\(A\in\mathbb{R}^{n\times n}\\) whose entries are bounded by \\(1\\), the paper asks whether we can approximate its outlying eigenvectors without even reading the whole matrix. The main result says yes: by uniformly sampling only \\(\widetilde O(\log n/\varepsilon^4)\\) columns, one can recover an approximate eigenvector for every eigenvalue \\(\lambda\\) satisfying \\(|\lambda|\geq\varepsilon n\\), with residual \\(|Av-\lambda v|_2\leq\varepsilon n\\). For the top eigenvector, the sample complexity improves to \\(\widetilde O(\log n/\varepsilon^2)\\), and the paper shows that this is tight up to logarithmic factors. The cute part is that the resulting eigenvectors are actually spanned by the small collection of sampled columns, so individual entries of the approximation can be computed in \\(poly(\log n,1/\varepsilon)\\) time. This puts the result squarely in the quantum-inspired algorithms framework, and gives the first sublinear-time classical algorithms for eigenvector approximation with additive error \\(\varepsilon|A|_F\\) By Akash

_Hi there, argmin readers! As the fall semester picks up, posting volume will, too. So I’m going to commit to writing short descriptive headers to help you sort through the different threads. Today’s post is a live blog of Class 6 of my graduate seminar “Forecasting: A Critical Retrospective.” A table of contents is here._ Given the week’s events, it’s a bit unfortunate that I scheduled our discussion of p(doom) for the last week of class. I predict AI won’t have killed us by then, and the real question is whether we’ll all be bored to tears discussing the topic in November. But the agenda for today, earthquakes, is a good preview for the challenges associated with quantifying uncertainties about catastrophe. Seismologists don’t think an earthquake will lead to human extinction, but it can cause massive casualties and damage. How do we quantify our predictions of whether an earthquake will happen? And then what do we do about it? Most experts agree that predicting the exact time and location of earthquakes on long time horizons is impossible. The dynamics of the Earth moving, building up stress, and slipping are far too complicated to predict with any reasonable granularity using differential equation models. Earthquake forecasting couldn’t be further removed from weather forecasting in that regard. At best, we can make coarse predictions based on a mix of temporal and spatial localization. Earthquakes tend to occur near fault lines. Fault lines have a history of previous ruptures of different sizes. Using these data, we can estimate rough statistical models. You might naively estimate an exponential recurrence time: the rate at which earthquakes occur is just the count divided by the observation window. In an exponential model, the expected time to the next earthquake would be the inverse of this number. A slightly more complicated formula then gives you the chance of an earthquake in the next decade. chance = 1 - np.exp( - rate * time ) Such primitive models are not precise, but they are helpful. What do you do with these probabilities? You can turn them into general warnings. If you expect a certain frequency of shaking, you should build infrastructure that can withstand it and teach people how to prepare for the disruption the next one will cause. If you know big earthquakes occur every few decades, that’s enough to inform planning and insurance. But nailing down the probability of an earthquake, even to one decimal place, is a fool’s errand. Our first reading of the week, Freedman and Stark’s classic paper “What is the Chance of an Earthquake?”, highlights the futility of precise probability models. If you want to validate a probabilistic forecast, you need a lot of events. The law of large numbers needs a lot of numbers! Large earthquakes are rare. Probabilistic models can’t be tested on human time scales. Moreover, when you add more geological reality to your model, you introduce a variety of hard-to-estimate parameters and researcher degrees of freedom into the equations. Every new modeling assumption introduces new unidentifiable parameters. More realistic doesn’t mean better estimates. If you want to predict _really_ big earthquakes, like those with magnitudes greater than 8.5, then we have an even sparser record. The old-fashioned AI chatbot, Wikipedia, has dozens of tables listing earthquakes by all sorts of characteristics. It lists only 17 of these in the past hundred years. Scientists have developed techniques to infer the occurrence of giant earthquakes thousands of years in the past. These tend to give noisier estimates of recurrence times, but sometimes they yield very ominous predictions. One of the most ominous is in this week’s reading, “The Really Big One,” a riveting 2015 New Yorker article by Kathryn Schulz. Schulz reports on the Cascadia subduction zone, a thousand-mile fault that runs from Northern California to Vancouver Island. Combining oral history, Japanese tsunami records, and tree rings, seismologists determined that a massive earthquake, with a magnitude pinned between 8.7 and 9.2 on the Richter scale, happened on this fault on the evening of January 26, 1700. It killed coastal forests of the Pacific Northwest and created a massive tsunami in Japan. Oral histories from First Nations tell of entire communities vanishing. Scientists have gone back to geological samples and counted 41 major earthquakes on this fault in the last ten thousand years. Using the rough rule of thumb, we should expect a major, destructive earthquake once every 243 years. It’s been 326 years since the last one. Now, you could try to guess the probability that an earthquake occurs on this fault before 2050, but that number doesn’t really do much of anything for you. We don’t know when it will occur, but we know an earthquake is inevitable here, and we know it will be catastrophic. Shulz details some predictive horror stories of what will happen when the next big one hits the Cascadia Subduction Zone. It does seem like a bad idea to put millions of people near such a seismically volatile region. But this is the problem with our slow ape brains. As Shutz writes, “[forty] years ago, no one knew that the Cascadia subduction zone had ever produced a major earthquake. [Fifty-five] years ago, no one even knew it existed.” In 1970, Seattle was already a major city with over half a million people. So the question is, what do we do now? The low end of state estimates of fatalities from the next major earthquake is in the tens of thousands. One answer would be to move millions of people away from the danger zone. No one is proposing this. The other is to build as much infrastructure as possible to handle the incoming crisis through seismic retrofitting and social infrastructure for tsunami evacuation protocols and earthquake preparedness. The work involves building systems to keep damage as small as possible, even though the damage will be unavoidably large. As Freedman and Stark say, “probabilities are a distraction.” Subscribe now By Ben Recht

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for all values of $p, q, \epsilon$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/\epsilon$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

We prove that, for every constant $\varepsilon>0$ and every function $f:\Sigma^n\to\\{0, 1\\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\\{0, 1\\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ with probability at least $1-\varepsilon$. The bound is independent of the alphabet size and also holds for monotone Boolean functions on $[0,1]^n$, resolving a conjecture of Friedgut (Combinatorics, Probability and Computing, 2004). Unlike the Boolean cube setting, where Kahn, Kalai, and Linial (FOCS, 1988) give a coalition bound of $O(n/\log n)$, no sublinear bound independent of the alphabet size was previously known. In collective coin flipping, our result gives the first sublinear bound on the number of bad players needed to force a fixed output with probability at least $1-\varepsilon$ in any one-round protocol with independent uniform messages, regardless of the message length. A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the $p$-biased influence of the encoded function. We then rely on a structure theorem of Hatami (Annals of Mathematics, 2012) for functions with small $p$-biased influence to bias the encoded function.

**Authors:** Tetsuo Yokoyama We determine the exact time exponent of space-optimal reversible pebbling on chains as $1.331742379256310\ldots$. The growth rate of space-optimal reach exists as a limit and admits a variational formula. The same exponent governs complete computations at minimal space, uniformly in the chain length.

Shana Tova _Shana Tova (happy new Jewish year) to all our readers! We have just returned to Tel Aviv from the beautiful city of Tiberias, on the Sea of Galilee._ The Simplex cube conjecture The simplex–cube conjecture was posed in my 1990 paper and was among the five problems on convex polytopes discussed in this 2008 post. **Conjecture A.** For every there exists an integer such that if is a -polytope with , then has a -face which is either a simplex or (combinatorially) a cube. We denote by the smallest such integer, if it exists, and otherwise set . A weaker conjecture, which remains open in general, is the following. **Conjecture B.** For every positive integer , there exist an integer and a finite collection of -dimensional polytopes such that every -polytope with has a -face combinatorially equivalent to a member of . As with , we let denote the smallest possible threshold, and set if no such threshold exists. Euler’s theorem implies that $latex d′(2)=3$: every 3-polytope has a 2-face that is a triangle, quadrilateral, or pentagon. I proved that $latex d(2)=5$, namely, every 5-polytope has a 2-face that is either a triangle or a quadrilateral. This answered a question of Perles and Shephard from 1967. The bound is sharp: the regular 120-cell is a 4-polytope all of whose 2-faces are pentagons. On Unavoidable Faces of High-Dimensional Polytopes I was very happy to learn that Jesús A. De Loera, Ethan X. Fang, Shengtao Guo, Junwei Lu, and Hailun Zheng in their paper On Unavoidable Faces of High Dimensional Polytopes proved **Conjecture A** for **_simple polytopes,_** along with other remarkable results. (A -polytope is simple if exactly edges meet at each vertex.) In my 1990 paper I considered the asymmetric version of the conjecture. Let be positive integers, and let be the smallest integer such that every polytope of dimension at least contains either an -dimensional simplex face or a -dimensional face combinatorially equivalent to a cube. If no such integer exists, set . The simplex–cube conjecture asserts that for all . The diagonal case is . If denotes the corresponding threshold restricted to simple polytopes, De Loera, Fang, Guo, Lu, and Zheng proved that for every and . Moreover, they obtained the explicit bounds: > _**Theorem (De Loera, Fang, Guo, Lu, and Zheng).** For every integer :_ > > _**(i)** ._ > > _**(ii)** For every integer ,_ > > _._ The first bound slightly improves my old bound . The paper contains several other developments. First, the authors obtain substantial new _lower bounds_ for both the general and simple versions of the problem. Second, they make remarkable progress on a related question concerning unavoidable small 3-dimensional faces. Earlier work of Meisinger, Kleinschmidt, and me showed that every rational -polytope with has a 3-face with fewer than 78 vertices or fewer than 78 facets. For dimensions at least 15, the new paper substantially improves the size bound and removes the rationality assumption: every convex polytope in these dimensions has a 3-face with at most 13 facets. The proof uses the nonnegativity of toric -numbers, inequalities due to Billera and Ehrenborg for the -index, and convolution operations. An exact rational certificate involving flag numbers is obtained using linear programming. By Gil Kalai

**Authors:** Heinrich Jiang, Hager Yasser Mohamed, Alexander Hitt, Valeriia Lomakina, Henning Jiang, Jennifer Jang Boundary representation (B-rep) is the standard format used by modern CAD systems for parametric 3D models. It turns out, the exact same solid can be represented by different B-reps: for example, two engineers using different operations, a geometry kernel rebuilding the file, and an export setting repartitioning faces will lead to different B-reps even though the underlying solid remains the same. We show that existing B-rep encoders are not robust to variation in the B-rep with the same solid on perturbations applied to standard benchmarks, naturally occurring variations inherent to CAD software, and differences in how designers model the same part via a human dataset we created in FreeCAD. The performance of popular B-rep encoders often collapses catastrophically. We propose the canonical region graph, an input representation whose nodes, features and coordinate frame are derived from the solid itself and show theoretical invariance guarantees on repartitioning and rigid motions. It matches the strongest baseline on standard benchmarks, and is stable under every perturbation we test.

**Authors:** Andreas F. Holmsen, Alfredo Hubard In this paper we introduce a generalization of Helly's theorem closely connected to Bárány-Gromov overlap theorems (also called selection lemmas). Our main result implies both the topological colorful Helly of Kalai and Meschulam and Karasev's topological centerpoint theorem. We further investigate the topological fractional Helly theorem from this overlap perspective, and show an overlap theorem for dense complexes (a continuous second selection lemma for tame maps).

We invite applications for a postdoctoral position in quantum complexity theory at Concordia University in Montréal, working with Honghao Fu and Benjamin Lovitz. Funding is available until March 2028. We welcome candidates with a strong research background in quantum complexity theory or closely related areas of theoretical computer science, quantum information, and mathematics. Website: https://www.concordia.ca/gradstudies/postdocs.html Email: benjamin.lovitz@concordia.ca By shacharlovett

We present a methodology for constructing interactive proof systems. This methodology, which is implicit in prior works, consists of reducing the original claim to an iteratively generated sequence of claims such that each claim is (interactively) generated based on the prior claim. Viewing each of these interactive generation steps as solving an adequate search problem, we present composition results that support a modular construction of interactive proof systems as well as their transformations to PCIPs (aka IOPs). The development of the foregoing methodology involves the explicit introduction of a few notions, which are of independent interest. These include ``dichotomous search problems'' (to be solved by protocols analogous to interactive proofs) and oracle-aided protocols (in which the oracle is a search problem rather than a decision problem). Using the foregoing methodology, we prove that every set in uniform-$\cal NC$ has a doubly-efficient PCIP. This result was conjectured by Arnon, Chiesa, and Yogev ({\em 37th CCC}, 2022), and our construction follows their ideas. Our contribution is in adapting their ``IP to PCIP'' transformation to the context of oracle-aided protocols and applying the foregoing methodology while following the ideas of Goldwasser, Kalai, and Rothblum ({\em 40th STOC}, 2008).

In the early to mid-1970s, my university classmate Ariel Rubinstein initiated a weekend hike from Jerusalem to the Dead Sea. A group of us left Jerusalem on Friday night, planning to reach the Dead Sea early the next morning. However, due to navigation errors and other obstacles, we didn’t arrive until noon. We were all exhausted and out of water. I then hitchhiked back to Jerusalem and was picked up by a kind driver, who was driving a massive truck. The two-lane road from the Dead Sea (−392 meters) to Jerusalem (+800 meters) was steep, and from time to time, our truck overtook other vehicles in a rather dangerous fashion. Sensing my discomfort, the truck driver shared an interesting theory: “You see, the engine of this truck is so strong — so strong — that whenever I start to overtake, I can always complete the maneuver safely!” This struck me as incorrect. The ability to overtake safely depends not only on engine power, but also on factors like visibility, road conditions, and the distance and speed of oncoming traffic. I thought this might be a case where pointing out the mistake could actually matter — not just to us, but to the safety of everyone on the road. I decided to offer an explanation that avoided technical jargon like “function.” “I think you’re mistaken,” I said, “Completing an overtake safely depends on several important factors — not just the power of your engine.” I elaborated a little further, and the driver listened with interest. “Ohh, that’s what you think?” he replied. “Now, watch this!” With that, the truck veered into the opposite lane in an especially dangerous maneuver. A few cars coming the other way swerved to the shoulder in panic, and — by a miracle — the truck completed the overtake without a collision. I said nothing more and sat quietly, disheartened, waiting for us to reach Jerusalem. Left: map of the hike; Right: Ariel Rubinstein By Gil Kalai

Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity $Q=\widetilde{\Theta}(M)$, and randomized query complexity $R=\Theta(M^{21/20})$, whereas, for every fixed $0<\eta<1/100$ and $S\le O(M^{1/100-\eta})$, its $S$-space quantum query complexity satisfies $Q_S=\omega(M^{21/20})$. Consequently, $$ Q<R<Q_S, $$ so the unrestricted quantum query advantage disappears under sufficiently small workspace. The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.

The Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) are the fundamental algorithmic questions in the geometry of numbers. In the past two decades, their algorithmic complexity has been studied quite extensively due to their connection with lattice based cryptosystems. In this paper, we study these problems in the setting of generic black-box metric query model, which captures algorithms that rely on distance evaluations without exploiting specific geometry of the underlying metric. We prove that any randomized algorithm for solving SVP or CVP within any constant factor $\gamma < 2/\sqrt{3} \approx 1.154$ which accesses the metric as a black-box oracle needs to make at least $2^{\Omega(n)}$ queries to the metric oracle. Our results rely on fundamental tools from the geometry of numbers and convex geometry. For our SVP lower bound, we use Siegel's Mean Value Theorem to probabilistically construct an adversarial metric by introducing $2^{\Omega(n)}$ disjoint local convex perturbations to the underlying Euclidean norm. The lower bound for CVP follows from the SVP lower bound by observing that the known Turing reduction from SVP to CVP works in the black-box metric query model.

**Authors:** Georgios Stamoulis In the uniform sparsest cut problem we are asked to find a vertex set that cuts few edges relative to the number of vertex pairs it separates. The Goemans-Linial SDP coupled with the Arora-Rao-Vazirani rounding gives an $\mathcal{O}(\sqrt{\log n})$ approximation on arbitrary graphs on $n$ vertices. We study this relaxation on finite Abelian Cayley graphs. First we show that when the second normalized Laplacian eigenvalue of $G= \mathrm{Cayley}(Γ, S)$ is realized by a Fourier character with image size at most four then $λ_2(G)=\mathrm{SDP}_{\mathrm{GL}}(G)=ψ(G)$. Geometrically, a character maps the vertices onto a regular polygon where the squared chord distance satisfies the triangle inequalities exactly when the polygon has at most four vertices. Grouping equal character fibers gives a cyclic quotient where the optimal cut can be found exactly and so the relaxation is exact on finite Abelian Cayley graphs on groups of exponent at most four. Second, we replace each generator $s$ of $S$ by a uniformly random element of its cyclic subgroup (including identity). If $r_s$ is the order of $s$, we let $α(r_s)$ to be the average number of $\pm s$ steps needed to simulate such a move, and let $ρ(S)=\max_{s\in S}α(r_s)$ be its worst case. Full cyclic averaging eliminates character phases and choosing a nontrivial character $χ^*$ minimizing the auxiliary eigenvalue and taking $K=\mathrm{ker}χ^*$ gives \\[ ψ(G)\leqψ_G(K)\leq\frac{q^*}{q^*-1} \cdotρ(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G)\leq 2ρ(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G), \\] where $q^*=|χ^*(Γ)|$. If all generator orders are at most $R$, this is an $R/2$ approximation. Finally, we construct an infinite family of finite Abelian Cayley graphs with Goemans-Linial integrality gap exactly $16/15$.

We provide a deterministic polynomial-time list decoding algorithm for Reed-Solomon codes over prime fields that approaches list decoding capacity on every evaluation set in the low (constant) rate regime.

**Authors:** Yu Liu We study non-adaptive selection of a feasible set $S$ so as to maximize the expected sum of the $k$ largest realized values among independent nonnegative discrete random variables. The same objective arises when hiring a team of $k$ workers or when computing VCG welfare in an $\ell$-unit auction. The main setting is a fixed-dimensional nonnegative packing family: the natural LP has $d=O(1)$ packing inequalities with binary coefficients. No single algorithm achieves a constant factor on every membership family (already at $k=1$). Given an $α$-approximate max-sum oracle, a decreasing surplus search yields ratio $α/((1+α)(1+\eps))$ for every $k\ge 1$ (cuts included). Every fixed-$d$ packing family already has a deterministic max-sum PTAS, hence inherits that constant. The same signatures that drive the exact-sum scheme---occupancy histograms when $k=O(1/\eps^2)$, and a three-dimensional mixture-quantile type when $k=Ω(1/\eps^2)$---are realized by a packing LP rather than by exact-sum, after enumerating $n^{f(d,1/\eps)}$ heavy items. The result is a PTAS for every $k\ge 1$ on every fixed-$d$ packing family, including binary one- and two-dimensional knapsack. In this packing setting the scheme is essentially optimal as a generic guarantee: there is no FPTAS that works for every such $\F$ unless $P=NP$, and no EPTAS unless $W[1]=FPT$ (two-dimensional knapsack is a witness, already at $k=1$). A separate boundary is query-weight exact-sum, which includes DAG paths and matchings and is incomparable with fixed-$d$ packing. That oracle also yields a PTAS for every $k$, so $d$-dimensional packing is a useful taxonomy, not a partition of every family that admits a PTAS.

_Hi there, argmin readers! As the fall semester picks up, posting volume will, too. So I’m going to commit to writing short descriptive headers to help you sort through the different threads. Today’s post is a live blog of Lecture 3 of my graduate seminar “Forecasting: A Critical Retrospective.” A table of contents is here._ Since the Great Depression, US law has required financial management companies that offer products like mutual funds to add a disclaimer to all of their advertising: “Past performance is not indicative of future results” The thing is, not a single person believes this. The fund managers don’t believe it, and neither do the customers. Why would you buy a mutual fund if you didn’t think its past performance told you something about how much you’ll have upon retirement? We tend to believe that some investments are _riskier_ than others and some managers are more reputable than others. These beliefs are based upon past observations, and we use them to inform our investment decisions. So what do we need to do to transform past observations into forecasts? We believe that the past can’t perfectly predict the future. We also believe that a forecaster is only as good as their track record. In today’s class, we’ll link these two together, showing how the evaluation metric for forecast track records leads us to particular forecasting algorithms. Let’s start with the two main examples from Edmond Halley. We believe the past strongly predicts the future when talking about the motions of celestial bodies. We believe it far less when pricing individual insurance policies. For his comet, Halley paired three observations together using insights about orbital shapes from Isaac Newton. Given the roughly 76-year gaps between these observations, he predicted we’d see the same object again 76 years later. In 1835, by the time we had seen Halley’s comet twice more, astronomers were uniformly convinced Halley was right and were certain we’d see the comet again in 1910 and 1986 (they were proven correct). For his life table, Halley grouped people by age and used these cohorts to make demographic forecasts. The proportion of the population aged 25 was 1.668%, and the proportion aged 26 was 1.647%. Therefore, he concluded the odds a 25-year-old would live to see 26 were approximately 80 to 1 in favor. The move in the demography example to consider odds and chance is interesting, and was something in the air at the time. Proto-demographer John Graunt had made similar calculations of hazard and risk in his tabulations thirty years earlier. Probability applied to casino games had only begun to be formalized forty years earlier. The transmutation of frequencies into risk was intuitive once you started assembling databases. Now we just take it for granted, having created a formal structure that hides the intuition. In today’s lecture, we’ll work out some of the formalism of this map from rates to risks, deriving the mathematical formulas that encode our assumptions. If you assert that a forecaster will be evaluated on their track record, and if you believe that events are effectively the same, then you bind yourself to making future predictions a deterministic function of the observed rates. The assumptions here are usually implicit. We’re assuming a strong level of interchangeability between past and future events with a particular signature. And we tend to use metrics that beg the question: the common scoring rules always return probabilistic forecasts. The evaluation ties your hands to making a particular form of forecast. Given a set of knowledge and a statistical score, you are forced to make a constant prediction for all future events. If you allow your predictions to be real-valued, they are suboptimal if they don’t obey the rules of probability. The score itself leads us into a probabilistic mindset. I’ve been calling this _metrical determinism,_ and I find myself inserting some variant of this lecture in every class I teach. Both the comet example and the life table example can be thought of as scoring track records on average. When you have highly predictable events, a perfect score is possible, but it takes a few hits to convince a skeptic that you really have nailed it down. When events are less predictable, you just want to make sure you’re not losing money on your annuity sales, and maximizing future profits again leads you into a particular form of forecasting. What’s important here is we don’t have to assume some sort of generative model of randomness to buy into probabilistic prediction. Halley did not have to assume that god was playing dice with who lived and died. Instead, probabilities and odds were simply convenient tools for the actuary to price their products. Probability was the logical consequence of assuming past performance was indicative of future results. Subscribe now By Ben Recht

The θ(p꜀) = 0 conjecture is solved in all dimensions. In 2024 Gady Kozma and Shahaf Nitzan showed how to derive the dying percolation conjecture from a proposed conjecture about percolation on general graphs. (I briefly discussed it in this post. Their conjecture was so general that many of us expected a counterexample to be discovered before long.) The dying percolation conjecture asserts that for percolation in at the critical probability, with probability one, there is no infinite cluster. This was known for planar percolation and for percolation in high dimensions. It was a famous open problem in the intermediate dimensions starting with dimension 3. A Claude document, accompanied with a Lean verification, claims a positive solution to the Kozma-Nitzan conjecture. (h/t to Itai Benjamini who told me about it yesterday and also about Hugo’s post.) If verified, this is a remarkable breakthrough. See here and here for the AI’s documents. There are very interesting related question about three-dimensional percolation. Is critical percolation in dimension three noise sensitive? Is the total influence of critical finite percolation (for large finite n by n by n box) larger than ? Larger than some ? (Here are positive.) I had a long research project around these questions with Gady, in which we managed to prove some interesting lemmas. We hoped to bring influences and Fourier tools to the picture. Hugo’s Duminil-Copin’s post on “Proofs and Prompts” There is a very interesting new blog called Proofs and Prompts and Hugo Duminil-Copin wrote a thoughtful post Care for a little more AI? about AI and mathematics, using the θ(p꜀) = 0 problem as a primary example. This was three days before Claude claimed the proof and several commentators remarked about the new AI proof. I liked Alonso Castillo-Ramirez’ comment: “we can still have great joy and be marvelled by the beauty of mathematics on its own, independently if it was created by a human or an AI.” And here is a moving Facebook post by another famous researcher in percolation theory – Jeff Steif. By Gil Kalai

**Authors:** Julia Baligacs, Davide Bilò, Václav Blažej, Maël Dumas, Anna Zych-Pawlewicz Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal $α$-spanner of a temporal graph with $n$ vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of $α$. While general temporal graphs may not admit sparse temporal $α$-spanners for any value of $α$, temporal cliques are known to admit temporal $(2k-1)$-spanners of size $\widetilde{\mathcal{O}}(kn^{1+1/k})$ for every positive integer $k$. We present a simple recursive algorithm that computes, for every temporal clique on $n$ vertices, a temporal $3$-spanner of size $n^{1+2/\sqrt{\ln n}}=n^{1+o(1)}$, thereby improving the previous best upper bound of $\widetilde{\mathcal{O}}(n^{3/2})$. We also show that a modified version of our algorithm computes temporal $3$-spanners of size $\mathcal{O}(nL)$ when the lifetime is bounded by $L$, i.e., all time labels are in $\\{1,\ldots,L\\}$, thus improving the previous bound of $\mathcal{O}(2^Ln\log n)$. Both results are particularly striking in light of the known lower bound of $Ω(n^2)$ on the size of temporal $2$-spanners, which already holds for temporal cliques of lifetime $L\geq 3$. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only $\mathcal{O}(n)$ carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.

Ben Brubaker has a new Quanta essay Does Computer Science Need Computers? Despite the title (and authors generally don't choose their titles), Brubaker's essay really addresses the question as to whether computer science is about computers. He starts with Dijkstra's apocryphal quote "Computer science is no more about computers than astronomy is about telescopes." This is the wrong analogy: computers are not the telescopes, they are the stars. You just have to use a broad definition of computer. The word "computer" goes back to at least 1613. The etymology 1. Latin com- meant “together.” 2. Putāre meant “to reckon” or “calculate”—and originally “to prune” or “clear up.” 3. English added -er, meaning “someone or something that performs an action.” The word originally meant one who computes, usually referring to a human performing a computational task. Its meaning as a machine didn't come into wide use until the mid-20th century. I start off every undergraduate theory class I teach with the question "What is a Computer", even in my Foundations of Complexity posts. After some discussion we end up with a diagram like this. --- A Computer The computer doesn't need to be electrical, mechanical or biological. You can think of the postal service delivering a letter based on an address, an auction arriving at a price, or even a well that draws water as we pull a rope. The Church-Turing thesis says the process can always be represented by a Turing machine, and then we are off to the races. When theoretical computer science stops talking about computing, it just becomes mathematics and no longer computer science. If we want to keep it computer science, we need a computer at the center, some kind of process. How about the title "Does Computer Science Need Computers?" No, not for electronic computers, though they've become more helpful, especially in this AI era. But doing research in computing is a process in itself. Alan Turing drew inspiration for his machine from thinking about how a mathematician works. So yes, you need a computer for computer science, and a computer for astronomy and every other discipline, even if that computer is just yourself. By Lance Fortnow

Akiva Kadari, Pablo Soberon and the cascade conjecture The cascade conjecture is discussed in this post. I proposed the conjecture back in 1974, inspired by work by Meir Katchalski (though the name “Cascade Conjecture” only came into use over the last decade or two). Akiva Kadari, a master’s student of Micha Perles, proved the planar case in his M.Sc. thesis. Although the proof was ready in the early-to-mid 1980s, writing the thesis was delayed until 1990, when Micha was on sabbatical and I stepped in as a co-supervisor. (Akiva himself was present in the lecture.) This is the conjecture Recently. Pablo Soberón proved a remarkable weaker version of the conjecture using topological methods—we will devote a dedicated post to it soon. Very recently, Pablo also disproved the last open case of Grünbaum’s famous mass partition conjecture. Yaacov Kupitz and Geometric graph theory Yaacov Kupitz once decided to spend a year abroad and got in touch with the famous mathematician John Conway. Just a few weeks before taking off, Yaacov discovered he was going to a _different_ John Conway—also famous, but in an entirely different field! Pivoting quickly, Yaacov instead spent a year in Aarhus, Denmark, where he wrote an influential monograph on geometric graphs (which later became his M.Sc. thesis). Vertices in geometric graphs are points in the plane, and edges are line segments (or sometimes pseudo-line segments) between them. It is a fascinating area, and we have written about it here before. János Pach took Micha Perles’s course on geometric graphs at Rutgers in 1989 and subsequently added the topic to his own research interests. In a previous post, we presented two of Micha’s proofs in geometric graph theory, both related to arthropods: his “proof by Lice” and his “proof for Caterpillars.” A nice story: Micha was once invited to spend a sabbatical at Rutgers at the newly founded DIMACS. One evening, he received a phone call from Daniel Gorenstein, the founding director of DIMACS, who explained that they needed to lower their offer from $70,000 to $65,000. Micha was quite surprised and responded that when he had originally accepted the offer (also over the phone), he was sure it was $17,000! Two Helly type problems from the 70s I thought the proof would come from a certain extension of the Nerve Theorem, but it arrived from a different direction instead. Very recently, the conjecture was proved for by Giuliamaria Menara in the paper A Helly-Type Theorem for two-component convex sets. I presented this conjecture in a birthday party of another Micha—Micha Sharir. Shortly afterward, it was settled and since then further extended in various directions. Meir Katchalski’s theorems about the dimensions of intersections of convex sets. Meir Katchalski’s beautiful theorems about the dimensions of intersections of convex sets were proved as part of his master’s and doctoral work. He obtained results regarding fractional Helly theorems, common transversals, and various other directions. (In my own doctoral work, I settled a conjecture by Katchalski and Perles.) Meir is the son of Israel’s fourth president, the renowned biologist Ephraim Katzir. I also spoke a bit about Branko Grünbaum, Micha’s doctoral supervisor. In one of the pictures , you can see representatives of five academic generations starting with Branko. Ido Shemer and neighborly polytopes Ido Shemer was a Ph.D. student around the same time as Noga Alon, Yaacov Kupitz, and me. His thesis was on neighborly polytopes, and he invented the “sewing” method. The Kupitz-Perles conjecture We devoted two posts to this beautiful conjecture (here and here), and Rom Pinchasi talked about it in greater detail in his lecture. When Rom proved his remarkable result, I used to ask him in a friendly way (or so I thought!), as a gesture of appreciation for his abilities: “What about ?” From Rom’s lecture, I learned that he felt uncomfortable about this and regarded it as a form of pressure. To quote Rom: “Gil log-log-logged me every time he saw me in the corridors of the Einstein Institute.” Four slides from Rom’s lecture. Ziva Deutsch non convexity and graph homomorphisms Nonconvexity is a very interesting topic closely related to graph homomorphisms—a subject that was greatly advanced by Perles and his students, as well as by Jarik Nešetřil and his colleagues. Two decades ago, Jarik gave a lecture series in Jerusalem on graph homomorphisms. The shapes in the slide are taken from a 1970 paper by Kay and Guay (see the picture below). Interesting examples of nonconvexity. You can see two interesting extensions of the Magen David symbol, as well as two “dancing rulers.” Here are Mazi, my mother, and me with Micha and members of his family. The younger daughter in the picture came to the session along with Micha’s oldest daughter. Two of Micha’s grandchildren, Shlomi and Itai, also attended—turns out they participated in our Math + AI project! Moshe Rosenfeld, Yosi Zaks, and Amos Altshuler I also wanted to mention three contemporaries of Micha: Moshe, Yosi, and Amos. Yosi Zaks and Moshe Rosenfeld were both students of Grünbaum—I mentioned their work and their problems here, here, and here. Amos Altshuler is the same age as Micha, but was unofficially Micha’s doctoral student (officially, he was Furstenberg’s student). Amos’s Ph.D. thesis discussed high-dimensional analogs of Hamiltonian cycles, which he tried to find in the boundary complexes of stacked polytopes. An anecdote: Ehud, Ziva, and Micha Michael Kallay and Zeev Smilansky Michael Kallay (an older academic brother) and Zeev Smilansky (a younger one) studied the decomposition of polytopes. (In Hebrew, Michael’s surname and mine have the exact same spelling.) I was enthusiastic about Zeev’s extensions of cyclic polytopes—though Zeev himself did not share my enthusiasm! Zeev eventually moved into biotech, winemaking, and writing prose and poetry, all while spending decades trying to find an elementary geometric proof and strengthenings for the unimodality of the $h$-vector of simple polytopes. (See this post.) Kallay’s father was a mathematician who wrote an early Hebrew book on calculus. Zeev Smilansky’s father was the famous writer Izhar Smilansky (S. Izhar). Micha’s early work on Gale’s transform Micha Perles used the Gale transform to translate the geometric and combinatorial properties of a -dimensional polytope into a lower-dimensional vector configuration in . This made it possible to study, classify, enumerate and construct complex, higher-dimensional polytopes through lower-dimensional representation. One of the most famous applications was Perles constructions an 8-dimensional polytope with 12 vertices that cannot be realized with rational Cartesian coordinates. Gale transform record the affine dependencies among vertices, and many years ago I conjectured that the space of affine stresses could lead to a similar useful “transform”. Enumeration of skeletons of polytopes This is another beautiful theorem by Micha Perles and a beautiful subsequent theorem by Arnau Padrol. Jamil Kasem’s thesis Kasem’s thesis dealt with neighborly families of standard boxes which are described by packing of a complete graph with complete bipartite graphs. Another anecdote I cannot translate it to English. Since that telephone call Ehud refers to ChatGPT as “my daughter Chatgi.” By Gil Kalai

**Authors:** Filippo Baroni, David Fisac, Mingkun Liu On the once-punctured torus, we give an exact formula for the number of curves in any given mapping class group orbit of given word length. This settles a conjecture of Chas in [Cha16].

**Authors:** Martin Kolář We show that a certified formalization of the hitting-set-existence axiom of Atserias and Tzameret, instantiated on the parity-based Nisan-Wigderson compression class of Khaniki, is independent of the two-sorted theory $V^0_1$ of $\mathrm{AC}^0$-reasoning, unconditionally: $V^0_1$ proves neither it nor its negation. The same holds for the corresponding certified dual weak pigeonhole principle, whose refutation is witnessed by a single seed that certified-computes every string of the model simultaneously. The mechanism is a bounded-arithmetic transfer of Atserias-Tzameret's reduction from hitting sets to the dual weak pigeonhole principle: the amplification half of that reduction, the sole source of its NP-oracle, is unnecessary at the native stretch of the Nisan-Wigderson map, and the compression half becomes a $V^0_1$-provable implication once circuit evaluation is replaced by its certified $Σ^B_0$ unfolding. This is, to our knowledge, the first independence result for a derandomization-flavoured existence principle at the $\mathrm{AC}^0$-reasoning level, and it makes explicit the bridge between the Khaniki Nisan-Wigderson line and the Atserias-Tzameret reverse mathematics of hitting sets.

BILL: Lance, I have a question and a meta question: a) List all the presidents and vice presidents who were colorblind. b) Do you know this sort of thing since you are colorblind, and hence might have looked this up in the past? LANCE: (b) No. And if Marco Rubio runs for president in 2028 he will need to earn my vote. He won't get it just for being colorblind. As for (a) I asked Claude. > Only one case is reasonably well documented, and it isn't a vice president. Bill Clinton is red-green colorblind: during the 1996 presidential debates, both Clinton and Bob Dole needed a modified cue-light system, since individual colored lights would have been hard for either of them to read, so a three-light arrangement was used instead — an anecdote that traces back to the Encyclopedia of Genetic Disorders and Birth Defects. Dole, of course, was Ford's running mate in 1976 and lost, so he never made it to the vice presidency. > Eisenhower is the other plausible case. His grandson David wrote that Ike confused browns and greens, sometimes asking for a brown suit when he meant green, and couldn't tell what color his golf balls were — someone had to write "DDE" on them. That's a family recollection rather than a diagnosis, but it's the kind of detail people don't invent. > Everything else you'll find online — Madison, Chester Arthur, Washington failing to distinguish crimson from scarlet, Lincoln calling lavender blue — comes from content-farm pages that cite nothing checkable, and I'd treat it as noise. Lincoln's documented eye problem was strabismus (eyes do not line up), not color vision. > > As for vice presidents: I can't find a single one with any credible claim. That's a bit surprising statistically — roughly 8% of men of Northern European descent are red-green deficient, and with fifty-odd vice presidents you'd expect several. The explanation is almost certainly that nobody was looking. Color blindness is invisible unless someone asks, the Ishihara test only dates to 1917, and a nineteenth-century politician had no occasion to disclose it. Clinton's case surfaced only because television lighting forced the issue. BILL: They left out Hubert Humphrey whose colorblindness was well known and well documented. It was why he was unable to serve in WW II. His not serving was used against him early in his career. LANCE: I asked Claude about that and here is what it said: > Good catch — that's the vice-presidential case I missed, and it's better documented than anything on the presidential side. Humphrey tried to enlist after Pearl Harbor and was turned down three times, twice by the Navy and once by the Army, on account of color blindness along with other physical problems. Biographical accounts add that he also had a double hernia and lung scarring, possibly from unpasteurized milk. > This one holds up because it left a paper trail: military induction physicals in the 1940s included Ishihara-style screening, so his condition was formally tested and recorded rather than inferred from someone's recollection about suits or golf balls. It also mattered politically — the failed enlistment dogged him, since he was a young man of draft age who spent the war teaching and working for the WPA, and opponents used it against him in his early Minneapolis campaigns. > > So the honest tally is one vice president (Humphrey), one president (Clinton), plus Eisenhower as a plausible unconfirmed case. Which, incidentally, undercuts the "nobody was looking" explanation I gave a moment ago — the real filter was that the condition surfaces only when an institution forces a test, and the military did that for exactly the cohort of politicians who came of age around the world wars. BILL: SO, why did it get it wrong? This is not something obscure which requires guesswork like speculating on whether Washington was colorblind (I can't tell scarlet from Crimson either). LANCE: Google AI did even worse. BILL-AI can solve Erdős problems, but it can't track down that Hubert Humphrey was colorblind. Why is that? LANCE- Claude was just too lazy to check over the military records of every vice-president. AI are people too! By gasarch

**Authors:** Lorenzo Beretta, Cameron Musco We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ of random matrices $A_i \in \mathbb R^{n_i \times m}$ whose columns are isotropic, independent and sub-Gaussian (e.g., Gaussian matrices). Khatri-Rao sketching matrices are widely applied in randomized algorithms for linear algebraic computation and data analysis, when the input data has tensor structure that allows for fast multiplication with $A_1\odot\cdots\odot A_d$. However, existing theory is not able to fully explain their performance in practice. In particular, despite significant attention, our best bounds for the important \emph{oblivious subspace embedding} property with Khatri-Rao matrices lag behind what is achievable with standard unstructured matrices. For embedding a $k$-dimensional subspace to $(1\pm ε)$ error, Bujanović et al. \cite{bujanovic2025subspace} prove that sketching dimension $m = O(k^{3/2}/ε^2)$ suffices in the special case of $d = 2$. Their dependence on $k$ is weaker than the tight bound of $O(k/ε^2)$ known for unstructured sub-Gaussian sketching matrices. In this work, we close this gap, showing that $m = \tilde O(k/ε^2)$ suffices for subspace embedding with a Khatri-Rao sketching matrix with any fixed order $d$. Our proof is simple, leveraging just two basic properties of the Khatri-Rao sketching distribution: 1) the columns of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ are independent and isotropic, and 2) each column of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ satisfies a weak Johnson-Lindenstrauss type moment property.

We show that a (stronger) version of random resolution has the feasible disjunction property. This is the first instance of a proof system not known to have feasible interpolation, which nevertheless has the feasible disjunction property.

**Authors:** Francesco Paolo Nerini, Francesco Bonchi, Arijit Khan, André Panisson Correlation Clustering (CC) is a natural formulation of clustering in combinatorial optimization, which uses a graph representation of the input and does not require a pre-specified number of clusters. Given $n$ objects and a pairwise similarity function, the goal is to cluster the objects so that similar objects are put in the same cluster and dissimilar objects are put in different clusters. Despite its versatility, existing CC algorithms suffer from significant scalability issues and are inherently transductive: i.e., the algorithm must be executed from scratch for any new problem instance. In this work, we bridge this gap by leveraging Graph Neural Networks (GNNs) to solve Inductive Correlation Clustering, a novel generalization of the CC problem designed to handle unseen graph instances. By learning to exploit common structural patterns and node features during training, our framework generalizes to new graphs drawn from the same distribution with minimal computational overhead with respect to standard algorithms. We demonstrate the effectiveness and scalability of our approach through extensive experiments. Our framework not only excels in the inductive setting, e.g., lowering the inference time up to $5$ order of magnitude, while maintaining an approximation ratio within $~10\%$ of the best baseline solution, but also achieves competitive results on standard (transductive) CC benchmarks. Finally, we showcase a practical application of our framework as a learnable pooling mechanism for graph classification. Our results indicate that our method serves as an efficient pooling layer, enhancing the ability of GNNs to capture hierarchical structural information in networks.

I more or less said what I was going to do in my tongue-in-cheek, cryptic post on Tuesday, but let me dive into the full details of how I’m planning on structuring this grad seminar. I’m going to log the course content here, which now lists a rough schedule for the class sessions. Taking inspiration from Matt Jones and Chris Wiggins, I’m going to do a weekly split between culture and engineering. Focusing on a particular application domain each week, we’ll spend one session discussing the _purpose_ of forecasts in that domain and the other on the _methods._ I arranged things into a thematic arc, starting with the weather—forecasting’s biggest success story—then moving to shakier ground in seismology and epidemiology, and ending with, well, millenarianism. As we move across timescales, our ability to predict nature dissipates: we can make accurate ten-day forecasts, but predicting large-scale climate disruptions is far more qualitative. We can predict immediate earthquake impacts at a distance once an earthquake has happened, but we can’t nail down precisely when a big one will happen. What we do with precise, short-term forecasts is completely different from what we do with imprecise long-term forecasts. Short-term forecasts dictate actions; long-term forecasts of discrete shocks inform risk management, preparedness, and rapid-response policies. I’m hoping that by the end of the semester I can better articulate what long-term forecasts of the end of the world do. We’ll look at forecasts in governance and how they influence and shape policy. I’m particularly interested in discussing the rise of cost-benefit analysis in US governance. Cost-benefit analysis puts a specific number on something completely unknowable, but is now mandatory for any bill or law to pass. I want to trace how we became so reliant on a particular set of methods for guessing costs and benefits. I’m also interested in how economists became convinced you could forecast “the economy.” This required inventing something called “the economy” that could be forecast in the first place. How our system of government got so tied to a particular style of economic prediction will occupy several weeks of the class. We’ll also get into why we want to predict “the public.” I want to examine how opinion polls went from a question of legibility to one of prediction. How did we get obsessed with using surveys to predict outcomes like elections? In parallel, we’ll look at the history of attempts to simulate the public. Simulation is nice because you don’t have to talk to people, right? We’ll look at the many misses over the history of human simulation in policy scenarios, and dig into the current obsessions with using LLMs to predict what people might do. Finally, we’ll get into the weird culture of competitive forecasting. We’ll engage with ideas from superforecasting and prediction markets and ask why people think these are useful information-processing systems. We’ll talk about punditry and how it’s not always interested in minimizing a Brier Score. We have to talk about the relationship between forecasts and gambling. And we’ll try to piece together why putting odds on outcomes makes people feel better about the future. For the methods, I did my topic matching so you could extract a logically ordered half-semester course on forecasting from those lectures alone. This is not a class on how to be a rational forecaster. I want to problematize those methods more than tell you how to implement them. You can ask your friend Claude if you need an honest, load-bearing implementation. Our methods survey starts with a refresher on my idiosyncratic views of machine learning as optimization-driven algorithmic pattern recognition. This will lead to a lot of discussion of the optimization problems themselves and why people like them. We’ll cover scoring rules, calibration, maximum likelihood, and utility maximization. We will discuss the role of models and look at probabilistic recurrence models, dynamical system models, differential equations, and other simulation-based tools. We’ll spend time on uncertainty quantification and how people come up with error bars (part of being a good forecaster is plausible deniability). Then we’ll look at offline and online optimization methods that let you fill in predictions based on your cost functions and modeling assumptions. I’m interested in highlighting the metrical determinism. The cost functions and models more or less tie your hands algorithmically, and most of the cleverness goes into how you evaluate. Hopefully this arc will feel coherent as we go. I’m not into predictions, so don’t get mad if the story changes as I go. I’ll blog through it, and then we can reflect on where we land at the end of the semester. Enrolled students (and those dedicated to following along at home) have an important first assignment: pick something to forecast. I don’t care what it is. Throughout the course, the goal is to learn the practical techniques by making predictions. Every week I’ll ask you to try to apply the tools to your problem. Or at least find how other people have applied those same tools to your problem. At the end of the semester, we’ll present our full findings and see how accurate we can be. Subscribe now By Ben Recht

**Authors:** Xiaoyu Chen, Kuikui Liu It is proved that, for every $δ\in (0,1)$, the Glauber dynamics for the uniform distribution on proper $q$-colorings is rapidly mixing when $q \geq (1+δ)Δ$ and the underlying graph has girth at least $5$ and maximum degree $Δ= Ω_δ(1)$. This result also extends to general multi-spin systems satisfying a $\textit{local spectral contraction}$ condition, including the anti-ferromagnetic Potts model with $q\geq (1+δ)(1-β)Δ$. These results are achieved by a new spectral local-to-global principle on graphs with girth at least five for general multi-spin systems, and a novel Fourier analysis for Glauber dynamics on a star. The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5.6 Sol Ultra.

I have just posted this report, which contains two previous reports, the counterexample to the dream xor lemma and the simple proof using majority, together with a new proof which appears to improve the parameters of all previous proofs of the xor lemma. Specifically, if a function has correlation epsilon with circuits of size S, the xor of two copies has correlation about epsilon square with circuits of size about S times epsilon square. By contrast, it seems to me that all previous proofs lost at least epsilon to the four in circuit size, and some also had a dependence on N. This loss arose from the need to estimate the final correlation, as is evident, for example, in Levin’s proof. The proof with the hard core set incurs this loss for similar reasons. The new proof in the report does not do this estimate. Instead, it uses an object which I call BMA for bounded mean amplifier. It is a function that, given iid variables with a small mean returns a variable whose mean is amplified. Majority is a decent BMA but doesn’t quite get to the square of the correlation. A randomized variant of majority does get you that. The function is very similar to what’s used, for example, in Levin’s proof and, I’m sure, in many other places, but as far as I can tell, the analysis is different. I also find it simpler. By Manu

There's a scene in Apollo 13 where Jim Lovell, played by Tom Hanks, asks Houston control to check his calculations, which they do using a slide rule. My father told me that when he was in college (1950s) that engineers measured their technical prowess in how many digits of accuracy they could get off a slide rule. The actual Apollo 13 incident took place in 1970. A year later Bowmar/Ali released the 901B, nicknamed the Bowmar Brain, for about $240. The following year came the HP-35, the first successful handheld scientific calculator that put slide rules out to pasture. A couple of years later I asked for a calculator for my birthday (the math nerd I was). I insisted on it having a memory button that could remember one number so I could do more complex calculations. The one I got even had a square root button! By the time I got to high school at the end of the decade, we all had handheld calculators. My AP chemistry teacher still insisted on teaching us how to use a slide rule. For fun, I decided to use my father's slide rule on a chemistry exam. That was a mistake for two reasons. 1. I did not have the "technical prowess" to get many digits of accuracy. So especially after a few calculations, my numbers were way off. The teacher took pity on me and gave me credit because I had the formulas right. 2. I spent too much time doing the calculations where everyone else just punched numbers into their calculator and didn't finish all the problems. Maybe with more experience I could have handled both issues better, but that was the last time I used the slide rule for any important calculations. School children still learned how to add and multiply, but I'm not sure my kids can do long division. Certainly I was the last generation to learn how to do square roots by hand. Is there an AI lesson in all this? We went from slide rules in mission control to calculators in high school in under a decade. No one suggests we go back to slide rules, and using a slide rule is now a lost art. Civilization survived. But there's a bigger story. The slide rule and calculator took care of the routine math, but the teacher graded me on my knowing the Chemistry. AI Can now do the chemistry. And what's left after that? By Lance Fortnow

**Authors:** Rolando D. Somma, Ronald de Wolf The guided Hamiltonian problem is the following: given access to the unitary $U=e^{i H}$ for some Hamiltonian $H$, and given access to a unitary that prepares a guiding state promised to have overlap at least $γ>0$ with the ground space of $H$, estimate the ground-state energy of $H$ within additive error $δ> 0$ and success probability at least $1-\varepsilon $, $\varepsilon>0$. How many applications of $U$ and its inverse $U^{-1}$ are necessary and sufficient? An upper bound $O(\log(1/\varepsilon)\log(1/γ)/γδ)$ was known, and was improved to $O(\log(1/\varepsilon)/γδ)$ very recently [JW26]. A matching lower bound was known whenever one of the three parameters $δ,γ,\varepsilon$ was held constant [MdW26]. In this paper we prove the joint lower bound $Ω(\log(1/\varepsilon)/γδ)$ with the tight $\varepsilon$-dependence provided the dimension of $H$ is at least $\log(1/\varepsilon)/γ^2$. Furthermore, we show that this same lower bound (with slightly larger dimension) holds for both the special case in which the ground state is guaranteed to be unique and $H$ has a gap of $δ$ between its first and second eigenvalue; and for ground-state preparation, where $δ$ denotes the spectral gap and $\varepsilon$ now is the approximation error. The lower bounds also apply when the Hamiltonian can be accessed via its block-encoding, and when fractional powers of $U$ are allowed, as in continuous-time Hamiltonian simulation. Lastly, improved upper bounds are known when $H$ is nonnegative and presented as a sum of squares; and our results imply the lower bound $Ω(\log(1/\varepsilon)/γ\sqrtδ)$ for this case.

Update: I haven’t joined Anthropic or taken leave from the university. That means I’ll be teaching as usual this fall, and you can look forward to your regular installment of live lecture blogs. Unlike past years, I’m assigned to my grad seminar in the fall, not the spring. Next semester I’ll be teaching our undergraduate probability class. That is assuming that the University is still here in the spring and hasn’t been put out of business by some new AI super tutor released by my friends across the bay. I mean, it would be the year 2027, and popular forecasts suggest AIs will be able to do everything taught in a CS degree by late 2026. By the end of the spring semester, those same prognosticators predict those AIs will go rogue, and we’ll find ourselves in the reality forecast by James Cameron in his 1984 prophecy, Terminator. Why should I bother dusting off my copy of Bertsekas and Tsitsiklis when the forecasts tell me I should work harder at the gym to prepare myself for robot enslavement in the salt mines? Actually, you know what would be a good way to prep for the robot apocalypse? Why don’t we spend a semester talking about forecasting and why people are obsessed with being certain about the future? Answering that question could potentially be a great way to shape a graduate course. We could spend a semester digging into not only _how_ people forecast, but _why_ they forecast. We could split our time in half, looking at the particularities of different domains where people make forecasts, and then looking into the tools they have settled on as mathematical culture. If you look at the places where forecasts are common, they all have different purposes. A local weather report is very different from a prediction of the end of the world. The former tells you if you should pack an umbrella on the way to work. The latter tells you whether you need to lobby your government to radically change its planned energy buildout. We all believe the evidence supporting forecasts of rain is far more certain and reliable than forecasts of nature’s end. But the costs of being wrong couldn’t be more different. What impact do these forecasts have? Why do we forecast the weather, and what hidden technology is needed to make these forecasts accurate? Why does Congress demand that we forecast future budgetary consequences of proposed laws, even though we know we can’t predict the actual structural shocks that will render those forecasts moot? Why are people so obsessed with predicting the rise of superintelligent robots? Is it more than a way to justify their greed and obsessive 996 work conditions? We’d learn a lot from a comparative study. I’d like to look at astronomy, meteorology, climate science, seismology, macroeconomics, government, epidemiology, public opinion research, and millenarianism to see what they have in common and how they differ. Forecasts let people externalize their beliefs about the likelihoods and consequences of various scenarios. Some forecasts are made for mundane planning. Some forecasts are made to literally gamble. Some forecasts communicate possible futures that others might not be considering. Some forecasts are made to be self-fulfilling, to manifest a change in the world the forecaster desires. Some are made to be self-negating, to convince people to act to avoid worst-case scenarios. I’m interested in understanding the threads that link all of these different purposes together. Though I’m much more interested in the why, the how has some fun tidbits too. The how is about creating certainty about the future by quantifying it. Uncertainty becomes certain once we turn it into an interval, right? In talking about the how-of-forecasting, I could tie together a lot of loose ends in methods that I’ve blogged about over the years. We might determine the conditions under which pattern recognition (aka machine learning aka AI) becomes a _forecast._ We could look at how forecasts are evaluated post-hoc with scoring rules and calibration tests and why people think those are good evaluations. We could look at methods for cost-benefit analysis and uncertainty quantification, and how people justify their modeling assumptions to make decisions. We could learn about tools from dynamical systems that move from simple moving averages to complex simulations. We could examine how statistical tools can be applied to extrapolate from the present to the future. And we could see how these sorts of metrics and models tie your hands algorithmically into unsurprising answers. This sounds like a fun class to me. I predict I’ll teach this class this fall and live blog it here, starting this Thursday. If you’re a Berkeley graduate student whose research depends on forecasts, email me if you’d like to join the course.[footnote: If you do email, please send me a description of your background and why you’re interested.] If you’re not local, I’ll post a syllabus and webpage this week, and I’ll do my best to keep all of the material public. I predict it will be fun. Subscribe now By Ben Recht

**Authors:** Bowen Liu, Yizhou Wang, Lingqian Meng Triangle-based measures, commonly referred to as badness functions, are widely employed to quantify the extent to which a distance matrix deviates from an ideal geometric configuration. Different formulations of these functions may capture distinct facets of local non-uniformity, and their behavior is often influenced by the underlying distance metric chosen for evaluation. In practical settings, although a canonical badness function may be conceptually preferred, factors such as computational cost, algorithmic constraints, or data-specific characteristics frequently necessitate the adoption of modified versions-for instance, approximate forms or alternatives defined under different distance metrics. This gives rise to a central question: to what degree do these variants retain the structural consistency properties of their original counterparts? To address this issue, we develop a systematic correlation-based framework for evaluating structural consistency. As an illustrative instantiation of this framework, we compute badness sequences from a set of representative distance matrices alongside randomly generated triangle configurations, which are designed to cover variants that may arise under diverse practical scenarios. We then assess pairwise similarities among these sequences using four correlation coefficients. The experimental outcomes indicate that certain badness variants exhibit a notably high degree of structural consistency, whereas others reveal complementary behavioral patterns; moreover, the choice of distance metric exerts a considerable influence on the observed trends. These findings offer practical insights for the informed selection of distance metrics and triangle badness function variants in tasks including geometric reconstruction, triangulation, and structural analysis of pairwise distance data.

For a very long time, my favorite activity was to sit and think about mathematical questions. Staring at a blank sheet of paper, trying to grasp in my mind abstract concepts, bouncing ideas off colleagues and students. There is nothing quite like the feeling that you are exploring the unknown by only using your mind. Mathematicians have different styles and motivations for doing math. For some, it is about the challenge of solving hard problems. Others might have some application in mind, or a question they feel compelled to find the answer to. But I believe that none would stick with this profession if they did not find the process of doing mathematics satisfying. We cannot deny that this process is going through a profound change with AI. Some mathematicians have been meeting this change with excitement, while others with grief. I share both sentiments. When considering the future of math (and science at large), it is worth reflecting on its past. For centuries, mathematicians and scientists typically worked under the patronage of nobles and royals: Archimedes advised King Hiero II, al-Khwarizmi was supported by the Abbasid caliphs, and Galileo by the Medicis, while medieval universities remained largely teaching institutions. It was only after the emergence of the royal academies and research universities from the seventeenth century onwards that scientists were paid by the state for pure research. Beyond patrons and academies, scientists have supported themselves in varied ways: military engineering (Archimedes), day jobs in law (Fermat), personal wealth (Darwin), the Royal Mint (Newton), tax farming (Lavoisier), and of course, examining patents. But if there is one constant that has held true from Archimedes to our time, it is the importance of a scientific community. Scientific communication evolved from personal correspondence and networks of letters, through academies, to modern journals. But throughout this evolution, scientists valued the community of their peers. What these communities focused on has changed over time. These days proving theorems is considered the prized activity in mathematics, but throughout much of history, the focus was on calculations or solving problems, rather than rigor. In the sixteenth century, Italian mathematicians earned jobs through equation-solving duels, which caused them to keep formulas such as the solution to the cubic equation secret. Euclid and al-Khwarizmi are known to this day not because of their new discoveries as much as for organizing known results. Today, there are many self-selected and self-organizing scientific communities, which set up their own publication venues, norms, and processes. They are by and large self-governing, and each scientist chooses in which of these communities to participate. The university, which typically pays the scientist’s salary, largely defers to the judgment of their community as to the value of their work. Together with the mechanism of tenure, this leads to a remarkable lack of direct employer oversight of scientists’ output. Many discussions of science’s culture, including peer review, the publication process, and tenure, focus on their various defects and problematic cases. Yet science has been immensely successful. To use AI terminology, the last “pretrain” humanity got was hundreds of thousands of years ago with Homo sapiens (internal codename: homo-erectus-v5-pro-max). And yet we have managed to advance so much on that basis. I am also surprised by how we managed to keep science legible. Theories like general relativity and quantum mechanics are the results of hundreds, if not thousands, of years of work by humanity’s most brilliant scientists and mathematicians. And yet we are able to routinely teach them to first-year undergraduates. **Impact of AI on Math** At this point, it is undeniable that AI can make significant contributions to solving mathematical problems. Solving open problems has been a prized activity in mathematics for a long time. One reason is that it is the easiest way to verify that one has done something that is both novel and interesting. And if we’re lucky and the problem was chosen well, the solution will not be a highly specific trick, but a more general insight or technique that can be used broadly. However, this does not mean that solving open problems is the only or even the most important contribution, and thankfully the “inefficiency” of the mechanisms for evaluating researchers allows many other types of contributions to still flourish. For the same reason as above, solving open problems with AI is a straightforward way to dispel the skepticism of people who believe it cannot do research-level mathematics. But once we go beyond such skepticism, it is not clear that solving open problems should be the only or even the main use of AI. If you hope or believe AI is inherently incapable of posing problems, writing exposition, or building theories, then you are bound to be disappointed. What does this mean for mathematics and the role of human mathematicians? There have been radically different responses to this. On one extreme, Weinreich called for a “total opposition to artificial mathematics,” and in particular for mathematics departments to “[establish] anti-AI policies for student work, [reserve] hire lines for mathematicians who eschew AI, [and value] AI-free papers more highly in tenure promotion.” (It is unclear if, under his proposal, “AI-free” papers would be allowed to cite results that did use AI.) On the other hand, Tao said that AI will change how we do math, and that “we do have to somehow let go of conventional assumptions of what intellect is.” Weinreich’s point of view resonates with the view of mathematics as an art, which is about human expression. On the other hand, many of the strongest mathematicians in history, including Archimedes, Newton, Euler, Gauss, and von Neumann, had a deep interest in its applications. If you care about mathematics’ applications, eschewing AI-enabled discoveries is not an option. Hence, I do not believe that an AI-free vision of mathematics, of the type promoted by Weinreich, is a viable future for it as an academic field. Recreational and competitive mathematics will have different standards, but the lessons of chess (which is actually thriving!) suggest that a complete rejection of AI is unwise even in these domains. This does not mean that we will have no need for human mathematicians. As mentioned above, the modes of scholarship and funding models for mathematicians have changed over the years, and can change again. In particular, education has long been one of the primary missions and occupations of mathematicians, and it will be as important as ever. If we want (as I do) humans to keep control of their destiny, an educated society will be only more important as AI systems become more powerful. I believe that human curiosity and legibility will also continue to play a crucial role in science and mathematics. One lesson from history is that it’s extremely hard to predict which directions will have practical applications, and the answers to questions pursued out of pure intellectual curiosity can have great practical impact. In 1940, the mathematician G. H. Hardy wrote that “Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems very unlikely that anyone will do so for many years.” Needless to say, since then people have found many useful, and even warlike applications for these fields, and in particular GPS and public-key cryptography. Given the track record of curiosity-based science, it would not be wise to eliminate humans from this process and replace them with “artificial scholarly communities” any time soon. Even if it were possible to get the same value, given the unpredictability and time lag of basic science applications, we will not be able to verify this in the near future. Also—and here I am biased—curiosity-based science is good in itself. Number theory is beautiful and would have been beautiful even without cryptography. Could humans even keep up with understanding AI advances? I believe the answer is yes. Humans have always developed increasingly powerful abstractions to handle complexity. This is the only way we can use brains much like those of our cave-dwelling ancestors to grasp quantum mechanics, write complex software, manage companies, and organize societies many orders of magnitude larger than they did. Abstraction is what allowed us to compress thousands of years of scientific progress into an undergraduate program, and will allow AI to compress its findings and make them legible to us. It may well be that such levels of abstraction will mean that we do not always follow all steps of a proof, just like we do not verify today that a program correctly multiplied two large numbers. AI will impact much more than science and math. Mathematicians are people too, and they face many greater risks (as well as potential benefits) from AI than those related to its impact on their profession. If AI leads (as I very much hope) to a flourishing human society, then it would be one that values education, curiosity and creativity. We might not explore math using a blank sheet of paper in the same way as I did as a graduate student, but we would still be making and sharing new discoveries. Emma Goldman is often (mis)quoted as saying “If I can’t dance, I don’t want to be part of your revolution.” Similarly, I don’t want to be part of an AI revolution that has no room for human scientists, mathematicians, or artists. By Boaz Barak

**Authors:** Deeparnab Chakrabarty, Cooper LaPorte, C. Seshadhri We study the problem of estimating the number of hyperedges in an arbitrary $n$-vertex hypergraph using sublinear in $n$ queries. Note that the number of hyperedges, $m$, can be exponential in $n$. For $k$-uniform hypergraphs, estimating $m$ is equivalent to estimating the average vertex degree, a problem studied in Barhum's Master's thesis (Weizmann Inst., 2007) under the standard access model of sampling random vertices, querying vertex degrees, and accessing incident hyperedges. Barhum's techniques do not extend to arbitrary hypergraphs, and simple lower-bound examples show that the standard access model cannot yield strongly sublinear algorithms when hyperedges have unbounded size. To obtain non-trivial sublinear bounds, we consider a natural generalization of the access model called the \emph{dual access model}, which allows sampling (labels of) random hyperedges, querying edge sizes, and accessing vertices in a hyperedge. In this model, we give a randomized algorithm that returns a $(1+\varepsilon)$-approximation to $m$ with high probability, making $O(\varepsilon^{-2}\sqrt{n} + \sqrt{n}\log n)$ queries. Complementing our algorithm, we prove a nearly matching lower bound showing that $Ω(\sqrt{n})$ queries are necessary for any algorithm that obtains a constant factor approximation to $m$.

MATS Winter 2027 is a fully funded, 12-week AI safety research and field-building fellowship in Berkeley and London, with seven tracks, mentorship from researchers at Anthropic, Google DeepMind, OpenAI and more, a $6,400/month stipend, up to $16,000/month for technical participants, and housing, meals, travel and office space covered. Website: https://www.matsprogram.org/apply?utm_source=cstheory-jobs&utm_medium=job-board&utm_campaign=w27 Email: applications@matsprogram.org By shacharlovett

We prove a common generalization of two structure theorems: the dimension-free decomposition theorem for idempotent Schur multipliers and the idempotent theorem in harmonic analysis. Roughly speaking, our result shows that an invariant integer-valued kernel with Hilbert-space factorization norm $\gamma$ admits a signed decomposition into at most $2^{O(\gamma^4)}$ elementary pieces. In the matrix setting these pieces are blocky matrices, while in the group setting they are indicators of cosets. In the locally compact abelian setting this quantitatively strengthens the theorem of Green and Sanders, while in the non-abelian setting it gives a quantitative strengthening of Host's idempotent theorem and, for finite groups, of Sanders's quantitative result. It also improves the exponent in the dimension-free matrix decomposition from $\gamma^6$ to $\gamma^4$.

We study low-degree testing for group-valued functions over a Boolean slice. Specifically given a degree parameter $d$ and oracle access to a function $f:\{0,1\}^n_{n/2} \to G$ where $\{0,1\}^n_k$ denotes the set of vectors in $\{0,1\}^n$ of Hamming weight $k$ and $G$ is an Abelian group (not necessarily finite), the low-degree testing problem asks us to distinguish the case where $f$ is a polynomial of degree at most $d$ (with coefficients from $G$) or is $\varepsilon$-far from the set of all such polynomials. Classical works in this area considered functions with domain $\mathbb{F}_q^n$ and range $\mathbb{F}_q$. More recent works have considered the setting where the domain is the Boolean cube [Bafna, Srinivasan, Sudan (Random Structures and Algorithms 2020), Amireddy, Srinivasan, Sudan (RANDOM 2023)], or when the domain is the slice (i.e., $\{0,1\}^n_{k}$) and the range is $\mathbb{F}_2$ [David, Dinur, Goldenberg, Kindler and Shinkar (SIAM Journal on Computing 2017), Kalai, Lifshitz, Minzer and Ziegler (FOCS 2024)]. Each of the changes introduces new challenges in designing and analyzing low-degree tests and this happens again in our setting with domain being a slice and range is general. Indeed the previous methods fail even when the domain is a Boolean slice and the range is $\mathbb{F}_3$. Our main theorem gives a test that makes $O_d(1)$ (specifically $\exp(d^{O(1)})$) queries to $f$ and accepts degree-$d$ functions while rejecting functions that are $\varepsilon$-far with probability $\Omega(\varepsilon)$. The central proof idea is to reduce this low-degree testing problem to the problem of low-degree testing on the cube. Specifically we show how to randomly embed the $n/2$-dimensional cube $\{0,1\}^{n/2}$ in the $n$-dimensional slice while nearly preserving the proximity of $f$ to the space of degree-$d$ polynomials on this cube (with high probability). While the embedding is simple and natural, the analysis involves a careful induction (seen in some prior works on low-degree testing) with a novel use of a basis of degree-$d$ polynomials on slices (from a work of Anstee, Rónyai and Sali (Graphs and Combinatorics 2002)). Such a basis of functions is non-trivial and has several nice combinatorial and algebraic closure properties. We show how these properties are useful by using them to analyze our low-degree tests.

Thanks to everyone for the constructive feedback on Monday’s microconferences post. I wanted to take a beat to engage with two salient themes in the replies: runbooks and homophily. I’ll start with runbooks today, and tackle homophily next week. No two microconferences are alike, and we shouldn’t impose hard-and-fast rules on their structure. One of the fun things about small conferences is you can tailor them to particular goals and dreams. And there are so many ways to do this well. However, I think it will be useful to compile a _runbook_ of agreements, strategies, and rules that you can use to help modularly assemble your ideal microconference. Today, I’ll run down a bunch of disorganized examples. You tell me your favorite ideas in the comments. I’ll assemble these more coherently into a document that I’ll widely share. We can learn a lot from existing institutions, and many people spoke fondly of places I should have shouted out in the first post, e.g., BIRS, Oberwolfach, Dagstuhl.1 I also adore the quirkiness of the American Institute of Mathematics, which has a very particular and very fun way to run a microconference, disallowing canned and prepared talks.2 I am inspired by unconferences that bring together dozens of people to spontaneously generate many microconferences. All of their best practices should be part of the runbook. I’ve found an easy model for microconferences is a bundle of short, 5-10 minute talks with adjoined group discussions led by the speakers. The past four microconferences I’ve attended have run this way. Short talks are fun because they force people to think hard about messaging and concision, and lead to a lot of interesting back-and-forth with the right serendipitous assignments. I was somewhat randomly assigned to a panel with Dan Wang and Dan Davies on cybernetics, and it was probably the most fun and rewarding 90 minutes I’ve ever had at a conference. That single brief session reshaped the narrative arc of _The Irrational Decision_. Johan Ugander raised several good ideas in his comment. About archiving and proceedings, he wrote: “The non-proceedings nature of workshops is key to drawing in a diverse set of people.” I agree. We should think broadly about what should count as “proceedings” or “archiving.” I liked Johan’s suggestion of simply inviting participants to submit to a special issue. You could consider this series of blogs ([1], [2], [3], [4]) and this youtube video the “proceedings” of the Cultural AI workshop organized by Leif Weatherby and Tyler Shoemaker this spring. I just want to suggest that we explore creative ways to archive, evaluate, and credit microconferences in the broader academic ecosystem. I’d add to my list of core microconference values that “archiving should encourage, not discourage dissemination and broader engagement.” As Johan wrote: > “ACM EC has a forward-to-journal mechanism, which gets Computer Science, Operations Research, and Economics folks together for a coherent conference but lets them still go harvest their respective tokens. The EC reviews get passed to the journal. And EC also organizes a ‘Highlights beyond EC’ session, which lets people request to present work recently/already published “elsewhere” but relevant to the community. Both of these mechanisms help keep the ‘conference’ and ‘publication’ goals separate.” Endorsed! Anna Gilbert raised the idea of “bump sessions”: > “The Dagstuhl and Oberwolfach type conferences in TCS used to also have “bump sessions” (maybe they were called rump!) where people proposed open problems, noodled over difficulties, etc. Sometimes these micro workshops even “published” open problems from these bump sessions. They were quite useful and engaging!” Anna also raised one of my favorite ideas, which I’m looking for an opportunity to try: > “Another model I’d like to advocate for is to have members of a PC present the papers they selected (see my rant about paper reviewing and big conferences) and then an audience discussion. Like what the statisticians do but in person and with a publication resulting for the authors.” I call this the “Not-so-royal Society.” The conference or session would center on a single paper written before the conference is organized. The organizers invite discussants to compose a response/review of this paper. The meeting could start with a presentation of the paper by the author. Many papers have multiple authors, and the presentation can be as collaborative as the writing. The author’s presentation is followed by commentary from the discussants. The remainder of the session is a conversation that invites commentary from the rest of the workshop participants. After the workshop, the author can revise the paper, the discussants can write formal commentaries, and the author can write a rejoinder if they choose. All of this writing could be posted to arXiv as refereed conference proceedings and linked from the microconference proceedings webpage. This format might be the most legible in the current regime of bean counting and could perhaps serve as a “gentle introduction” to the microconference format. If you have ideas of papers we should use as testbeds for this format, reach out! I’d love to help set something like this up. Finally, I want to give a shout out to Henry Farrell and Cosma Shalizi, who have been experimenting with clever microconference formats for years. Cosma wrote up the idea of having people present others’ work. Everyone writes a talk or slides, but then the presentation is assigned to someone else. They found that doing this at the start of the workshop creates a shared comprehension, allowing for a lot of multidisciplinary crosstalk. And they also found that speakers had to work extra hard to make their points comprehensible. This is by no means an exhaustive list of ideas. And it shouldn’t be. My next major to-do is posting a working document of this runbook somewhere. But before I jump in and commit myself to a design, I’m looking for pointers to good online institutional memories that allow for edits and revisions. I love the minimalism of PMLR and bactra.org, but I also want to host a living mission statement and runbook on the same site. Let me know what platforms I should look into. Tech tips would be most appreciated! Subscribe now 1 You can get a sense of the skew of my readership by the institutions they love. 2 I also love that it used to be in the backrooms of a Fry’s Electronics store By Ben Recht

**Authors:** Saverio Giallorenzo, Jacopo Mauro, Gianluigi Zavattaro Kubernetes is the de-facto platform for container orchestration. Its scheduler combines resource capacities with label-based affinity and anti-affinity rules, and the interaction of these features can make the eventual placement of a pod. In this paper, we study the pod-deployability problem: given an initial cluster, a pod type, and a designated node, does some legal sequence of pod deployments and deletions cover the target pair? We give three complexity results. First, when dynamic constraints contain no affinity (anti-affinity is allowed), pod-deployability is decidable in polynomial time. Second, required affinity together with required anti-affinity makes the problem PSPACE-complete. Third, required affinity alone is already enough for PSPACE-completeness on a single node with one scalar capacity. The lower bounds encode, respectively, 1-safe Petri-net coverability and bounded black pebbling. These results isolate two independent sources of state-space complexity in Kubernetes scheduling: logical exclusion and resource-bounded prerequisite management.

A fully-funded PhD position and MS positions with RA/TA support are available under the supervision of Prof. Prantar Ghosh at Tennessee Tech University starting Jan 2027 (Spring 2027 semester). Research will focus broadly on graph algorithms. A good mathematical background and prior experience in Theoretical CS is required. Please email CV and a brief description of background to the email below. Website: https://sites.google.com/view/prantarg/home Email: pghosh@tntech.edu By shacharlovett

**Authors:** Dmitry V. Alexandrov We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a triplet-based combinatorial framework for reasoning about compatible paths through layered triplet structures, called Compact Triplets Structures (CTS), and their intersection via Romanov's Effective Procedure, which we refer to as Simple Vertex Intersection (SVI). Originally motivated by Boolean satisfiability, TLS constitutes a self-contained mathematical theory whose formal properties had not been previously established. We formalise the core of TLS in Rocq, including Compact Triplets Formulas (CTF), CTS, hyperstructures, clearing, and SVI. For the well-formed sliding-window fragment we verify a clause-by-clause CNF-to-CTF translation, the clearing procedure, and aligned intersection, and we prove explicit polynomial-time bounds for the filter stages. Our main contribution is a precise correctness boundary: the existence of a joint satisfying set implies non-emptiness of SVI, but the converse does not hold in general; for aligned structures we recover a complete bi-implication, extended to systems of structures. We also formalise soundness of grouped-window translation and exhibit a formal counterexample to its completeness. We introduce VFR, an extracted OCaml prototype that provides a verified decision procedure for the sliding-window fragment and a sound one-sided filter for general 3-CNF, with a Python runtime and reproducible Docker packaging. Benchmarks on random and structured instances confirm the predicted behaviour, and the complete toolchain is available as a curated Zenodo artifact. The Rocq development comprises more than 23,000 lines of code across seventeen files, with 427 proved lemmas and theorems and zero admitted goals.

A bunch of new video content came out over the past couple of months, summarized here in case of interest: First Principles podcast series, featuring interviews with Barbara Liskov, Leslie Lamport, Alvin Roth, Paul Milgrom, Ron Rivest, Shafi Goldwasser, and Noam Nisan. Ergo lecture series on Computation and Its Limits: Series intro; Is There Anything Computers Can’t Do?; How Algorithms Outsmart Complexity; Easy Problems, Hard Problems; Two Worlds We Might Live In; AI, Quantum Computing, and Beyond. These lectures, aimed at a general audience, focus mostly on the developments in computability and complexity theory from the 1930s through the 1970s. Videos from the 2026 Summer School on the Theory & Practice of Blockchain Consensus, featuring talks by Ittai Abraham (a16z crypto), Roger Wattenhofer (ETH Zurich/Anza), Dongning Guo (Northwestern University), Maria Apostolaki (Princeton University), Andrew Lewis-Pye (Commonware/London School of Economics), Sasha Spiegelman (Aptos), Francesco d’Amato (Ethereum Foundation), Yann Vonlanthen (Ethereum Foundation), Sourav Das (Category Labs), Guru Vamsi Policharla (Commonware), Alberto Sonnino (Mysten Labs), Patrick O’Grady (Commonware), Joachim Neu (a16z crypto), and Kartik Nayak (Duke University). By timroughgarden

Part of the reason I brought up microconferences on Monday is that I was attending a great one this week on public feedback for AI, organized by Jessica Dai here at Berkeley. In the spirit of creating an archival footprint, Jess and I will have a lot to say about the workshop over the next few days. I’ll kick things off by describing what I talked about. I opened with a provocation about the trap that policy-minded computer scientists and social scientists so easily fall into. Longtime argmin readers will recognize the pattern. If we want to raise the concerns of a public, we need to convincingly present “evidence” supporting those concerns to policymakers. “Evidence” means cold, hard quantifiable facts that are easy to explain to policymakers, not just anecdotes of harm. I’m sympathetic. If you want to advance an agenda you care about in a complex world, you have to make it simple for those in power to understand. Too many things are happening at once, there’s far too much nuance and ambiguity, policymakers can only keep so many in their heads, and only so many laws can be drafted and passed at any given time. It makes sense then that people concerned with technocratic solutions spend so much of their time designing _architectures of legibility_. They focus on the right ways to summarize data, weigh competing interests, and write compelling reports. They build computational frameworks to compile complicated, singular events into useful statistical summaries. A nice chart is worth a thousand testimonies. These architectures of legibility are what enable the inevitable quantification trap. To make things legible to decision makers, we quantify them. Since we agreed on transparent procedures, the quantified must be objective. Numbers are always objective, right? Objectivity buys analyses authority. And expert authority then becomes a tool of power. The quantification trap has been a pervasive and mimetic signature of the information age. And it has become progressively invisible as computation has miniaturized and sublimated into ubiquity. Every moment of our lives is now surveilled and quantified, ready to be summarized into new systems of control. I am not against quantification of social systems. I just want to consistently raise awareness of its hegemony. There are clear benefits to quantification. It buys us a level of intersubjectivity, as anyone can trace the path from evidence to summary statistic. This shared, standardized language lets us collaboratively govern complex societies. On the other hand, the quantification trap removes discretion, forcing us to abide by rigid rules. Quantification erases individuals in its bucketing and summarization. And quantification enables structural violence, forcing citizens to constantly make themselves legible to those with power to avoid being punished. The question I always get from technocrats after presenting these critiques of quantification and architectures of legibility is “What else could you do?” My answer is to think about an alternative type of social architecture, _architectures of participation._ Tim O’Reilly coined this term in the early aughts to describe what makes participatory culture work on the internet. Why do some software systems take off as collaborative efforts? Tim noted that many software and communication systems are _designed_ for contribution. Open source software has countless success stories. We also have the legacy of internet communication, message boards, and the World Wide Web. We have the astounding body of knowledge that is Wikipedia. And we have a powerful public challenge to copyright that was Napster. This last example highlights that not every architecture of participation brings unambiguous good to every stakeholder. The lens of participation helps us think about what elevates voices and values directly through individual actions. Architecture of participation subsumes many different perspectives on the design of social systems. It includes standard economic mechanism design, the rules of games we play, and the decision-making agreements established by anarchist groups. What distinguishes these systems from architectures of legibility is they aim to cultivate broad expertise from a broad group of people. They are ugly and organic by nature. They are structured _agreements_ for interaction and discussion. They do not suppose a benevolent set of experts at the top will make decisions based on what they see. Mods often write explicit rules, but community patterns are encouraged to be emergent and reflexive. They let the community work together, in small spaces and large ones. Architectures of participation focus on designing flexible agreements for flexible ends. They accept that there is no clear metric to maximize. Sure, you can build legibility dashboards to make sure your system isn’t crashing. Again, I’m not against quantification. However, the focus of participatory design is not quantification, but broadening engagement and diversifying served ends. So what does this have to do with _AI_ and public feedback? It is very weird that our contemporary AI took all of human knowledge, made something very interesting and very powerful, and then gave all of the rewards to a small group of people who whine all the time about how they have no power. This is a perversion of participation. Built on the labor and love of individuals, generative AI technology concentrated power. And then those in power convinced themselves they are powerless. San Francisco wants to abdicate all human agency and reduce us to making ourselves legible to an artificial bureaucratic god. On the other hand, the data center protests are inspirational. Here you have a lot of people who are really upset for a complicated set of reasons about AI. It’s hard to say why they are so mad, and why this issue is so salient, but it’s undeniable that they are driving policy conversations. Their protests and organization have made them not legible, but unignorable. AI doesn’t have to be exclusionary. We could build an AI that’s a public good. One that invites participation. One that involves known training data, participatory training data. We now know that if you train next-token predictors on collective intelligence, you end up with a quirky piece of software that speaks in natural language, solves impossible math problems, and does all of your coding. We can’t unsee that. But we don’t have to let a small group of whiny, weird people own it. We can use this insight to build a public infrastructure for collective, participatory intelligence. Subscribe now By Ben Recht

In the past, new PhD students would ask how they could succeed when they had to compete with the likes of say, Richard Karp or Avi Wigderson. I would say Karp and Wigderson have limited bandwidth and you can work on problems they don't work on, or think deeper about a problem than Karp or Wigderson has time to. Now we get the same question but with names like Claude and ChatGPT and it's hard to make the same bandwidth argument. What do we tell them as we get closer to Math AGI? What even is Math AGI? It's not that every math problem gets solved. I don't expect P vs NP to be solved anytime soon. It would require a completely new approach, and AI doesn't (yet) think outside the box, though it has a very large box. Math AGI means that with rare exceptions, if AI can't solve a math problem then no human could either. If you need a proof, you'd have to pay for more cycles, or wait for the next new and improved model. Like the Turing test, we'll only truly realize we've reached Math AGI once we've gone well past it. We haven't reached Math AGI yet and we may never fully get there. We have entered the world of Centaur Math. Mathematicians can still prove theorems AI can't, AI can prove some theorems mathematicians haven't yet proven, but the real strength comes with mathematicians and AI working together. Working with AI today is like having a pretty good PhD student, who has a huge broad base knowledge of mathematics, is a whiz at coding, but still needs direction, encouragement and verification. Chess had a short centaur moment when humans and AI working together could beat the best human players and AI programs. Now, any human would play worse not following what AI says. Nevertheless, we still enjoy watching two sub-AI humans play chess against each other. I doubt the same would hold for sub-AI mathematicians. So what do we tell the students? If you love math, do math. Embrace AI, use it to go further, not as a crutch. Challenge yourself and remain agile so you can find success whatever the future might hand us. And remember, math is not ultimately about the theorems we prove but how we understand the principles behind them, and that's a human endeavor not a machine one. By Lance Fortnow

The quantum analogue of the PCP theorem for QMA remains wide open. A central obstacle is the local indistinguishability of quantum codes: every sufficiently small view of an encoded witness is independent of the witness, seemingly preventing a local verifier from distinguishing YES from NO instances. One approach to this apparent paradox in the work of Anshu, Breuckmann and Nguyen, is to encode the witness in a quantum code and compute on it fault-tolerantly, successively reducing the encoding length until the answer is revealed. We study a classical relaxation of this approach based on the equivalent view of quantum codes as private randomized encodings from multiparty computation. Specifically, we ask whether one can construct circuits that compute on a private encoding of an NP witness, such that every sufficiently small fractional view of the honest computation transcript is independent of the witness (i.e. has quantum distance) and the computation remains correct despite a small fraction of adversarial bit-flip or X-errors in every layer. We construct such circuits and use the classical Cook--Levin theorem to obtain private PCPs for NP: the prescribed PCP encoding is randomized, and for each instance every view below the privacy threshold has the same distribution for all assignments, whether satisfying or not. For Circuit-SAT instances of size $n$, we get $\sqrt{n}$-query private PCPs of size $O(n\log n)$ over alphabet size $\mathrm{poly}(n)$, fractional privacy $\Omega(1/\log n)$ and constant soundness gap. Furthermore, conditional on a high-dimensional product expansion conjecture for Reed-Solomon codes, our PCPs have length $n^{1+o(1)}$, use $n^{o(1)}$ queries, and have fractional privacy and soundness gap $n^{-o(1)}$. Our construction is based on a new family of small-alphabet quantum codes which have near-linear rate, sparse $X$-checks that enable local testability for $X$-errors, support for multiplication (or transversal CCZ gates on the full logical space) and near-linear quantum distance using product expansion. The codes are obtained using tensor products of Reed--Solomon codes, and our key innovation is to choose the evaluation domains as multiplicative subgroups of pairwise coprime orders of $\mathbb{F}_q^\star$. A proof obtained by ChatGPT 5.6 Sol establishes constant 2-dimensional product expansion whenever both rates are bounded away from one, crossing the tight sum-of-rates-below-one barrier in the product expansion theorem of Polishchuk and Spielman. We conjecture the analogous statement in higher dimensions.

**Authors:** Paweł Rzążewski We study the parameterized complexity of $k$-Coloring in $H$-free graphs, when $H$ is a linear forest (i.e., a disjoint union of paths) as an induced subgraph. We show two hardness results: * $k$-Coloring is W[1]-hard in $2P_2$-free graphs when parameterized by $k$. * $3$-Coloring is W[1]-hard in $P_t$-free graphs when parameterized by $t$. Moreover, assuming the ETH, these problems admit no algorithms solving $n$-vertex instances in time $f(k) \cdot n^{o(k)}$ and $f(t) \cdot n^{o(t/\log t)}$, respectively, for any computable function $f$. The first result resolves in a strong form a long-standing open problem, originally posed by Hoàng, Kamiński, Lozin, Sawada, and Shu [Algorithmica, 2010]. The second result answers a question of Golovach, Johnson, Paulusma, and Song [Journal of Graph Theory, 2017].

As part of Mind-IL.- Israel’s Science and Academia Week (which also is around the Israeli election) there would be a special conference in honor of Michael Rabin with some fantastic lecturers. By Boaz Barak

For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \\{0,1,2\\}^n$. We prove a counting lemma for somewhat restricted $3$-APs in dense sets in $\mathbb{F}_p^n$. More precisely, we prove that for all $\alpha>0$, there exists $\beta>0$, such that for sufficiently large $n$, if a set $A\subseteq \mathbb{F}_p^n$ has density at least $\alpha$, then it contains at least $\beta$ fraction of all somewhat restricted $3$-APs. Our proof builds on recently developed machinery from [Bhangale, Khot, Minzer, 2026]. Our main new ingredient is an arithmetic regularity lemma for patterns such as somewhat restricted 3-APs. This result is in the spirit of arithmetic regularity lemmas from the theory of Gowers uniformity norms [Green, Tao, 2010] and may be of independent interest.