Theory of Computing Report

I wrote the post below last week. That was a quaint and quiet time. Last night OpenAI released a treasure trove of 722 manuscripts solving 372 major open problems in mathematics including from theoretical computer science:

• A proof of the unique games conjecture (formalized in Lean)
• A full derandomization of randomized log space
• Matrix multiplication in \(n^{2.25+\epsilon}\) time (formalized in Lean)

Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit and Avishay Tal posted a paper giving an oracle where \(\mathrm{BQP}\) is not in \(\mathrm{IP}\) (interactive proofs). Now \(\mathrm{BQP}\) is in \(\mathrm{IP}\) since \(\mathrm{BQP}\subseteq\mathrm{PSPACE}=\mathrm{IP}\), but the \(\mathrm{IP}=\mathrm{PSPACE}\) proof doesn't relativize and Bouland et al. show you can even get an oracle that puts \(\mathrm{BQP}\) out of \(\mathrm{IP}\).

The paper also states "Together with recent work due to Scott Aaronson, Anand Natarajan, Avishay Tal, and Ági Villányi, our work also gives the first oracle separation between IP and MIP, answering a question dating back to Fortnow's thesis." \(\mathrm{MIP}\) is the set of languages with multi-prover interactive proofs.

When I saw this paper, I pulled my PhD thesis off the shelf and indeed on page 40 I wrote "What is the relation between MIP and IP? Is there, for instance, an oracle separating the two classes".

When I wrote the thesis in 1989 we didn't know yet that \(\mathrm{IP}=\mathrm{PSPACE}\) and \(\mathrm{MIP}=\mathrm{NEXP}\) so we really didn't have any idea whether multiple provers actually gave you more power than one prover. When László Babai, Carsten Lund and I proved \(\mathrm{MIP}=\mathrm{NEXP}\) a year later, we had strong evidence that \(\mathrm{IP}\neq\mathrm{MIP}\) since we believe that \(\mathrm{PSPACE}\neq\mathrm{NEXP}\). However since the proof that \(\mathrm{MIP}=\mathrm{NEXP}\) doesn't relativize either, the question of the oracle separation between \(\mathrm{IP}\) and \(\mathrm{MIP}\) remained open until the Bouland et al. paper.

Finally, Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal and Emanuele Viola gave new exponential correlation bounds for polynomials. The authors use that bound to give a new pseudorandom generator against \(\mathrm{AC}^0[\oplus]\) circuits.

When I saw the paper I realized one could use this generator to show that \(\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\), answering a question I had wondered about in the 90s. Here \(\text{Almost-}\oplus\mathrm{P}\) is the class of languages \(L\) such that \(L\in\oplus\mathrm{P}^R\) with probability one for a random oracle \(R\). This in turn could be used to give an alternative proof of Toda's theorem. Ken Regan and Jim Royer showed that relative to a random oracle the polynomial-time hierarchy is contained in \(\oplus\mathrm{P}\), so \(\mathrm{PH}\subseteq\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\). It would take me a long time to work out and write up the details so I had Claude do it for me.

I still have many more open problems, see for example my survey of open oracle questions. I'd be happy to see them solved. Feel free to use AI but verify the proof. You too could get mentioned on this blog.

By Lance Fortnow

This is a draft lecture notes written under my guidance for today’s lecture. Blue text represent my further comments.) The lecture will be on Oct 7 at IAS, at 3:30, in the Seminar room.

I will speak at the IAS about the wonderful theory of intersection homology, introduced by Mark Goresky and Bob MacPherson, and some of its connections to combinatorics. This post is an extended description of the lecture and a set of notes toward it. I would like to explain the basic definitions, then discuss three directions that particularly interest me: the missing ring structure behind toric -vectors, the search for intersection homology in face rings, and extensions involving several perversities.

These questions continue discussions from the pleasant informal seminar we had here in 1995 with Bob MacPherson, Mark Goresky, Tom Braden, and a few others. I will try to keep the discussion self-contained and easygoing. Throughout, coefficients are rational unless another field is specified.

I will start by briefly discussing convex polytopes , the parameter , rigidity, and the theorem of Walter Whiteley.

For a closed oriented manifold of dimension , Poincaré duality gives a perfect pairing between homology in degrees and . Singular spaces need not satisfy this duality. Intersection homology repairs it by controlling the way chains meet the singularities.

Start with a stratified pseudomanifold, with filtration

The strata are manifolds, the top stratum is dense, and a neighborhood of a point in an -dimensional stratum looks like , where is the open cone on a compact link. We initially exclude codimension-one strata.

A traditional perversity is an integer function satisfying

For a PL -chain , the allowability condition is

A negative bound means that the intersection must be empty. The chain and its boundary must satisfy their respective conditions. These chains form a complex ; its homology is . One uses compatible subdivisions in the PL construction. A singular-chain formulation instead requires

for every simplex occurring with nonzero coefficient in the chain or its boundary. Requiring the boundary to be allowable is essential: allowable simplices alone do not form a chain complex. [1, 2]

Why do complementary perversities occur? If chains of dimensions and meet a codimension- stratum in their allowed dimensions, a general-position intersection there has dimension at most

For and , this bound is . Thus complementary cycles can intersect in the regular part, where signed intersection numbers make sense.

The theorem of Goresky and MacPherson says that, for a compact oriented pseudomanifold without boundary and complementary traditional perversities, this produces a perfect pairing

Traditional intersection homology is independent of the chosen suitable stratification. On a manifold it recovers ordinary homology. These are substantial theorems: the definition itself visibly uses the strata. [1, 2]

Let be a connected closed manifold of dimension . For the cone stratification, the finite-chain cone formula, in positive degrees, is

The zeroth group is . A cycle on the link becomes a boundary when its radial cone is allowable. For example, at a cone point of codimension three, prohibits a two-dimensional filling from meeting the vertex, whereas permits it. This is a useful local calculation to keep in mind throughout the lecture. [1, 6]

The two middle perversities are

They are complementary. They agree in even codimension and differ by one in odd codimension. A complex algebraic variety admits a stratification with even real codimensions, so the distinction disappears there. Middle intersection homology is consequently self-dual. For projective varieties it also has a hard Lefschetz theorem, with the action of an ample class. [2]

Here is a combinatorial definition that fixes our convention. For a -polytope , recursively define

including the empty face, with and . For a point, . Write

where . These are the toric h and g vectors, extending the usual simplicial definitions. For a polygon with vertices, the recursion gives

For rational , place the origin in its interior and take the fan of cones over its proper faces. Its projective toric variety has

This convention uses the face fan of , equivalently the normal fan of its polar. Using the normal fan of itself gives the convention for the dual polytope.

Duality gives ; hard Lefschetz gives . Combinatorial intersection cohomology of fans extends the theory beyond rational polytopes, and Kalle Karu proved hard Lefschetz in that generality. [3]

The paper of Tom Braden and Bob MacPherson, Intersection homology of toric varieties and a conjecture of Kalai, proves my monotonicity conjecture for rational polytopes using intersection homology. Braden’s subsequent paper, Remarks on the combinatorial intersection cohomology of fans, explains the extension to arbitrary polytopes, further properties of toric -vectors, and the connection between and rigidity. [11, 12]

There is also a striking relation between a four-dimensional polytope and its polar: $latex g_2(P)=g_2(P^)$. I discussed it in my post A Mysterious Duality Relation for 4-dimensional Polytopes. Braden’s work places such relations in a broader framework involving exact sequences and Koszul duality. Stanley’s Subdivisions and local h-vectors* is another central reference: it develops local invariants of subdivisions and identities connecting the toric invariants of dual face lattices. [12, 13, 14]

But there is a further question. Is the toric g vector of every convex polytope an M-sequence? That means it is the Hilbert function of a standard graded algebra:

This asks for more than nonnegativity. Macaulay’s inequalities constrain the growth of such a Hilbert function; already

For a simplicial polytope, its Stanley–Reisner ring provides the mechanism: take an Artinian reduction by a linear system of parameters, then quotient by a Lefschetz linear form. The Hilbert function of this last quotient is the -vector.

For a general polytope we have intersection cohomology and Lefschetz operators, but no natural internal multiplication on fixed middle-perversity intersection cohomology that supplies this argument. There are products involving different perversities, and an action of ordinary cohomology; neither automatically gives the needed standard graded algebra. This is the missing ring problem. A suitable substitute might be enough: an algebra realizing the primitive dimensions, or another mechanism enforcing Macaulay’s inequalities. The numerical M-sequence question and the construction of a geometrically meaningful multiplication are related, but distinct problems.

I discussed the search for a product—or a weaker substitute, perhaps resembling a Massey product—in my 2004 report, Combinatorial expectations from commutative algebra. This remains a useful reference for the missing ring problem and its broader combinatorial motivation. [17]

Paul Siegel’s Witt condition enlarges the class of spaces with self-dual middle intersection homology beyond spaces with only even-codimension singularities. At every singular stratum of odd codimension , its link has dimension . The rational Witt condition is

On a Witt space the natural comparison from lower-middle to upper-middle intersection homology is an isomorphism. Compact oriented Witt spaces therefore have a self-dual middle theory. The condition is local and depends on the coefficient field. [4]

For a concrete example, the cone on a two-torus fails the Witt condition because . The cone calculation gives lower-middle and upper-middle . In contrast, the cone on satisfies the condition. The obstruction is precisely the middle homology of the link.

Paul Howard Siegel developed Witt spaces in his 1979 MIT thesis, with crucial guidance from Mark Goresky. Goresky introduced him to the problem, and their conversations were central to its solution. Edward Y. Miller was the formally listed thesis supervisor. Siegel’s paper appeared in 1983. His later career took him into information theory, coding, and data storage, through IBM Research and UC San Diego. I find this a lovely connection between a beautiful idea about singular spaces and a quite different area of mathematics and engineering. [5]

The upper bound theorem says that a -polytope with vertices has no more -faces than the cyclic polytope . Here is the simplicial Witt-space conjecture I would like to discuss:

Conjecture. Let triangulate a compact oriented Witt pseudomanifold of dimension , with vertices. If is even, additionally assume . Then

The global vanishing assumption is additional to the local Witt condition. Every closed oriented manifold is a Witt space, so the local condition alone cannot impose all cyclic-polytope bounds. For example, the seven-vertex triangulation of the torus has 21 edges, while the boundary of a three-dimensional cyclic polytope with seven vertices has 15.

Novik proved the bound for even-dimensional manifolds with vanishing middle homology. Her ICM survey states the Witt-space conjecture and discusses further cases and stronger upper-bound questions. The hoped-for bridge is an algebraic interpretation of intersection homology that interacts with face enumeration. [7]

Let be a simplicial complex on . Its symmetric face ring is

Its exterior face ring is

Both record faces; their additional algebraic structures record much more.

In the exterior ring there is a particularly direct illustration. Multiplication by gives a differential , since . Its cohomology in degree is the reduced simplicial cohomology : the monomial basis is the face basis, and the differential adds one vertex with the usual signs. Thus ordinary cohomology already lives in this algebra.

On the symmetric side, local cohomology and graded resolutions encode the homology of links and induced subcomplexes. For triangulated manifolds, Schenzel’s formula and the work of Novik and Swartz show how ordinary Betti numbers enter Artinian reductions and their socles. These results provide models for what one might seek for intersection homology. [8, 9]

The question is to recover, for each traditional perversity,

through algebraically defined complexes, subquotients, or filtrations associated with either face ring, without supplying a separate stratification. Here “arbitrary perversities” initially means arbitrary traditional Goresky–MacPherson perversities; more general stratum-dependent or superperversities require separate invariance hypotheses.

Merely recovering ordinary homology is insufficient. In the cone on the torus, ordinary positive-degree homology vanishes, while lower-middle intersection homology retains two degree-one classes. Any proposed face-ring construction must distinguish these phenomena.

A possible direction is to use generic linear forms and their flags to express allowability algebraically. On the exterior side this suggests kernels of contraction operators; on the symmetric side, Koszul complexes, annihilators, and local cohomology suggest candidates. These are research directions, not established replacements for the intersection-chain definition.

For the algebraic background, see also Braden’s Koszul duality for toric varieties and the paper with Valery Lunts, Equivariant-constructible Koszul duality for dual toric varieties. These concern categories of sheaves associated with dual cones; they provide a further connection between intersection cohomology and homological algebra. [15, 16]

There are several useful tests. On manifolds, a candidate must recover ordinary homology for every traditional perversity. On cones, it must reproduce the correct perversity-dependent truncation. It must survive subdivision and produce the complementary-perversity pairing. To help with upper bounds, it must also relate the resulting groups to dimensions or multiplication in the face ring. The last requirement is what makes this a combinatorial project rather than just another way to calculate topological groups.

Here I will talk about my (dubious) vision.

In our paper, A multiperversity generalization of intersection homology, Greg Friedman and I replace one perversity by a finite collection . Let be the span of singular -simplices allowable for at least one member of . Then

Different simplices may use different perversities, and the boundary may use different choices again. Consequently this is generally not the sum of the single-perversity intersection-chain complexes. If has a greatest member, the construction reduces to that member; incomparable perversities are the interesting case.

We established subdivision, Mayer–Vietoris, product results, and a cone formula. The paper left independence of stratification open. Its motivation was to find further invariants of singular spaces and, eventually, further combinatorial invariants of polytopes. [6]

Topological invariance is the central issue. An extra subdivision of a manifold must not create new invariants by adding artificial strata. More generally, the same underlying singular space, described by different suitable stratifications, should give canonically comparable groups. Henry King’s intrinsic-stratification approach gives a strategy; Greg’s later short proofs of ordinary intersection-homology invariance offer further guidance. [10]

One can see why collections of perversities introduce extra bookkeeping. For a link of dimension , define

These are the labels under which an -cycle can be filled radially in the cone. As changes, the collection changes. One must therefore track the maps between theories for subcollections, not just the dimensions of the groups. Images of these maps can matter even when the separate groups are known.

The question is whether this local information can be assembled into a proof that the theory is unchanged under intrinsic aggregation of strata. A proposed proof must keep the comparison maps compatible with inclusions of collections, cone constructions, and the passage from local charts to the whole space. Duality for multiperversities is another question; it does not follow just by complementing each member of a collection.

I hope (do I really hope it?) these directions will eventually reinforce one another: more flexible topological invariants, algebraic constructions inside face rings, and new inequalities for face numbers. For the lecture, I would like to emphasize both the remarkable strength of the classical theory and the concrete questions that remain.

1. Mark Goresky and Robert MacPherson, Intersection homology theory, Topology 19 (1980), 135–162. Paper.
2. Mark Goresky and Robert MacPherson, Intersection homology II, Inventiones Mathematicae 72 (1983), 77–129. Paper.
3. Kalle Karu, Hard Lefschetz theorem for nonrational polytopes, Inventiones Mathematicae 157 (2004), 419–447. Preprint.
4. Paul H. Siegel, Witt spaces: A geometric cycle theory for KO-homology at odd primes, American Journal of Mathematics 105 (1983), 1067–1105. See also Greg Friedman, Intersection homology with field coefficients: K-Witt spaces and K-Witt bordism.
5. Siegel’s MIT thesis and UC San Diego biography.
6. Greg Friedman and Gil Kalai, A multiperversity generalization of intersection homology, Pure and Applied Mathematics Quarterly 3 (2007), 205–224. Author’s preprint.
7. Isabella Novik, Face numbers: the upper bound side of the story, ICM 2022; especially Section 5 and Conjecture 5.1. Survey.
8. Isabella Novik and Ed Swartz, Socles of Buchsbaum modules, complexes and posets, Advances in Mathematics 222 (2009), 2059–2084. Preprint.
9. Satoshi Murai, Isabella Novik, and Ken-ichi Yoshida, A duality in Buchsbaum rings and triangulated manifolds. Preprint.
10. Greg Friedman, Two short proofs of the topological invariance of intersection homology. Preprint.
11. Tom Braden and Robert MacPherson, Intersection homology of toric varieties and a conjecture of Kalai, Commentarii Mathematici Helvetici 74 (1999), 442–455. Preprint.
12. Tom Braden, Remarks on the combinatorial intersection cohomology of fans, Pure and Applied Mathematics Quarterly 2 (2006), 1149–1186. Preprint.
13. Richard P. Stanley, Subdivisions and local h-vectors, Journal of the American Mathematical Society 5 (1992), 805–851. Paper.
14. Gil Kalai, A Mysterious Duality Relation for 4-dimensional Polytopes, Combinatorics and more, June 6, 2018. Blog post.
15. Tom Braden, Koszul duality for toric varieties, Transactions of the American Mathematical Society 359 (2007), 385–415. Preprint.
16. Tom Braden and Valery Lunts, Equivariant-constructible Koszul duality for dual toric varieties, Advances in Mathematics 201 (2006), 408–453. Preprint.
17. Gil Kalai, Combinatorial expectations from commutative algebra, in Combinatorial Commutative Algebra, Oberwolfach Reports 1 (2004), Report 32/2004. Report

By Gil Kalai

With Danny and Sharon Kleitman and Michel Goemans at the MIT Endicott house.

A few hours ago, Open AI shared solution to a few hundred mathematical problems. Certainly this is an amazing milestone for mathematics, and the results will needs to be verified and digested by human mathematicians in the months to come. Several of the problems were discussed here on the blog over the past two decades and I will try to give a more detailed update regarding these problems and other “Math for AI” recent achievements.  This is an amazing development!

Both the Open AI list and some news from colleagues from the last days are relevant to my lecture around Borsuk’s conjecture on Friday in Jeff-Fest.

I am currently in the middle of a nostalgic and hectic tour, visiting Brown University, MIT, Yale, IAS, Rutgers  (for Jeff Kahn’s conference celebration), and Princeton University.  It is a pleasure to meet old friends and (both young and old) mathematicians that I did not meet before.  I truly love both mathematics and the community of mathematicians, and I hope my lectures and posts reflect this feeling.

Right now I am writing from Avi and Edna’s home at the IAS,  having just returned from a lovely mathematics department event welcoming the new academic year. Tomorrow, I will be speaking here about intersection homology and combinatorics. Later in the evening, I am giving a short lecture in the “discussion series” about my work on quantum computation, which I hope will spark an engaging conversation. It will be quite a challenge to present quantum computation and my two decades of research on the subject in a 20-to-30-minute lecture tailored for a general audience.

I also have a rather intense blogging plans: I am planning three posts based on my lectures: one on algebraic shifting at MIT, one on intersection homology and combinatorics at the IAS, and one on problems around Borsuk’s conjecture at “Jeff Fest.” Here is how I plan to go about it: I will feed an AI tool my abstract and a rough outline of the talk, and let it prepare detailed lecture notes that I can use for the presentation itself. (For the MIT talk, I only thought of this approach after the fact!) Later on, I will edit those lecture notes into blog posts. It is quite interesting—and a little amusing—to note that the AI writes not only about the technical matters but also attempts to capture “my” feelings and hopes.

I also plan a post with a candidate for “the most outrageous conjecture,” alongside an entertaining double-feature “test your intuition” post.

As I mentioned above, OpenAI released an impressive collection of mathematical results produced by an internal AI model: 722 manuscripts grouped into 372 families. Many of these concern problems that have appeared on this blog over the years.

Three disclaimers: first, the collection includes results with different stages of verification; their proofs will need to be checked and digested by the mathematical community.  Second, even Lean verification may have issues, and third, there were a variety of other AI based results, also related to earlier blog posts that I did not collected; among those let me mention the Irrationality of , the Navier Stoke problem, The Komlos conjecture, Chvatal’s conjecture, and the KLS conjecture.

Here are twenty connections to earlier posts, with related results occasionally grouped together.

1. The Mahler conjectures. I discussed the symmetric Mahler conjecture and its connections to symplectic geometry and my conjectures on faces and flags. The release announces proofs of both the symmetric and general Mahler conjectures in every dimension, including the equality cases of Hanner polytopes and simplices, respectively.
2. Borsuk’s problem in dimension nine. The question of the smallest dimension admitting a counterexample to Borsuk’s conjecture has appeared here repeatedly, including in this 2023 update. The new manuscript gives a compact set in nine-dimensional Euclidean space that cannot be covered by ten sets of smaller diameter.
3. Hadwiger’s conjecture. In Combinatorics News I discussed Hadwiger’s conjecture, which relates graph coloring to complete minors, while reporting the disproof of its odd-minor strengthening. The new announcement gives counterexamples to the original conjecture, even among graphs with independence number at most two.
4. The chromatic number of the plane. In 2018 I reported Aubrey de Grey’s breakthrough showing that five colors are necessary to avoid monochromatic pairs at distance one. The new manuscript raises the lower bound to six, leaving six and seven as the two possible answers.
5. The Kakeya problem. My post on Hong Wang and Joshua Zahl’s breakthrough discussed the three-dimensional Kakeya set conjecture and the stronger maximal-function problem. The release announces the maximal conjecture in three dimensions and the Hausdorff-dimension conjecture in four dimensions.
6. Periodic tiling in dimension three. In An Aperiodic Monotile I also mentioned Greenfeld and Tao’s disproof of the periodic translational tiling conjecture. The new construction gives a finite translational tile in that admits no fully periodic tiling, reaching the smallest possible dimension for the lattice problem.
7. Covering density of convex bodies. I described the breakthrough of Ordentlich, Regev, and Weiss on efficient lattice coverings in this post. OpenAI announces a universal lattice-covering bound and matching examples even for unrestricted translative coverings, determining the worst-case order over convex bodies.
8. Distinct distances and unit distances. These problems featured in János Pach’s guest post on Guth and Katz and in my earlier extremal-combinatorics post. The release includes the sharp-order bound for distinct distances in every fixed dimension and an improved planar unit-distance bound for some absolute .
9. Erdős’s arithmetic-progression conjecture. My post on Bloom and Sisask’s breakthrough discussed the three-term case of the assertion that divergent reciprocal sums force arithmetic progressions. The new result covers every finite length: any set of positive integers with divergent reciprocal sum contains arbitrarily long arithmetic progressions, with quasipolynomial quantitative bounds in Szemerédi’s theorem.
10. Sidorenko’s conjecture. I described Sidorenko’s conjecture, which predicts that a fixed bipartite graph has at least the density it would have in a random graph of the same edge density. The announced counterexample has 35 vertices and 66 edges and also disproves the related forcing conjecture.
11. Ryser’s covering conjecture. I discussed Ryser’s conjecture in my birthday post for Ron Aharoni, including his proof of the tripartite case. The new counterexamples are intersecting -partite, -uniform hypergraphs requiring vertices to meet every edge, whereas the conjecture predicts .
12. Crossing numbers of complete and complete bipartite graphs. These problems appeared in my discussion of Turán’s mathematics. The release reports proofs of the Harary–Hill and Zarankiewicz formulas, determining the minimum number of crossings in plane drawings of complete and complete bipartite graphs.
13. Barnette’s Hamiltonian-cycle conjecture. In Coloring Simple Polytopes and Triangulations I discussed Barnette’s conjecture that every cubic, bipartite, 3-connected planar graph has a Hamiltonian cycle. The new manuscript announces a proof of this conjecture.
14. Combinatorial invariance of Kazhdan–Lusztig polynomials. This was Problem 11 in my discussions of the G-programme, and I returned to it in a 2021 post about DeepMind’s mathematical work. The announced theorem says that isomorphic Bruhat intervals have the same equal-parameter Kazhdan–Lusztig polynomial, even when the intervals come from different Coxeter systems.
15. Ramanujan graphs and higher-dimensional expanders. The subject of New Ramanujan Graphs! returns with a deterministic polynomial-time construction of nonbipartite Ramanujan graphs, for every fixed degree at least three and every sufficiently large even number of vertices. In higher dimensions, the release announces bounded-vertex-degree coboundary expanders over in every dimension at least three, continuing the theme of my introductory posts.
16. The second Kahn–Kalai conjecture and Talagrand’s conjectures. The release reports proofs of the second Kahn–Kalai conjecture, which bounds graph-containment thresholds using subgraph expectations, and of Talagrand’s discrete convexity conjecture, both discussed in my account of Jinyoung Park’s ICM lecture. A companion result makes integral and fractional expectation thresholds equivalent up to a universal constant.
17. The Friedgut–Kalai sharp-threshold conjecture. Sharp thresholds and the role of symmetry were central themes of Boolean Functions: Influence, Threshold, and Noise. The release announces the threshold-width bound for monotone graph properties between fixed intermediate probabilities, where counts vertices, together with the conjectured extension to uniform hypergraphs.
18. Unique Games and 2-to-1 Games. My 2018 post on the 2-to-2 Games Theorem discussed progress toward Khot’s conjectures and the issue of perfect completeness. The release announces a proof of the Unique Games Conjecture and, separately, the 2-to-1 Games Conjecture with perfect completeness.
19. Matrix multiplication. My post Cap Sets, Sunflowers, and Matrix Multiplication explored the connections between these problems. The new bound is over the complex numbers, a substantial advance toward the conjecture .
20. Percolation: criticality and nonuniqueness. The release includes absence of infinite critical clusters for bond percolation on infinite connected locally finite quasi-transitive graphs with , extending the setting of my recent post on an AI proof of critical nonpercolation. It also announces for nonamenable graphs in this class, resolving the Benjamini–Schramm nonuniqueness conjecture discussed here in 2009.

1. The logarithmic Brunn–Minkowski conjecture. My post The Logarithmic Minkowski Problem (2021) discussed the closely related existence problem for convex bodies with prescribed cone-volume data. The release announces a proof of the logarithmic Brunn–Minkowski conjecture for origin-symmetric convex bodies in every dimension.
2. The two-point Chowla conjecture. In EDP Reflections and Celebrations (2015), I discussed Tao’s logarithmically averaged Chowla and Elliott results and their role in solving the Erdős discrepancy problem. The new manuscript announces the ordinary two-point Chowla conjecture, giving cancellation in the Liouville correlations (\sum_{n\le X}\lambda(n)\lambda(n+h)=o(X)) for every fixed (h\ge1).
3. High-dimensional expanders. In High Dimensional Expanders: Introduction I (2011), I discussed several notions of expansion for simplicial complexes, including coboundary expansion. The new construction gives arbitrarily large complexes in every dimension (d\ge3), with bounded vertex degrees and uniform (\mathbb F_2) coboundary expansion in every degree below (d).
4. Amenability of Thompson’s group (F). My post The Thompson Group (2009) introduced the group of dyadic piecewise-linear homeomorphisms of the interval and highlighted the question of whether it is amenable. The new manuscript announces that Thompson’s group (F) is nonamenable.
5. Flat and ultraflat Littlewood polynomials. In Flat polynomials exist! (2019), I described the breakthrough of Balister, Bollobás, Morris, Sahasrabudhe, and Tiba and emphasized the remaining ultraflat problem for coefficients (\pm1). The new manuscript announces polynomials with (N) such coefficients whose modulus is ((1+o(1))\sqrt N) uniformly on the entire unit circle, answering that stronger question.

It is remarkable to see so many familiar questions in a single announcement. There is a great deal here to read, check, understand, and build on!

By Gil Kalai

Authors: Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell

Authors: Alexandr Grebennikov

Authors: Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi

Authors: Zhewei Wei

Authors: Mikkel Abrahamsen, Jacobus Conradi, Asbjørn Lind

Authors: Hariharan Narayanan

Authors: Joshua Brakensiek, Aaron Putterman, Amatya Sharma, Santhoshini Velusamy

Authors: Anup Bhattacharya, Suryendu Mondal, Pinki Pradhan

Authors: Arnab Mallick, Indraveni Chebolu

Authors: Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Chinmay Sonar, Vaishali Surianarayanan, Jie Xue

Authors: Eric Dai, Maxwell Fishelson

Authors: Hanqing Li

Authors: Hanqing Li

Authors: Moran Feldman, Alan Kuhnle

Authors: Purv Patel, Ajay D. Kshemkalyani

Authors: Jerry Anunrojwong, Akshit Kumar, Rachitesh Kumar

Authors: Victor Lagerkvist

Authors: Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff

Authors: Daniel A. Spielman, Xifan Yu

Authors: Cameron Ibrahim, S M Ferdous, Erdal Mutlu, Ilya Safro, Mahantesh Halappanavar

Authors: Emile Anand, Jan van den Brand, Peter Chen

Authors: Benjamin Lovitz

Authors: Marcia Fampa, Jon Lee

Authors: Nader H. Bshouty

Authors: Zhangsong Li

Recent OpenAI Math dump have solutions to many long standing probems in Math and TCS. In the dump, two problems that I and my friends, notably Arnold Filtser, have studied for more than a decade, and published a few papers about this:

1. The $\ell_1$-embedding conjecture for planar graphs. Open AI solution here.
2. The $\ell_1$-embedding conjecture for bounded treewidth graphs. Open AI solution here.

It is unsettling and hard to swallow. I have not looked at the details yet, and will be doing so in the next few days. On a positive note, I hope to learn new techniques in planar graphs. I always believe that we have not been able to solve these problems because we lack a serious understanding of planar metrics. Now that they are solved, learning what the serious understanding is exciting.

A clear next prediction (not included among Open AI solution) is a solution of the conjecture that that minor-free graph metrics are embeddable into $\ell_1$ with constant distortion. Using the Robertson-Seymour decomposition, one basically could reduce this conjecture to bounded treewidth and planar graphs. At this point, I feel that understanding the two results above are more important than churning out another result.

Will udpate my understsanding of the two papers above.

I intentially do not mention other big results. What a strange time to be alive.

By Hung Le

I was just pointed to https://arxiv.org/abs/2610.06783v1 wow! Another item for my growing list of disproved conjectures in my book… told ya that P=NP!

By Manu

Hi there, argmin readers! Today’s post is a live blog of Class 10 of my graduate seminar “Forecasting: A Critical Retrospective.” The syllabus and list of past posts are here.

All of my cybernetically inclined friends are into Friedrich Hayek, but my research and teaching keep bringing me back to John Maynard Keynes. These two gentlemen occupy the two poles of the dialectic of the American Experiment. Hayek famously introduced the notion of markets as distributed computers, where prices carry knowledge across the economy. Keynes, with his economic theory of central banking, set the stage for centralized computing of economic variables to govern those markets.

In Keynes’ paradigm-shifting 1936 work, The General Theory of Employment, Interest, and Money, he lays out an oxymoronic formula for central planning in capitalist societies.1 The basics of the Keynesian model are laid out in the appendix of Robert Evans’ paper from this week’s reading. The national economy has four key variables: the amount of investment firms make into the economy, the amount of savings firms accumulate in financial instruments or by paying down debt, the demand for money in the economy to facilitate purchases and sales, and the supply of money from the government. To change these variables, the government can enact various policies. For example, it can invest in infrastructure, raise taxes, increase the money supply, or change interest rates. Keynes argues that the government can dictate the economy’s output—and hence the general welfare of all citizens, who are players in the big macroeconomic game—by properly executing its policy apparatus.

This would set the stage for the subsequent 90 years of democratic capitalist monetary policy. The government has to make policy to ensure a well-run economy. To do this, it has to know the current state of national investment and savings. It also has to be able to forecast what these variables will be if no policy changes are enacted. This last requirement has driven the major investment in macroeconomic forecasting.

Forecasting in macroeconomics is thus primarily a tool of control. Here I mean control in the academic sense: the theory of dynamical systems with inputs and outputs and the design of subsystems to drive outputs to desired targets. Keynes casts the economy as a giant control problem, where the goal is to deftly change policy to ensure a particular state of economic output and employment. It should be no surprise that tools from control, notably the work of Rudolf Kalman on optimal filtering and control of linear systems with quadratic objectives, play a central role in macroeconomics.

Now, to filter and control, we need to make predictions. Keynes didn’t tell us how to generate those predictions. But his disciples, in what is often called “Keynesian” macroeconomic forecasting, write down structural equations of the economy, fit the parameters of these equations using varied means, and then make forecasts directly from the fitted models.

This program of prediction ran into several obstacles. First, it requires mathematical equations that predict all of the aspects of the economy needed to precisely determine optimal policies. Second, it requires a massive measurement system to pin down all the relevant factors in the model. Both were terribly daunting and required a great deal of expert judgment.

Economists want their methods to be “scientific,” since they influence decisions with major consequences. However, with so many variables, so little stationarity in economic conditions, and so much politics involved, building a truly objective and replicable system seems like a fool’s errand. Beatrice Cherrier details some of the typically arbitrary, political nature of macroeconomic sausage-making in this blog post. Evans details the amount of analytical flexibility and expert judgment forecasters necessarily employ in their predictive techniques.

Beyond these nuances of modeling and measurement, however, a fundamental problem of feedback control remains insurmountable. The models have a ton of parameters that are fit to historical data. Different policies yield different parameters. These parameters change when a policy changes. And you can’t predict what the parameters will be after a policy changes. So what on earth are we doing?

The critique in the previous paragraph was levied at macroeconomic forecasting by Robert Lucas in 1976. That macroeconomic forecasting is still an influential practice 50 years later certainly tells us something. Macroeconomic forecasters occupied positions of power and held a sense of civic duty. So they took Lucas’ critique as a challenge, not a reason to close up shop.

I’m not going to hash out the various attempts to build complex, nonparametric macroeconomic models that add ornate complexity while failing to dodge the fundamental problem. Theoretical critiques can carry only so much weight. The fact that the Great Recession was substantially caused by terrible financial policy and inadequate forecasting should have been the nail in the coffin. In 2003, Robert Lucas himself declared that macroeconomics had been a great success:

“My thesis in this lecture is that macroeconomics in this original sense has succeeded: Its central problem of depression prevention has been solved, for all practical purposes, and has in fact been solved for many decades.”

Oops.

Economists didn’t see a problem with the deep instability created by hyperfinancialization. Indeed, though Evans did his ethnographic research on macroeconomists a decade before the crash, his point rings true:

“...[E]conomic policy cannot be based on a quantitative calculus of costs and benefits and must, instead, rest on the considered judgement of a community of experts. Macroeconomic modellers may be those experts, but to expect anything more from them is to expect too much.”

So who should we trust? The Obama administration hoped economists could help get us out of the mess. But 8 years of attempted neoliberal patching of the American system ended in such broad dissatisfaction that… well, you know what happened. We’ve since had a decade of federal unrest as we try to unmoor ourselves from the expertise of economists. While I don’t believe the Biden and Trump administrations have found themselves a suitable alternative, I make no predictions about whose policy advice we’ll be deferring ot next.

Subscribe now

By Ben Recht

By Ittai Abraham, Clément Burgelin, Antoine Murat, Joachim Neu

Authors: Christine Li, Natalie Parham

Authors: Mark Bun, Joao F. Doriguello, John Kallaugher, Nadezhda Voronova

Authors: Berta Casas, Diego García-Martín, Yuxuan Zhang

Authors: Anssi Yli-Jyrä

Authors: Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung, Tzu-Yi Yang

Authors: Szilárd Zsolt Fazekas, Xinhao Huang, Robert Mercaş

Authors: Andrew Huang, Akshar Ramkumar, John Wright

Authors: Swastik Kopparty, Rishabh Kothary, Shanthanu S. Rai

Authors: Quinten Tupker

Authors: Olivier Bournez, Johanne Cohen, Laura Cohen, Adrian Wurm

Authors: Vasilis Pollatos, Andreas Kontogiannis

Authors: Boyu Liu, Zihe Wang

Authors: Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal

Authors: Siu On Chan, Jeff Xu

Authors: Chenghua Liu, Boning Meng

Authors: Yannis Tzitzikas

Authors: Gabriel Istrate

Authors: Dax Enshan Koh, Triscia Mundo, Iosif Sakos, Antonios Varvitsiotis

Authors: Mitali Bafna, Quynh T. Nguyen, Tina Zhang

Authors: Jin-Yi Cai, Jin Soo Ihm

Authors: Yoshiki Nakamura, Yuya Uezato

Authors: Sanjay Jain, Frank Stephan, Haoyun Tang

Authors: Jeremy Ahrens Huang

Authors: Dimitrios Myrisiotis

Authors: Ezekiel Cochran, Atul Mantri

Authors: Klaus Jansen, Dirk Nowotka, Lis Pirotton, Corinna Wambsganz, Max Wiedenhöft

Authors: Mattéo Clémot, Julie Digne, Julien Tierny

Authors: Animesh Maiti, Prakhar Shukla, Subhash Bhagat

Authors: Prakhar Shukla, Animesh Maiti, Shivam Kumar, Subhash Bhagat

Authors: Aoran Zhang, César A. Uribe

Authors: Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty, Subhash Bhagat

Authors: Josh Alman, Virginia Vassilevska Williams

Authors: Xiaoyu Chen, Kuikui Liu

Authors: Thomas Depian, Robert Ganian, Jakob Greilhuber, Marlene Gründel, Simon Wietheger

Authors: Simon Apers, Roman Edenhofer, Benjamin Mathieu-Bloise, Partha Mukhopadhyay

Authors: Jonas Friemel, Tilo Hoitz, Phillip Keldenich, Arne Schmidt

Authors: Pascal J. Gollin, Tesshu Hanaka, Ekkehard Köhler, Martin Milanič, Yushi Uno

Authors: Yonggang Jiang, Xiaoming Sun, Penghui Yao, Zekun Ye, Jialin Zhang, Zhijie Zhang

Authors: Barak Gorodissky, Tal Wagner

Authors: Ruizhe Zhang

Authors: Mohammad Ansari, Sina Azizeddin, AmirMohammad Bandari, Pouria Mahmoudkhan, Hamid Zarabi-Zadeh

Authors: Sriram Bharadwaj, Di Luo, Leo Zhou

Authors: Alvan Arulandu, Sitan Chen, Ziyun Chen, Jerry Li, Eric Ma

Authors: Dutch Hansen, Jerry Li

Authors: Alexander Schmidhuber, Alexander Zlokapa

Authors: Junzhao Yang

Authors: Nadezhda Voronova

Authors: Yang P. Liu, Richard Peng, Alicia Stepin, Colin Tang

Authors: Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar, Jaikumar Radhakrishnan

Authors: Chenxin Dai, Alicia Stepin, Colin Tang

Authors: Dario Fiorenza, Daniele Gorla, Ivano Salvo

Authors: Fan Chen, Sinho Chewi, Jianfeng Lu, Matthew S. Zhang

Authors: Daniele Carnevale

Authors: Sourav Das, Ashwin Jacob, Arpit Kumar, Diptapriyo Majumdar

Authors: Sepideh Mahabadi, Jakub Tarnawski

Authors: Wataru Inariba

Authors: Yiyi Cai, Yongtao Zhan, Alexander Zlokapa

Authors: Yoshiteru Ishida

Authors: Jessica Enright, Melissa A. Huggan, Ethan Hunter-Frankland, Margaret-Ellen Messinger, Dylan Pearson

Authors: Mahmoud Abo Khamis, Hubie Chen

Authors: Hyundong Jin, Hyunki Hong, Yo-Sub Han

Authors: Dennis Joyce

Authors: Simone Faro

Authors: Dmitry Kamenetsky

Authors: Simon Frisk, Sungjin Im, Paraschos Koutris, Benjamin Moseley, Hung Ngo, Kirk Pruhs, Hangdong Zhao

Authors: Vaneet Aggarwal

Authors: Simon Frisk, Paraschos Koutris

Authors: Lucas de Oliveira Silva, Lehilton Lelis Chaves Pedrosa

Authors: Xi Chen, Ruiquan Gao, Yuhao Li, Aviad Rubinstein, Mihalis Yannakakis

Authors: Rong-Hua Li, Yichun Yang, Junjie Zhou

Authors: Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu

Authors: Ali Karim Lalani

The Joint Center for Quantum Information and Computer Science (QuICS, http://quics.umd.edu) is seeking exceptional candidates for the QuICS Hartree Postdoctoral Fellowships in Quantum Information and Computer Science. Apply at: https://umd.wd1.myworkdayjobs.com/en-US/UMCP/job/QuICS-Hartree-Postdoctoral-Fellow-1_JR104987

Website: https://umd.wd1.myworkdayjobs.com/en-US/UMCP/job/QuICS-Hartree-Postdoctoral-Fellow-1_JR104987
Email: quics-coordinator@umiacs.umd.edu

By shacharlovett

Authors: Ihar Babushkin, Oliver Melchert, Ayhan Demircan, Uwe Morgner

Authors: Eric Culf

Authors: Jiawei Li, Zhiyang Xun, Lijie Chen, Jonah Brown-Cohen

Authors: Eshan Chattopadhyay, Noam Ringach, Nicholas Spooner

Authors: Xin Li, Yan Zhong

Authors: Alper Cakan

Authors: Adam Bouland, Matthew Ding, Siddhartha Jain

Authors: Shih-Han Hung, Han-Hsuan Lin

Authors: Erin Chambers, Shankha Shubhra Mukherjee, Katharine Turner

Authors: Pankaj K. Agarwal, Esther Ezra, Micha Sharir

Authors: Francisco Escudero Gutiérrez, Junseo Lee, Sebastian Zur

Authors: Arthur Braida, Joseph Cunningham, Jérémie Roland

Authors: Kleitos Papadopoulos

Authors: Kou Hamada, Satoru Iwata

Authors: Suho Kang, Rajan Udwani

Authors: Rudransh Kumar, Nima Nasiri, Jared Paul, Sathish Gopalakrishnan

Authors: Cyril Nicaud, Pablo Rotondo

Authors: Philip N. Klein

Authors: Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, Brian Hu Zhang

Authors: Sherzod Turaev, Mary John, Mamoun Awad

Authors: Dylan Herman, Jacob Watkins, Guneykan Ozgul, Jiayu Shen, Brandon Augustino, Junhyung Lyle Kim, Shouvanik Chakrabarti

Authors: Shuchi Chawla, Trung Dang

Authors: Peter Kiss, Arash Kooroshnezhad

Authors: Anupam Prakash, Shree Hari Sureshbabu, Dylan Herman, Shouvanik Chakrabarti

Authors: El-Mehdi Mehiri, Nabil Absi, Elodie Suzanne

Authors: Yash Khanna

The School of Computer Science at McGill University (Montreal, Canada) invites applications for a tenure-track appointment at the rank of Assistant Professor. We are seeking candidates with a PhD (or close to finishing) in Computer Science and expertise at the intersection of quantum computing and computer science.

Website: https://mcgill.wd3.myworkdayjobs.com/en-US/McGill_Careers/job/Tenure-Track-Faculty-Position-in-Computer-Science–Quantum-Computing_JR0000080250
Email: brigitte.pientka@mcgill.ca

By shacharlovett

This semester, I’ve been teaching a brand-new course, entitled CS395T AI Alignment Theory. Here’s the course description:

The astounding progress of AI over the past decade has been accompanied by a rising fear: do we really understand how to align and control powerful AI systems—how to get them reliably to do what we wanted, or would want them to do on reflection, rather than merely what we said? If we succeed at building general-purpose superhuman intelligences along the current paradigm, should we expect that development to go well for humanity? Can we modify the design, training, monitoring, or scaffolding of those intelligences to help ensure that it goes well? While there’s been a great deal of recent empirical work touching on these questions, this course will concentrate mainly on theoretical and mathematical foundations. As a warning, the theoretical foundations of AI alignment have not yet gelled into any one coherent body of results accepted as canonical by the field. Nevertheless, in this course, we’ll read and debate many of the conceptual and mathematical works that have been most influential in the AI alignment field, from both before and during the current LLM revolution. Student presentations, reports, and projects will play a central role.

I vividly remember encountering Eliezer Yudkowsky and his Sequences 20 years ago. I remember thinking: even if these people talk and act like crazy cultists, still, let me bend over backwards to be epistemically virtuous, and entertain their ideas on their merits, as very few academics would. Even if, of course, I ultimately end up rejecting the ideas, on the simple ground that powerful AI is such an absurdly remote prospect that it’s almost impossible to say anything useful about it today, outside the realm of speculative fiction.

For my failure to see what was coming, it seems like an appropriate punishment that I’m now, in 2026, effectively teaching a course on Yudkowsky Studies. And it’s the most important course I can teach.

Well, for some definition of “teach.” The thing about AI alignment is that there’s no textbook (though apparently ILIAD is working on one), no core of nontrivial theorems considered canonical by the field, no real body of mathematical theory at all. This makes it extremely different from the courses I’m used to teaching, like Quantum Information Science or Computability and Complexity.

So we’ve been running the course as a discussion seminar. Every session, a “rapporteur” presents an AI alignment research paper or other reading; then I and others ask questions and discuss. Some of the readings (like Omohundro on the “basic AI drives,” or Hadfield-Menell et al. on the off-switch game) predate the current LLM revolution, while others (like the METR report on the HuggingFace incident or Dario Amodei’s “We Must Pace the Frontier”) are so timely that they were only released while the course was underway. Most are somewhere in between.

I expected to have to make a case to students about why AI alignment is a pressing concern, why it’s no longer science fiction, etc. There was huge demand for the course, and while of course there’s a selection effect, the students who’ve shown up have been extremely engaged, sometimes criticizing the assigned papers for not taking existential risk seriously enough.

Perhaps unsurprisingly, we didn’t get that criticism about our very first assigned reading, which was Eliezer Yudkowsky’s 2022 essay AGI Ruin: A List of Lethalities—one the most canonical statements of what Eliezer believes and why that’s shorter than a book. Which brings me to the topic of the rest of this post! Our rapporteurs are not merely presenting the papers in class; they’re also submitting written reports about what the papers said, what their own thoughts were, and what were the highlights of the class discussion. And, with student permission, I’ll be sharing those reports on this blog!

So, without further ado, I present to you our first report, on Eliezer’s list of lethalities, by Tennyson Bardwell, who I thank for his work. Feel free to discuss in the comment section; some of the students might also chime in. Expect more reports here over the coming weeks.

UT Austin has a new Computer Science course this fall. Alongside familiar graduate-level classes such as Advanced Computer Networks and Convex Optimization sits CS 395T: AI Alignment Theory, taught by Scott Aaronson. This is one of a growing number of AI Alignment courses taught at academic institutions. Just as concerns over catastrophic consequences for misaligned AGI systems reach a broader public discourse, Eliezer Yudkowsky—one of the loudest voices in the field and author of the first assigned reading in Professor Aaronson’s course—is declaring the cause hopeless.

Thus, the students of AI Alignment Theory began their semester by reading a laundry list of critical problems in AI Alignment research, how failure to solve those problems will result in catastrophic consequences, and the reasons to be pessimistic about both past and future progress on these problems. The essay by Eliezer, titled AGI Ruin: A List of Lethalities and posted to his popular community-driven website LessWrong in 2022, is divided into three sections.

Section A roughly describes the magnitude of the AI Alignment problem. That is, the magnitude of the consequences for a complete failure to align an AGI system to human values before construction. It posits that AGI would quickly catch up to all human knowledge simply by learning from existing human productions (colloquially referred to as “eating the internet”) and then, nearly as quickly, begin to meaningfully surpass human knowledge. AlphaGo Zero is presented as a model both for how this might happen, and how it might be difficult to correctly predict beforehand. Many believed that AlphaGo’s success in the board game Go was chiefly attributed to its ability to learn from the extensive history of human-played games. Less than a year after AlphaGo beat the best human player, the successor system AlphaGo Zero surpassed the original AlphaGo. Unlike its predecessor, AlphaGo Zero was trained in just three days by exclusively playing against itself without seeing a single human game.

This quick ramp from AGI to super-intelligence would pose a different sort of problem than humans are generally used to dealing with. Unlike traditional problems in science and engineering, the consequence for a failed attempt might not leave room for another try. An intelligent entity with a misaligned goal would be well aware that it stands in opposition to humans, and might act deceitfully until in a position to act openly against humans without jeopardizing its own survival. Since most goals benefit from control of power and resources, it seems likely that nearly any goal-driven intelligence would have ample opportunity to be misaligned with human desires.

Section B describes reasons why, by default, any AGI that humans build using current methods is likely to be unaligned even if considerable attention is paid to the topic. This “current method” is gradient descent. That is, incremental progress with respect to some loss function which “punishes” a model for undesirable behavior. A notoriously elusive property of such trained models is the ability to generalize out of their training distributions. To train a primitive model to be aligned to humans might involve learning a great many behavioral rules. However, the sorts of rules needed to keep a drastically smarter agent in check might not always be relevant to simpler models (e.g., “do not emotionally dysregulate humans you speak with” might not be relevant to a simpler model that is less able to reliably get under the skin of humans it operates with, or which is assigned tasks in training which do not benefit from such anti-social behavior).

Eliezer focuses on the misalignment of humans with their creators (evolution or evolutionary pressures) as a critical data point for reasoning about misaligned intelligent systems. Despite being a generally slow process, evolution eventually created a runaway intelligent system (Homo sapiens) which proceeded to dominate the globe, decimate related species, and eventually (it is forecasted) effectuate population decline. That last development is arguably in opposition to the sole imperative demanded by evolution: to reproduce.

Section B also makes time for criticism of the most popular paths toward AI alignment, including interpretability (unworkable, and attempting to train on it evokes Goodhart’s law, incentivizing deceit), using multiple AIs to maintain a balance of power (it is not clear how multiple strong AIs unaligned with humanity results in better outcomes for the weak humans), and corrigibility (it seems impossible to motivate an AI system to effect outcomes without also motivating it to desire its own survival to effectuate said outcomes).

Section C describes a bleak state of affairs in which veterans in AI alignment are unsatisfied with current progress and do not have a plan to deliver tangible solutions before the advent of AGI systems. In particular, Eliezer describes recent results as showy but useless. He believes that even with additional funding, the lack of appropriate evaluation mechanisms will prevent the most effective researchers from rising to the top.

A summary of the landscape, as described by Eliezer, in the flowchart below.

Figure 1: A flow chart of (select) paths described by Eliezer in his essay. A common feature of this flow chart is that many “good states”—such as disabling a misbehaving AGI or choosing not to build an AGI—are not “final” states in the sense that they are not permanent solutions. Such a state merely represent the avoidance of a single potential disaster, rather than the emergence of a new stable world state. Hence, these nodes posses back-arrows.

Despite the bleak content, Eliezer’s colorful prose inspired a lively class discussion. Before this discussion started, a survey was taken of the class’s predictions for various outcomes of the AGI in the coming years (with the full results below in figure 2). This survey asked students for their opinion of a number of statements. Each of these individual statement, if true, would reduce concerns of catastrophic AI-driven disasters. For example, when asked “How much do you agree with the statement: Humans will choose to not build AGI” half of respondents said they strongly disagreed with high confidence (agreement = 1, confidence = 5). Students also generally disagreed with the statements:

• “AGI will not be technically feasible in our lifetime”
• “(hyper-)AGI will not make extremely obviously unethical decisions”
• “No reason is individually sufficient, but taken together they provide justification to not fear AGI”

There was a divergence in responses regarding interpretability, corrigibility, and “other” AI alignment research. In the latter two cases, a plurality of respondents (about a quarter) agreed strongly with statements that such research would defang AGI (agreement = 4, confidence=4), while most other responses express various levels of agreement with low confidence. However, when asked about the likelihood of interpretability research defanging AI, the pessimistic voices were more united. A quarter of responses still expressed the same optimism, but roughly half expressed pessimism (agreement ≤ 2) with half of those expressing at least moderate confidence (confidence ≥ 4). Based on the following discussion, this might have been caused by more familiarity with interpretability research, including first-hand experience.

The only statement with general agreement was “(hyper-)AGI will understand human intentions better than we can code it.” However, it should be noted that no statement such as “AGI will respect human desires, as it understand them” was asked on the survey.

Figure 2: Class Survey Results; conducted before a class-wide discussion. Note that students were instructed to answer confidence = 1 when they had not previously considered the statement, to answer confidence = 3 when they felt there were strong arguments on both sides, and to answer confidence = 5 when they possessed well-considered resolve.

After the survey was completed, the results were displayed as an open discussion began. Similar to recent empirical research from frontier labs, interpretability research received more airtime than in Eliezer’s article. Students disagreed first about the definition of interpretability: whether it refers to the ability to interpret a model’s behavior solely by its weights, to interpration via repeated probing of the model in a sandbox, or whether it can also refer to the modern chain-of-thought traces. Regardless of how it was defined, however, participants were either pessimistic or very pessimistic about interpretability research broadly. One student criticized common misunderstandings of chain of thought. Rather than being a verbatim copy of the models internal dialog, it is instead a superficial summary of the complete thought state and routinely produced gibberish, such as rarely used Chinese characters in the middle of otherwise English reasoning.

A popular topic was the exact shape and speed of a recursive self-improvement loop. If it takes place slowly, then what might we learn from “near misses” such as the Hugging Face incident? The number of near misses we are able to learn from before AI possesses sufficient power to prevent further iterations could depend on this curve, with some students arguing that the sheer number of humans, as well as their default robustness in the physical world compared to AI systems means that AI-driven extinction events are still a long way off. Bolstering this “slow take-off” opinion are rumors that AI already plays a major role in model development which could be interpreted as the start of this process.

Some criticized a focus on “solving ethics” as a needlessly high bar that distracts from the more mundane tasks dominating AI alignment work. In particular, the student volunteer who presented this paper (and the author of this report) included a section on “Ethical Dilemmas” in their presentation. Among arguments against focusing on abstract moral philosophy, Professor Aaronson cites Eliezer to emphasize that any alignment at all is difficult, not just in morally gray cases:

When I say that alignment is difficult, I mean that in practice, using the techniques we actually have, “please don’t disassemble literally everyone with probability roughly 1” is an overly large ask that we are not on course to get.

In response, I argue that some examination of everyday decisions with a critical lens—such as telling white lies to loved ones or consuming animal products—can help disabuse us of the notion that goodness emerges in every sufficiently intelligent agent.

One of the most interesting discussions was about the difference between state-of-the-art LLMs and the theorized AI agents long discussed in rationalist discourse. Since current LLMs “mimic the human distribution,” they come preloaded with extensive understanding of human social norms and moral behavior. This makes constitutional alignment (the current practices of using system prompts to establish ground rules) extremely effective. This might either fundamentally change the orthogonality thesis, or provide a new tool to better approximate human judgment in complicated situations.

Of all the points made, the one I found most interesting was simply (paraphrased):

I think human-alignment is just very tractable

Here, “human-alignment” refers not to AI alignment with human values, but cooperation between different humans. More specifically, it refers to the ability for human societies to choose not to rush recklessly into larger-and-larger AI systems. In an academic course focused on the technical problem of AI alignment, this was a reminder to not completely discard policy discussions in the believe that they lack any value. After all, many destructive technologies have been previously contained by international agreements. Notable examples include nuclear weapons and engineered plagues. However, even this was a contentious topic. The main criticisms were (1) the extreme “dual-use” nature of AIs for both peaceful growth and warfare, and (2) the greater danger for AI escapes even after taking precautions to prevent it. However, in the interest of ending on an optimistic note—unlike the assigned reading—it is on this belief in human cooperation that I will leave you.

By Scott

(This was written about 9 months ago.  Its not out of date... yet)

People think that AI is going to DESTROY some jobs and CREATE some jobs. It may be too early to tell if this is true. Even so, here are some thoughts. 

1) Who will win? Who will lose?

2) Historically in the long term society was better off after a tech change (e.g., we live longer now than we did in the farm-era). Will that happen here as well?

3) We have some sense of what kinds of jobs will be destroyed. But what kind will be created? Will they be interesting? See later in this blog for a job you might not have thought of. 

4) Many jobs will change.  If you are over X years old then think about how much technology has changed your job even before the AI revolution. (The value of X may vary depending on how high-tech you are.) 

For an intelligent view of the questions above, see here.

For my view of one aspect of this, read on. 

There is one job which has been either created or expanded by AI:

Annotator.

(See here for an ARTICLE about these jobs, from which I got most of the rest of this post. The word ARTICLE is in caps so when I refer to it later you'll know what I am referring to.) 

The job consists of looking at pictures and labeling things.

Here is a direct quote from the manual: 

LABEL real items that can be worn by real people.

Does Lady Gaga count as a real person? She sometimes wears dresses made of meat. Should that count?  See here for a real article about her and see here for the Weird Al parody of Born that Way. Note that this is Weird AL, not Weird Artificial Intelligence. (See here for the Weird AI for Weird AL problem.)

They do this to create data for AI.

a) The jobs don't pay well though there are some exceptions.

b) The jobs are boring though there are some exceptions (and that may depend on the worker). 

c) This job is needed because AI keeps running into edge cases. This may have happened with AI's attempts to solve my GROUP ONE-GROUP TWO prez-VP problem from a prior blog post here  or my baseball-brother-pitchers post here.

c) KEY: People in AI used to think this is a temporary thing and these jobs will soon be automated. This might not  be the case. There are SO MANY edge cases that AI encounters. The more we expect from AI the more edge cases there will be.

A quote from page 26 (of the ARTICLE pointed to above) which is informative if you can parse it. I think. 

Put another way, ChatGPT seems so human because it was trained by an AI that was mimicking humans who were rating an AI that was mimicking humans who were pretending to be a better version of an AI that was trained on human writing.

By gasarch

U. Colorado Boulder CS seeks applications for a TT Asst. Prof. position in Quantum Computation. We invite applications from all areas of QC; priority consideration will be given to:

– Quantum computation theory: quantum algorithms, quantum complexity, quantum information, & quantum error correcting codes
– Applications of QC to important or emerging areas such as quantum optimization & quantum ML

Website: https://jobs.colorado.edu/jobs/JobDetail/Tenure-Track-Faculty-in-Quantum-Computation/74741
Email: jgrochow@colorado.edu

By shacharlovett

My host at Brown University was the fascinating Basilis Gidas whom I first met in Rio in 2018. Basilis has had a remarkable career, taking him from electrical and mechanical engineering through quantum field theory to many areas of applied mathematics. In the context of AI, Basilis told me about a well-known passage in Plato—new to me—expressing concern that reliance on writing (new technology at the time) would weaken human memory. Overall, Basilis thinks that the most creative aspects of mathematics will remain human.

I had a wonderful and very intense time in Providence, where I gave an applied mathematics colloquium on my work on quantum computing. During my visit, I met and talked with quite a few mathematicians, chemists, physicists, computer scientists, and an economist Oded Galor.

Regarding quantum computation, I heard many excellent new questions about my point of view (I have collected earlier questions in this post), and learned about topics in chemistry and physics closely related to my work. I still have quite a bit to digest from these conversations. I also had a lovely dinner discussion about the notorious “measurement problem.”

Here are the slides of my talk: The Quantum Computer – A Miracle or Mirage.

The talk has five parts, and the audience and I concentrated on the second, devoted to my conjectures on correlated errors.

A few days ago I uploaded to the arXiv my paper The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective, that is going to appear in: Fields of Logic and Computation IV: Essays dedicated to Yuri Gurevich, editted by: Guillermo Badia, Manfred Droste, Andreas Blass, and Nachum Dershowitz. (I noticed two even newer papers on the arXiv, on quantum cryptography by Yael Kalai!)

Of course, I also learned about advances in computer science and mathematics close to my other interests, heard new perspectives on the AI revolution in mathematics and the emotions it evokes, reconnected with old friends, and made some new ones. Let me mention Eli Upfal, now a distinguished computer scientist. Eli and I were graduate students at HUJI at the same time (he studied with Eli Shamir), and I had not seen him for several decades.

Greetings from Boston! For those who attended my talk here on “algebraic shifting,” here are the handouts. (There were not enough copies for everybody.) I plan to return to my Boston visit and to algebraic shifting a little later.

A bit of nostalgia: Providence was the first US city I set foot in, in 1978. It was my first trip outside Israel: I spent two weeks at a summer school in Montreal, then got a lift to Providence, where I took a bus to Boston. My hosts in Boston, Israeli sailing champions, took me sailing on the (then polluted) Charles River. They invited me to take the helm, and shortly afterward we all found ourselves in the water.

By Gil Kalai

Max Planck Institute for Informatics (Saarbrücken) seeks Postdocs and Group Leaders in Algorithms & Complexity and related areas. Flexible start dates; strong research environment and travel support. Apply by 15 Dec 2026 with CV, publications, research plan, and 3 references.

Website: https://www.mpi-inf.mpg.de/d1/offers/postdoc
Email: join-d1@mpi-inf.mpg.de

By shacharlovett

Authors: Omar Al-Ghattas, David Gamarnik, Bobak T Kiani

Authors: Daniel Grier, Jackson Morris, Kewen Wu

Authors: Benoît Dubus, Julien Ladeuze, Jérémie Roland

Authors: Shaowei Cai, Ziqun Li

Authors: Alessandro Chiesa, Ziyi Guan, Burcu Yildiz

Authors: Minki Hhan, Hojune Lee

Authors: Isaac Rudich, Louis-Martin Rousseau

Authors: Tymoteusz Kucharek, Piotr Hofman

Authors: Kishor Bharti

Authors: Shuo Pang

Authors: Jin-Yi Cai, Zhuxiao Tang

Authors: Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas, James Worrell

Authors: Piotr Lange

Authors: Thomas Bläsius, Lennart Großkreutz, Jean-Pierre von der Heydt

Authors: Eunku Park

Authors: Dmitry Kamenetsky

Authors: Mingyang Gong, Adiesha Liyanage, Braeden Sopp, Muzhou Chen, Binhai Zhu

Authors: Jan Kynčl, Carolina Medina, Gelasio Salazar

Authors: Matthew Coudron, Michael J. Gullans, Jon Nelson, Joel Rajakumar, Shi Jie Samuel Tan

Authors: Eren C. Kızıldağ, Shuangping Li

Authors: Emile Anand

Authors: Han Zhong, Yinyu Ye

Authors: Wendao Wu, Cong Fang

Authors: Steef Hegeman, Joon Hyung Lee, Alfons Laarman

Authors: Thuy-Duong Vuong

Authors: Yaowei Long

Authors: Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizić-Nikolac, Lucas Pesenti, Robert Wang

Authors: Xiaohui Bei, Zhihao Gavin Tang, Wenhao Wu

Authors: Gabriel Marques Domingues

Authors: Chandrima Kayal, Sayantan Sen, Dániel Szabó

Authors: Yu Deng, Xinyi Yang, Keren Zhu

Authors: Marek Gałązka, Hanna Wdowicka

Authors: Anthony Dugois, Vincent Fagnon, Giorgio Lucarelli

Authors: Egor Gorbachev

Authors: Xinyu Wang, Ziyu Zhao, Yixuan He, Xiaowen Chang Alex Smola

Authors: Sepehr Assadi, Janani Sundaresan

Authors: Laura Toma

Authors: Joshua A. Grochow, Gábor Ivanyos, Youming Qiao, Xiaorui Sun

Authors: Slobodan Mitrović, Theodore Pan

Authors: Amir Azarmehr, Michael A. Bender, William Kuszmaul, Rose Silver

Authors: Koustav De, Debajyoti Kar, Swagato Sanyal

Authors: Priyanshi Agrawal, Balagopal Komarath

Authors: Floris Geerts, Rihan Hai, Matthias Lanzinger, Reinhard Pichler, Emanuel Sallinger, Daniel Unterberger

Authors: Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh

Hi there, argmin readers! Today’s post is a live blog of Class 9 of my graduate seminar “Forecasting: A Critical Retrospective.” The syllabus and list of past posts are here.

Every class I teach seems to require a lecture or two on expected utility maximization. It’s the basis of classification rules, so it’s integral to machine learning classes. It’s the simplest stochastic optimization problem, so it appears in my optimization classes. It’s a great motivator for probabilistic thinking, so it appears in probability classes. Perhaps a bit less well appreciated, it’s an indirect proper scoring rule for forecasts, so we have to talk about it in this class. And, I suppose, it’s a mathematical tool that scarily dominates the philosophy of many powerful people in government and industry alike. It’s worth understanding the nuts and bolts!

Part of what makes utility maximization so appealing is how simple the core idea is. We want to decide whether to act or not. We build a probabilistic model of the world under the action and compute the expected value of the benefit. We also build a model for what would happen if we don’t act and compute the expected value of the benefit of inaction. We choose to act if our calculations imply that action has more benefit than inaction.

What could be simpler? You compute probabilities. You compute costs. You multiply them together and add them up. Everything is beautifully quantified and calculable.

The only problem is these numbers are all made up. They are forecasts, and they are rarely justifiable. Outside of the casino, we rarely know how to calculate precise odds of outcomes. Worse, forecasting the prices out in the future is also inherently uncertain, often more uncertain than the odds calculations. Maximizing the utility of a rational actor or a general population is an appealing philosophical goal, but the precise rational calculations are always made about fantasy stories. Economists know this, and proceed with caution. In the comments of Tuesday’s post, Jordan Ellenberg flagged this quote from John Maynard Keynes.

“By ‘uncertain’ knowledge, let me explain, I do not mean merely to distinguish what is known for certain from what is only probable. The game of roulette is not subject, in this sense, to uncertainty… Even the weather is only moderately uncertain. The sense in which I am using the term is that in which the prospect of a European war is uncertain, or the price of copper and the rate of interest twenty years hence, or the obsolescence of a new invention, or the position of private wealthowners in the social system in 1970. About these matters there is no scientific basis on which to form any calculable probability whatever. We simply do not know. Nevertheless, the necessity for action and for decision compels us as practical men to do our best to overlook this awkward fact and to behave exactly as we should if we had behind us a good Benthamite calculation of a series of prospective advantages and disadvantages, each multiplied by its appropriate probability, waiting to be summed.”

Keynes here seems to be reluctantly defending utility maximization as the best of many bad options for decision making in the face of uncertainty. But I don’t think that’s his point at all! Keynes is defending his “General Theory of Employment” and arguing against this sort of utilitarian calculation.

As it is colloquially known, “Keynesian economics” — a term that sadly oversimplifies Keynes’ brilliant collected works — tells governments to stimulate economies during recessions. Keynes argues that we can’t accurately predict the future, and hence people tend to lean on status-quo bias. The safest bet is to assume nothing changes. But when the status quo is bad, people become risk-averse and hold their money. This hoarding prolongs recessions. Because the future is uncertain, people don’t act “rationally” when they fear they might not have money to spend later. Keynes thus argues that governments should step in to nudge citizens out of their undue pessimism by giving them extra money to spend.

Written in the pits of the Great Depression, Keynes’ argument in his 1937 article in the Quarterly Journal of Economics articulates how utility maximization goes wrong. The future is unknowable. Uncertainty makes people afraid. Fear makes hoarding more attractive. Mass hoarding perpetuates a vicious cycle of societal hardship. At this point, someone needs to step in to get the ball rolling, eating up some of the risk to inspire more confidence in people to spend their money.

In this class, we’re not going to debate the merits and challenges of recessionary stimulus spending. But Keynes’ article (which I have added to the reading list) articulates the nuance of forecasting under great uncertainty. Human psychology plays a key role. Today we’ll go through how this appears in the mathematics, with different utility functions expressing different models of risk aversion, and different algorithms for action. We’ll see that not only are the costs and benefits uncertain, but the algorithm itself can be shaped by different models of psychology. Expected utility maximization might be a reasonable way to engineer machines, but it’s not something that reasonable people do. Understanding the many hyperparameters of optimal decision making can help us better understand the psychology of people obsessed with forecasting.

Subscribe now

By Ben Recht

Authors: Atul Singh Arora, Shantanav Chakraborty, Alexandru Cojocaru, Sreyas Saminathan, Uttam Singh

Authors: Oren Renard, Nicholas Spooner

Authors: Bireswar Das, Udit Kumar, Kavita Samant, Dhara Thakkar

Authors: Dorian Rudolph, Arsalan Motamedi, Dhruva Sambrani, Hamid Reza Naeij, Ulysse Chabaud, Sevag Gharibian, Saeed Mehraban

Authors: Juntai Zhou, Felix Leditzky

Authors: Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu

Authors: Adrian Wurm

Authors: Alex Della Schiava, Ranitha Mataraarachchi