Theory of Computing Report

The following conversation is fictional.

---------------------------

ALICE: (Looking over a student's record.) Hmm, let's see. She wants to work in quantum computing. She's had the year-long quantum sequence in the physics department and has taken a course in quantum computing in the computer science department. She has done a project in quantum computing in an REU program.  Grades good, letters good. I think we should admit her.

BOB: Wait! Did she get a minor in Physics? This is very important!

--------------------------

When looking over a student's record the questions

Does she have a minor in X? or

Did she double major?  or

Did she graduate with honors? 

never dawn on me.

1) When I am on an admissions committee I look at:

a) Transcript: What did they take? The grades are generally good so that's a minor factor.

b) Letters that tell me what they did within STEM. I don't care about ballroom dancing or moral character. 

c) Papers they've written whether or not they have been published.

d) Their personal statement. They need to tell me:

i) Why they want to get a PhD.  When Ted Kennedy challenged Jimmy Carter for the presidential nomination in 1980, Ted Kennedy was asked Why do you want to be president? See here for his rambling and incoherent answer.

Despite his background in proving lower bounds on approximation contingent on the Unique Games Conjecture, Ted Kennedy would not have gotten into our graduate program.

ii) What they are interested in (this may have been covered in part (i)).

iii) Why they are qualified.

2) Do I care what the major is? No. I care that they know computer science which I can get off of their transcript.

3) Do I care if they double major in (say) Math. No. I can look at the transcript and see what math courses they took.  I don't care what (possibly arbitrary) rules their school has for double majoring.

4) Do I care if they minored in (say) physics? Not even a little. If they want to do quantum computing I care if they have taken courses in that area.  I don't care what (likely arbitrary) rules their school has for minors.  I took five courses in Philosophy as an undergraduate. Did I get a minor? I don't recall.  Two of them were in logic so I don't think I deserve a minor.

5) Are they in their school's CS honors program? Some other honor program? Are they on track to graduate with CS honors? Some other honors?  I don't care what (definitely arbitrary) rules their school has for honors programs.  If they are writing a paper, honors thesis or not, I will want to hear about it from their letter writer and from their personal statement. 

6) Do I care if they are in phi-beta-kappa? Sigma-Xi? Tau-Beta-Pi?  The last two I only know about since I googled  is there an analog of phi-beta-kappa geared toward STEM  for this post. You can probably guess that I don't care about any of those things. 

7) The point is that these formal criteria: major, minor, honors are not important when I am doing admissions.

a) Are they important to students?

I've heard that high school students who are honors students get a bumper sticker for their parents car that says:

                 My kid is an honors student at blah high school.

I would be more impressed if the bumper sticker said

                 My kid can prove the polynomial van der Waerden theorem.

b) Are they important to other people on the admissions committee?

8) Has the scenario I paint at the beginning of this post ever happened?

By gasarch

Assume indistinguishability obfuscation (iO) and one-way functions, both secure against nonuniform polynomial-size adversaries. We show that no randomized polynomial-size pruning procedure isolates a witness with probability at least a/log L, for any constant a > 0, where L is the length of the circuit description. Dell, Kabanets, van Melkebeek, and Watanabe (DKMW) proved without cryptographic assumptions that success 2/3 + 1/poly(L) implies NP ? P/poly. Under iO alone we get the same collapse from success a/log L, and the guarantee only has to hold on nonempty affine-subspace inputs. The isolator is given no affine basis, it may use the circuit description in any way, and the obfuscator may have negligible correctness error. The reduction hides a known affine subspace inside a larger solution space whose dimension does not depend on the scale being tested. Obfuscation then lets us compare the isolator's output, computationally, with an independent reference output. Along the way we prove an unconditional preprocessing criterion. It characterizes presentation-invariant isolation and, unless NP ? P/poly, gives common and efficiently testable witnesses that a constant-success isolator depends on the presentation. For isolators that see the target only through adaptive membership queries, we determine the optimal tradeoff between queries and success up to absolute constants. Finally, a matching restriction-law construction shows why tests on the planted region stop at the logarithmic scale.

Local LCL properties [Levi, Mosheiff, and Shagrithaya (LMS), FOCS 2025] give a language to express a broad range of linear properties of codes. Subspace design [Guruswami and Xing, 2013] is an elegant property about the linear structure of codes, and it governs important code behavior. In this note, we show that the subspace design property can be phrased as an LCL property. This allows us to recover the recent Goyal, Guruswami, and Hsieh result of constant-alphabet subspace-design codes from the earlier LCL derandomization framework [Jeronimo--Shagrithaya (JS), STOC 2026], with the same coarse alphabet dependence.

We prove that every finite two-player game $G$ with entangled value $\omega^*(G)=1-\epsilon$ satisfies \[ \omega^*(G^{\otimes n}) \le\exp(-\Omega(\frac{\epsilon^3}{\epsilon+ \ell }n)) \] for every $n\ge1$, where $\ell:=\log(|A| |B|)$, and $A$ and $B$ are the answer alphabets. Compared with Chapter 6 of the OpenAI report [Ope26], this improves the gap exponent from thirteen to three and matches the cubic gap dependence in Holenstein's general classical bound [Hol09]: \[ \omega(G^{\otimes n})\le\exp(-\Omega( \frac{ (1-\omega(G))^3}{1+\ell} n)). \] The proof replaces the randomly shifted logarithmic grid used in quantum correlated sampling by smooth soft labels. This makes the relevant label infidelity quadratic in the distance between state descriptions and avoids a Jensen loss when averaging over questions. Together with the postselection argument, these improvements yield the cubic gap dependence stated above.

Let f be a product of D generic linear forms in m variables over a field of characteristic 0, and for integers k, l >= 0 let Gamma_{k,l}(f) = dim S_l * partial^k f be its shifted partial derivative measure, the complexity measure behind the known lower bounds for homogeneous depth-four algebraic circuits. Two universal upper bounds hold for every homogeneous f of degree D: Gamma_{k,l}(f) = 0. For every fixed m >= 3 we prove that for all (k,l) and all D >= D_0(m,k,l) = poly(k,l), a generic product of D linear forms satisfies Gamma_{k,l}(f) = min(N_k N_l, N_{D-k+l}) -- full saturation of the universal cap. For derivative spaces (l = 0) we prove exact equality dim partial^k f = min(N_k, N_{D-k}) for all k = D - D/m, and (once D >= 2m^2) within a factor (2/e)^{m-1}/(2e^2 m) of the cap at every k, via a standalone combinatorial comparison lemma for capped compositions (a Polya-urn coupling plus log-concavity). We also compute exactly, by a filtration calculus, the measure of products with disjoint-pair block structure, and show these are genuinely deficient in the row-dominated regime -- for even m >= 6 and k = l >= m^2, by a factor at least (k/32m)^{(m-4)/2} -- witness choice, not analysis slack, is what previously kept this regime open. The complexity-theoretic reading: against a single product gate of generic linear forms in any fixed number of variables, shifted partial derivatives certify nothing beyond a polynomial degree threshold. This is an exact, per-gate form of the saturation phenomenon underlying the rank-measure barriers of Efremenko-Landsberg-Schenck-Weyman, Efremenko-Garg-Oliveira-Wigderson, and Bhargav-Dutta-Saxena, here established with exact constants in the few-variable, high-degree regime relevant to algebraic hardness-randomness bootstrapping. Characteristic 0 is essential: over small finite fields the evaluation variant of the measure (Armand-Behera-Tavenas, 2026) reverses the polarity. The commutative-algebra reading: we determine the Hilbert function of the ideal generated by partial^k f in each degree k+l -- for f a generic hyperplane multi-arrangement form -- extending the study of apolar algebras of products of linear forms initiated by DiPasquale-Flores-Peterson. The proofs are elementary throughout (no recourse to Froberg-type conjectures or Alexander-Hirschowitz): the main theorem reduces, by an exact "master reduction," to the rank of an explicit Laurent-polynomial family, which is resolved by a zero-multiplicity bound for exponential polynomials, layered confluent and twist Vandermonde arguments, and a residual core lemma valid over any field. Every machine-checkable step of the derivation has been verified exactly (integer or modular arithmetic, multiple primes and seeds), including the full generic-m code path at m = 4, ..., 9.

For several reasons, I have attended very few conferences and workshops for quite a while. However, I made an exception for GandALF 2026, which was held in Aalborg in the period 15-17 September 2026. I am glad that I did so.  

By Luca Aceto

We provide a digest of the paper of Fei and Rubinfeld (arXiv 2026), which provides an alternative analysis of the Bipartite Tester of Goldreich and Ron ({\em Combinatorica}, 1999), which operates in the bounded-degree graph model. Loosely speaking, on input an $n$-vertex graph $G$, the tester selects few vertices, conducts $\tildeO(n^{1/2})$ random walks of polylogarithmic length from each selected vertex, and rejects if and only if an odd cycle is formed by a pair of walks. While the analysis of the foregoing tester in the rapid-mixing case is quite appealing, the original analysis of the general case is quite imposing; it involves the introduction and analysis of Markov Chains that capture the behavior of random walks on a sequence of residual subgraphs that are iteratively defined by the analysis. In contrast, Fei and Rubinfeld avoid this iterative process, and present an analysis that only refers to the random walks on the input graph. More specifically, the original analysis derives a sequence of (non-overlapping) partial 2-partitions of the graph, and stitches them together. In contrast, the new analysis combines a set of ``fractional'' 2-partitions of the entire graph, where the combination is obtained by defining adequate vectors that represent these fractional 2-partitions and employing randomized rounding (a la Goemans and Williamson ({\em JACM}, 1995)). In addition, the new analysis allows for presenting an extremely efficient interactive proof of proximity for Bipartiteness. Such an interactive proof was known before for the rapid-mixing case (Rothblum, Vadhan, and Wigderson ({\em STOC}, 2013)).

For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement "$y\not\in\mathrm{Range}(G)$" for every $y \in \{0, 1\}^N$, and $G$ is a *demi-bits generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the statement "$y \not\in\mathrm{Range}(G)$" for a noticeable fraction of $y \in \{0, 1\}^N$. As can be seen from the definitions, proof complexity generators are qualitatively stronger objects than demi-bits generators. Our main result is that, perhaps counter-intuitively, every demi-bits generator "contains" exponentially many proof complexity generators. In fact, a random subset of output bits of a demi-bits generator forms a proof complexity generator with constant probability. This result is an extremely simple corollary of Pajor's Lemma (a strengthening of the well-known Sauer--Shelah Lemma). This result allows us to exhibit the hardness of the Range Avoidance problem ($\text{Avoid}$) in several new, restricted settings of interest: * We show that demi-bits generators computable in $\text{NC}^0$ implies the hardness of $\text{NC}^0$-$\text{Avoid}$ up to constant factors in the stretch, demonstrating a barrier to further improvements on the recent progress on this problem (Korten--Pitassi--Impagliazzo, FOCS'25; Guruswami--Lyu--Yuan, SODA'26). * Given a linear space $V\subseteq \mathrm{GF}(2)^n$ of dimension $k$, the $\text{XOR}$-$\text{Remote-Point}$ problem asks to find a vector far from $V$ (Alon--Panigrahy--Yekhanin, RANDOM'09). Assuming a demi-hardness version of LPN (Learning Parity with Noise), we show that $\text{XOR}$-$\text{Remote-Point}$ cannot be solved by efficient nondeterministic algorithms. * An intriguing challenge in circuit complexity is to build a partial Boolean function on a given domain that has high circuit complexity (Arvind--Srinivasan, ICS'10; Chen--Huang--Li--Ren, STOC'23). Even for hardness against *polynomial-size DNFs*, no efficient algorithm is known for this task. We show that under a version of the random $k$-SAT Hypothesis against $\text{AM}$ algorithms, such hard functions cannot be constructed in nondeterministic polynomial time. Along the way, we introduce the notion of *zero-error disperser families* that can transform demi-bits generators into proof complexity generators, and show that this family can be computed by projections (i.e., without any circuit complexity overhead). Using a different instantiation of this family, we construct proof complexity generators from *barely non-trivial* demi-bits generators $G: \{0, 1\}^n \to \{0, 1\}^N$, where the number of hard-to-prove statements of the form "$y \not \in \mathrm{Range}(G)$" just slightly exceeds $2^n$ (which is the number of *false* statements of this form).

Scott’s foreword: I’m extremely grateful to my brilliant colleagues, Pravesh Kothari, Raghu Meka, and Prasad Raghavendra, for sharing the guest post below about how theoretical computer science (and in particlar, the STOC/FOCS/SODA conferences) should evolve to deal with the AI asteroid that’s right now slamming into our field, at least as we human theorists have practiced it since its inception. While Pravesh, Raghu, and Prasad speak only for themselves, not for myself and not for the theory community as a whole, I found their proposal of a separate “conceptual track” to be an excellent starting point for further discussion. –SA

Considering the pace of developments in AI theorem provers, most would concede that the following scenario is at least plausible in the very near future:

AI theorem provers could prove well-specified mathematical claims, even many well-studied ones that have been open for years, in a matter of hours. Moreover, these systems could be widely available to consumers at nominal cost.

As TCS researchers, let us pretend that the above scenario has come to the fore, and ask ourselves: What is our role in such a world? Does it mean the end of theory research?

As we ponder this question, let us ignore all of these other confounders:

1. Recent controversies surrounding the developments on the Millennium Prize Problems
2. Motivations and actions of the AI companies
3. Observed faults in existing AI systems when it comes to writing, exposition or attribution to previous work.

None of the above confounders have any impact on our answer to the question: What should theorists do, in the presence of superhuman AI theorem provers?

Notice that we use the term “AI theorem provers” instead of just “AI”. We believe that this conceptual distinction is important as we consider this question.

At the outset, we would like to admit that for a generation of theorists like us (and many from earlier), research was mainly centered around problem-solving. Even when we developed conceptual insights, it was mostly in service of answering well-specified long-standing questions. We don’t intend this proposal as judging one form of research to be better than others; it only reflects that AI theorem provers accelerate a certain type of research activity and want to make the best of it. There is also a tremendous human cost of this upheaval, which is perhaps a more important question, and one which this proposal does not address directly (we do not have any good ideas as such). Similar points have also been made in various contexts
before, but the timing now is more pressing.

Definitions, Questions & Theories:

The goal of any theoretical science is to advance human understanding of observed phenomena. Apart from theorems and proofs, a theoretical science has definitions, questions, and theories.

Definitions identify the objects to observe. Curiosity and context drive the questions to ask. Theories explain the phenomena observed. We believe humans will continue to play a central role in generating definitions, questions & theories, even in the presence of a super-human AI theorem prover.

Definitions: Could an AI define randomness extractors, streaming algorithms, or zero-knowledge proofs? Maybe. But there are some reasons to believe, humans will still have a big role to play in coming up with definitions.

For instance, the notion of extractors arises from the real-world problem of lacking perfect random sources. Zero-knowledge proofs seem to arise purely out of human curiosity, guided by taste. Human context and curiosity will continue to drive theoretical research. After all, we get to decide what objects we choose to observe!

Theories: Consider the following thought experiment. Suppose in 1965, we had a magic machine that at the press of a button, given any computational problem, would tell us if it had a polynomial-time algorithm or not.

Would that have been the end of computational complexity theory? No. Humans would find it entirely unsatisfactory, and ask, why do these problems not have a polynomial-time algorithm? Why do these others have?

The theory of NP-completeness identifies some patterns among problems that don’t seem to have efficient algorithms. This theory would still be a crown jewel of theoretical computer science, even in a world where we had a magic machine to tell if a problem had an efficient algorithm or not, at the press of a button. Similarly, if we had a machine to predict whether a CSP is NP-complete or in P, we would then ask: what makes 3-SAT NP-complete, while 2-SAT is in P? This question leads to the theory of polymorphisms, which yields a satisfactory answer.

Theories aren’t just succinct or efficient mechanisms to answer questions. The best theories provide are those which humans deem to be a “satisfactory explanation” – whatever that means.

Finally, even as the capabilities of AI theorem provers advance, human curiosity will probe grander and deeper questions. Previously, even if we wanted to build new models and theories, proving something about them was a prerequisite, and given that the grand questions were already at the limit in long-studied domains, we had to scale things down. If each theorem proven by AI is treated as an experimental datapoint, humans can ask grander questions that look for patterns across these theorems.

A concrete proposal:

We think theorists should embrace these AI theorem provers in our research. To a certain extent this is already happening explicitly or implicitly.

As theorists, we have been parsimonious in introducing new models or asking entirely new questions, and careful about adopting new ones too quickly. This was partly because formally proving the properties of a new definition or a model was an onerous task that could take a decade, and tens of papers. AI theorem provers might completely change this dynamic. This is precisely the moment to refocus our work on definitions, questions, and theories. We need explicit systems to encourage and reinforce these parts of theoretical research. You might also say the next generation of AI models can do this; it may be so, but we believe you have to take the current opportunity.

To this end, we suggest that STOC/FOCS/SODA create a separate track of papers. This track is meant specifically for papers that introduce new definitions, ask novel questions or build explanatory theories. The papers in this track are short, say less than 10 pages. Papers may, and should, contain theorems as usual and as needed. Most importantly, the radical shift is that the papers need not contain the proofs of the theorems. Instead, the authors supply a Lean certificate as a supplement to the paper. The evaluation will also in a sense “orthogonalize’’ against the difficulty of these proofs.

The papers in this track should be judged exclusively on the conceptual merits, completely agnostic to the difficulty of the proofs.

Reviewing must be completely agnostic to the proof for two reasons. The main track at STOC/FOCS already includes papers in the former category. Second, a major barrier to producing truly novel conceptual papers is that they often get judged poorly for a lack of technical depth in their proofs. We think these two aspects separate it from (ITCS/SOSA) and, regardless, it’s something we urgently need for all our conferences, including STOC/FOCS (the ‘flagship’ conferences).

To be clear, we ourselves admit that we need to hone these skills of making new definitions, asking deep and interesting questions or building new theories. A separate track of conceptual papers will provide a systematic mechanism for both junior and senior researchers, and the field as a whole to do so.

We believe that upcoming generations of grad students will tackle research directions that seemed completely out of reach to us. We just need to set up systems that nurture new ways of doing research in theory.

— Pravesh Kothari, Raghu Meka, Prasad Raghavendra.

By Scott

Applications are invited for a postdoctoral position in Dean Doron’s group at Ben-Gurion University, supported by an ERC Starting Grant. Candidates interested in complexity theory and pseudorandomness, broadly construed, are welcome to apply.
Further details and application instructions are available on the website. You are also welcome to contact me with any questions before applying.

Website: https://deandoron.github.io/#derand
Email: deand@bgu.ac.il

By shacharlovett

We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.

Private information retrieval (PIR) inherently requires public-key cryptography. A recent line of work suggests that this barrier can be avoided in secret-key PIR, where the client first preprocesses an N-bit database and retains only a short secret key. This line of work has yielded communication O(N^\epsilon) for any constant \epsilon under the Learning Parity with Noise (LPN) assumption in a high-noise regime not known to imply public-key cryptography, and communication O(N^{1/2}) under one-way functions. Whether compression beyond N^{1/2} can be achieved without relying on structured assumptions such as LPN has remained open. We show that interaction enables polylogarithmic communication in the random oracle model. We construct a secret-key PIR protocol with O(log N ) rounds and polylogarithmic total communication. Alternatively, for any constant \epsilon, we obtain a constant-round protocol with communication O(N^\epsilon). We also obtain protocols with similar communication in the plain model under the weakest version of LPN, with maximal noise rate 1/2 ? o(1). Our main idea, inspired by the free-XOR technique for circuit garbling, is to make secret-key preprocessing homomorphic under XOR, while relying on security against related-key attacks.

An outstanding open problem asks if there exists a boolean matrix with unbounded sign-rank, but bounded randomised communication complexity. We make progress towards this question by proving lower bounds against real linear sketches (a model weaker than sign-rank): Alice and Bob send few linear measurements to a referee, who makes a decision based on the evaluation of a low-degree polynomial. Our proof uses the Combinatorial Nullstellensatz and the rank method from algebraic circuit complexity.

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.

Many readers have asked me to write about AI companies’ conquest of mathematics. Today’s post is a first, but by no means final, attempt at grappling with our new mathematical condition.

Early in my career, I was fortunate to get caught up in a fascinating research frenzy at the intersection of pure and applied math, the compressed sensing gold rush. Compressed sensing asked whether signals could be compressed at the time of measurement. Rather than sampling an image with a high-resolution camera and then compressing it to a JPEG, could we collect a number of samples equal to the number of bytes in the JPEG? Compressed sensing rested on deep mathematics from geometric functional analysis, convex geometry, and probability theory. It yielded multiple engineering artifacts, from faster MRI capture times to better systems for content recommendation.

Though we can see the influence of the field across many applied domains, the math of compressed sensing was never decidedly prescriptive. The theorems always assumed things about reality that couldn’t be verified or required measurement systems that were too costly or impractical. Yet the math of compressed sensing helped us focus on a shared narrative of design principles. It helped us design new algorithms. It helped us construct new measurement schemes that were robust to noise. It helped us map out which other system structures were amenable to compressive techniques. Pure math gave us a frame to see what was possible.

While this mathematical formalism was unreasonably effective, it came with a decidedly unhealthy downside. Shahar Mendelson best described this general problem of applied pure mathematics in a talk he gave at COLT 2014. Applied mathematicians often need to build a giant scaffolding of mathematical modeling to solve a problem. This scaffolding creates new mathematical puzzles that aren’t directly connected to the original problem of interest, but that entice problem solvers. You’ll then see dozens of follow-up papers solving the puzzles but forgetting the problem we cared about in the first place.

This is open problem culture, and it’s corrosive. It leads to trophy hunting, where people race to scoop each other, consult expert friends for secret insights, or steamroll each other with ever more complicated math.

This fetishization of puzzle-solving as genius has long been a destructive tendency in mathematics more broadly. It’s easy to get caught up in the thrill of it. Mathematics is arguably the most meritocratic academic discipline. There are set problems, and the people who solve them are the smart ones. Everyone forgets that the only reason problems confer status is that (a) they are currently unsolved and (b) enough mathematicians have decided these are worth solving. That (b) part is not meritocratic.

This is why many are confused and angry at the practicing mathematicians who try to explain that the discipline of mathematics is about understanding, not proving stuff. To many observers, even those who strive to become mathematicians, math seems set up as a competition from the get-go. It’s rote testing all the way up through college. Ace the SAT as a 7-year-old. Win the IMO gold as a 14-year-old. Max the Putnam Exam as a 19-year-old.

Your reward is the permission to work on whatever puzzles you want, without questions, for the rest of your life. There is no requirement for the winners to explain anything. Maybe they have to teach calculus, but they don’t have to do a good job at it.

From the outside, you can see why people think mathematics is just about winning those competitions and proving what is true. Math doesn’t send many outward signals that “understanding” is a core part of the pursuit. Most people see math as a quiz show culture. Math culture is ruthlessly competitive, and it makes a lot of people feel stupid.

The actions of many notable mathematicians have only lent credibility to their critics. Wars over credit and who gets there first have now ruined two of Clay’s Millennium Problems. This will have to change in light of recent events with AI companies solving math problems few thought they’d be able to. When computers do something we think they wouldn’t, the reaction should not be writing insanely long posts about how Eliezer Yudkowsky was right and the machines are going to kill everyone. Instead, we have to adjust our reference narrative about what we thought was true.

Indeed, I didn’t learn anything about fluid dynamics from OpenAI’s proposed solution to the Clay Millennium Prize Navier-Stokes problem. This problem is exactly the sort of puzzle artifact that I lamented above. The resolution of the Navier-Stokes problem itself tells us nothing about the dynamics of fluids that the equations attempt to model.

That said, I’ve learned a lot from the supposed resolution. I learned that the jump from rote IMO solving to the Millennium Prizes was much shorter than I expected. If you build an algorithm that’s good at solving IMO problems, and you present it with the right ingredients and computational resources, you can solve hard math problems too. That is, a lot of mathematics is training people to benchmaxx. We have already created a battery of tests, carefully tuned with the best psychometrics to find mathematical genius. Training computers to maximize those benchmarks ends up solving the benchmarks. What are millennium problems other than humanity’s final math exam?

This unfortunately makes a lot of sense with the benefit of hindsight!

If this is the lesson, there’s a funny takeaway. While it feels like you need to be an IMO prodigy to set foot in the mathematical arena, being a great IMO solver doesn’t mean you’ll become a great mathematician. For that, you need to bring other talents to bear. Despite the efforts of many smart and caring people, those talents remain ineffable. They certainly aren’t benchmarkable.

In an age of the decidedly anti-intellectual culture of artificial intelligence, mathematicians, both pure and applied, need to keep working to articulate what on earth those talents are. The statements so far, describing how mathematical programs are more than the truth values of their associated theorems, are a good start even if they are not met with universal acclaim. More need to chime in with stories about how mathematics, even the very pure variety, is valuable for scientists, engineers, and everyone else.

I can describe my own experience. Though I’m much less concerned with proving theorems than I was earlier in my career, I still consider myself an applied pure mathematician. Applied mathematics is a formal language that bridges two unbridgeable worlds. Mathematics is a deductive practice that combines axioms via a set of well-specified rules to generate lemmas, theorems, and corollaries. Empirical science and engineering are inductive. We confirm theories when they make correct predictions, willfully committing the logical fallacy of affirming the consequent. This does not make science wrong. It just means, as David Hume told us three hundred years ago, that mathematics can’t justify science.1

Applied mathematics is thus a logical language for describing inductive processes. It’s, um, unreasonably effective at this task. As captured above in my discussion of compressed sensing, it can never perfectly specify what you should do in practice. Instead, it acts as a form of linguistic technical drawing, allowing communities of scientists to build complex theories and engineers to build complex systems. Pure mathematics gives applied mathematicians new pens and brushes for those drawings.

This is why I like (and have been using throughout) Jordan Ellenberg’s term applied pure mathematics. Applied mathematics often just means the mathematics of partial differential equations. Applied pure mathematics is any application of any mathematics to anything outside of the closed world of mathematics itself. You never know which weird corner of the vast libraries of “apparently useless” mathematics will help you make sense of reality.

Let me give an example of unexpected brushwork from my time in the compressed sensing gold rush. Did I need to learn p-adic analysis as an undergrad? Maybe not, but it fixed a set of regularities and patterns in my head. I remembered Bochner’s theorem on locally compact abelian groups when Ali Rahimi and I were trying to make sense of our code generating random features. This turned into a very cool paper with a lot of practical impact. The web of facts I had gathered sitting through weird courses and reading esoteric math books shaped how I saw this applied machine learning problem. AI could likely make that connection today, but my personal education is still needed to create the prompt.

In the first lecture of my first college math course, the legendary Chicago Professor Paul Sally (IYKYK) barked that he wasn’t there to teach us facts, but to fix our brains. Sally dedicated his career to mathematics education, passionately broadening the conception of who could be a mathematician. Math wasn’t a competition for Sally. It was a way of seeing. It still can be, even if our computers now outcompete us.

Subscribe now

By Ben Recht

Authors: Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal, Aparna Gupte

Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman-Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampling and membership-oracle access to a set $A \subseteq \mathbb{F}_2^n$ with doubling constant at most $K$, our algorithm outputs a subspace of size at most $|A|$ whose $K^{O(1)}$ translates cover $A$. The algorithm runs in $\textsf{poly}(n,K)$ time. As applications, we obtain polynomial-time algorithms for a variety of learning problems, including quadratic Goldreich-Levin, improper agnostic tomography of stabilizer states, and tomography of quantum states with bounded stabilizer extent.

Authors: Haoyu Wang, Pei Wu

In this paper, we construct a total Boolean function with $\widetilde{O}(\log n)$ randomized communication protocol, while any monochromatic rectangle has density at most $O(2^{-\mathrm{poly}(n)})$. As a corollary, it gives the first total function separation for $\mathrm{BPP}\not\subseteq\mathrm{P}^{\mathrm{NP}}$ in the communication world. Inspired by Gavinsky's recent work (arXiv:2608.18784), our construction combines the cheat-sheet framework with fully linear PCPs.

Authors: Lorenzo Ciardo, Iris Hebbeker, Gideo Joubert, Jana Kreiß, Antoine Mottet

We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include Kneser graphs, $q$-Kneser graphs, and the complements of Johnson, Grassmann, and Hamming graphs. Our proof develops a spectral method for establishing non-contextuality of quantum polymorphisms. It combines an equality analysis of Roberson's bound on the projective packing number in terms of Schrijver's theta with a structural argument inspired by Erdős-Ko-Rado theory.

Authors: David Miloschewsky, Supartha Podder

Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.

Authors: Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang, Yukai Tang

We show that unless P = NP, there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical system with a linear controller. This settles one of the best-known open problems in control theory. The result holds in both continuous and discrete time. We also present a family of stabilizable linear dynamical systems for which no polynomial-time algorithm can write down a stabilizing controller in its standard representation.

Authors: Yimu Qiao, Lijia Yu, Ruichen Qiu, Xiao-Shan Gao

Transformers have emerged as the dominant architecture in sequence modeling, achieving remarkable success in natural language processing and reasoning tasks. While existing literature has established the Turing completeness of transformers under bounded input length, the reasoning power of a single transformer operating on inputs of unbounded length is not fully explored. In this paper, we theoretically investigate the reasoning limitations of a single transformer and the enhanced capabilities of agent systems. We show that a single fixed finite precision transformer cannot memorize certain Turing machines with inputs of arbitrary length, such as the arithmetic; and a single fixed infinite precision transformer trained with a random algorithm is not Turing complete with probability one under reasonable conditions. To overcome the limitation of a single transformer, we define a formal agent architecture consisting of decision, execution, and memory modules and show that for any Turing machine $\mathbb{T}$, there exists an agent that can memorize $\mathbb{T}$ and is computationally the same as $\mathbb{T}$. Thus, agents are Turing complete.

Authors: Yusuke Kobayashi, Bingkai Lin, Joseph Swernofsky

An instance of {\sc Pinwheel Packing} is a list of positive integers $a_1,\ldots,a_k$. A feasible schedule assigns one task to every integer time so that every interval of $a_i$ consecutive times contains task $i$. The instance is \emph{dense} when $\sum_i1/a_i=1$. We prove that {\sc Dense Pinwheel Packing} is NP-complete even when every period is encoded in unary and equal periods are listed as distinct tasks. Consequently, the usual binary-encoded problem is strongly NP-complete. Kleinberg and Mishra also prove NP-completeness \cite[Corollary~5.1]{KleinbergMishra2026}, but their reduction uses periods of exponential numerical size and therefore yields only weak NP-hardness. Our proof uses a direct reduction from triangle partition in a sparse tripartite graph. If each of the three parts of the source graph has $n$ vertices, the reduction produces $O(n^4\log^3 n)$ explicitly listed tasks, each with period $O(n^4\log^3 n)$; consequently, its full unary encoding has length $O(n^8\log^6 n)$.

Authors: Shyamal Patel

We show that there exists a class of boolean functions C such that $(i)$ there is a distribution-independent statistical query algorithm for learning C that makes a polynomial number of queries of inverse polynomial tolerance and $(ii)$ for any set of functions $Φ_1, \dots, Φ_r$ such that for all $f \in$ C we can write $f(x) = \text{sign} \left( \sum_{i = 1}^r w_i Φ_i(x) \right)$ for some set of weights $w_i \in \mathbb{R}$, we must have that $r \geq n^{ω(1)}$. This gives a superpolynomial separation between dimension complexity and the query complexity of distribution-free learning in the statistical query model, negatively answering a question of Feldman, Kamath, and Srebro [FKS26]. Our construction C is a subclass of DNFs, and the proof is a simple consequence of recent progress on agnostically learning conjunctions [DKR25,CPS26] and the work of Razborov and Sherstov on the sign rank of DNFs [RS10].

Authors: Bingkai Lin, Xin Zheng

We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size $k$. Let $n$ be the universe size, $m$ the number of available sets, and $|Γ|$ the explicit input length. We prove that, for some absolute constant $c>0$, distinguishing \[ \operatorname{opt}(Γ)\le k \quad\text{from}\quad \operatorname{opt}(Γ)>k\cdot\frac{c\log n}{k^2\log\log n} \] is $\mathsf{W[1]}$-hard. Assuming the Exponential Time Hypothesis, there is also an absolute constant $\varepsilon>0$ for which no deterministic algorithm solves this gap problem in time $f(k)|Γ|^{\varepsilon k}$, for any computable function $f$. For every fixed $α>0$, both hardness results hold even when $n=O((\log m)^{1+α})$, with constants allowed to depend on $α$. For fixed $k$, the gap is within an $O_k(\log\log n)$ factor of the greedy algorithm's guarantee. Under the Strong Exponential Time Hypothesis, we further rule out $o(\log n/\log\log n)$ approximation in time $O(|Γ|^{k-δ})$ for every fixed $k\ge 2$ and $δ>0$. Thus a near-logarithmic hardness factor persists even when the exponent is reduced from exhaustive search by only a fixed constant. The constant in this SETH hardness factor may depend on $k$ and $δ$.

Authors: Zhiyang Dou, Ang Zhao, Chen Peng, Minghao Guo, Haixu Wu, Cheng Lin, Yuan Liu, Junfeng Yao, Xiaohu Guo, Wenping Wang, Wojciech Matusik

Rigid-body interpenetration frequently occurs in procedurally assembled and generated scenes and must be removed before downstream applications such as physical simulation. We present S4R (Scaling for Rigid-Body Interpenetration Resolution), a scale-continuation method for static interpenetration repair. S4R first uniformly shrinks each body about a fixed reference center to a small initial scale, at which the layout is penetration-free, and then restores full scale through a sequence of minimum-norm convex contact quadratic programs (QPs) that target the linearized separation margin during continuation. Resolution thereby replaces one deep correction with a sequence of shallow-contact subproblems. A conservative scale-event bound and frozen-witness gap predictions cut the number of exact mesh queries; the continuation then ends with a full-scale evaluator check and bounded tail refinement. We evaluate S4R on Kubric, HY3D-Bench, and Thingi10K using a shared mesh-level evaluator and a unified per-scene timing protocol. In the main comparisons on all three benchmarks, up to N=5000 bodies, S4R reaches zero reported penetration with displacement that stays small and nearly independent of scene size, and at the lowest wall time within each hardware tier among the compared methods. A GPU implementation extends these results to large-scale scenes. Our code and data can be found on our project page: https://frank-zy-dou.github.io/projects/S4R/index.html.

Authors: Venkatesan Guruswami, Xuandi Ren

We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\bigl(\frac{\log n}{\log\log n}\bigr)^{1/k}$ in (Lin, 2019) and $(\log n)^{1/\operatorname{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the number of candidate sets. While the best approximation ratio is still $O(\log n)$ via the greedy algorithm, closing this $1/k$ gap in the exponent has been a longstanding open problem; we remove this loss via a simple direct reduction. The construction is self-contained and does not rely on the parameterized inapproximability hypothesis (PIH). Starting with sparse parameterized 2-CSP instances (Karthik, Marx, Pilipczuk, and Souza, 2024), we build a monotone CNF formula, which is equivalent to a SetCover instance. To obtain a $k$-versus-$h$ gap, the reduction enumerates all hash functions from $Σ$ to $[2h]$ and all unsatisfiable 2-CSP instances on the same constraint graph with alphabet $[2h]$. For each such instance, it asks for a certificate that the hashed label pairs are not all contained in that instance. Perfect hashing makes this enumeration efficient for $h=\log n/\log\log n$.

Authors: Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, José A. Soto, Victor Verdugo

We prove a $1/e$ guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online. In the known-matroid model, the result extends more generally to matroids admitting a finitary modular extension. Each element of a fixed optimal basis is selected with probability at least $1/e$. $\mathbf{\text{Concurrent Discovery Disclosure:}}$ The proof of the main result in this manuscript was obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM PDT. We then prepared this manuscript for public release, with the intent of uploading it on the morning of Thursday, September 17, 2026. In the early morning hours of September 17, while finalizing the submission, we discovered the manuscript https://arxiv.org/abs/2609.19118 of Abdi, Banihashem, Hajiaghayi, and Mittal, uploaded on September 16, 2026, which contains the same result via an essentially identical approach. We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era.

Authors: Debarati Das, Evangelos Kipouridis, Tomasz Kociumaka

For every $0 < \varepsilon \le 1$, we give a randomized $(3+\varepsilon)$-approximation to weighted edit distance when the costs form a metric on the alphabet augmented with a gap symbol. For strings of total length $N$, the running time is $\widetilde{O}(N^{8/5}/\varepsilon^{16/5})$, where $\widetilde{O}$ suppresses factors polynomial in $\log(N/\varepsilon)$. The dependence on $N$ matches that of the fastest known $(3+\varepsilon)$-approximation for unit-cost edit distance. The algorithm never underestimates the edit distance and achieves the approximation guarantee with inverse-polynomial failure probability in $N$. The running time bound assumes constant-time exact arithmetic operations and metric queries, and it is independent of the numerical range of the edit costs. We build on three tools: the sampling framework of Chakraborty, Das, Goldenberg, Koucký, and Saks (J. ACM, 2020), with subsequent refinements by Andoni (2020); Kuszmaul's removal of inexpensive characters (ICALP 2019); and Klein's data structure for distances in planar graphs (SODA 2005). Our new ingredients include, among others, a decomposition of one string into pieces of bounded length with highly structured total deletion costs. This decomposition lets us compare all pieces against a small family of substrings of the other string.

Authors: Xiaoyu Chen, Heng Guo, Eric Vigoda, Xiongxin Yang

We give an FPRAS for the permanent of an $n\times n$ $0/1$ matrix with running time $\widetilde{O}(n^{3.5}\varepsilon^{-2})$. Our algorithm extends to a strongly polynomial FPRAS for arbitrary nonnegative matrices, as in previous works. Jerrum, Sinclair, and Vigoda (2004) gave the first FPRAS for the permanent of a nonnegative matrix. The running time was subsequently improved to $\widetilde{O}(n^7)$ by Bezáková, Štefankovič, Vazirani, and Vigoda (2008), and recently to $\widetilde{O}(n^6)$ by Chen, Vigoda, and Yang (2026). We introduce a multicommodity-flow bound inspired by electrical flows, replacing the usual path-length factor by routing energy. For a boosted version of the classical JSV chain, we prove a relaxation-time bound of $O(n^3\log n)$ and show that stationary trajectories of this length estimate all stationary hole-pattern probabilities, yielding an $\widetilde O(n^5)$-time FPRAS algorithm. Our new hole-weighted slide (HWS) chain improves both bounds to $O(n^2\log n)$, yielding an $\widetilde O(n^4)$-time algorithm. Finally, we obtain the claimed $\widetilde O(n^{3.5})$ running time by using a subset of $\widetilde{O}(\sqrt{n})$ checkpoint temperatures in an iterated sequence of warm-starts to obtain initializations at every temperature.

Authors: Yu Cong, Chao Xu, Yi Zhou

We consider a large-scale incentive allocation problem where the entire trade-off curve between budget and profit has to be maintained approximately at all times. The application originally comes from assigning coupons to users of ride-sharing apps, where each user can have a limit on the number of coupons assigned to them. We consider a more general form, where the coupons for each user form a matroid, and the set of coupons assigned to each user must be an independent set. We show the entire trade-off curve can be maintained approximately in near real time.

Authors: Roie Levin

We show an information-theoretic lower bound of $Ω\left(\frac{\log n \log m}{\log \log n + \log \log m}\right)$ for online set cover against randomized algorithms, for all sufficiently large $m$ and $n$ satisfying $\log^2 n \leq m \leq 2^n$.

Authors: Sitan Chen, Liye Wang

A popular selling point of diffusion large language models (dLLMs) is their capacity for parallelism: the ability to generate sequences of text far more efficiently than autoregressive models, which require one forward pass per token. Yet among the many competing paradigms for dLLMs, from masked to uniform to Gaussian diffusion, principled understanding of how these different proposals compare in parallelism remains limited. In this work, we initiate a fine-grained comparison of the capacity for parallelism among these three leading approaches and prove the following: - Uniform and Gaussian diffusion can sample in a number of forward passes which scales with the dual total correlation of the underlying distribution, a measure of intrinsic complexity which can be much smaller than the context length. Previously, it was only known how to achieve this using masked diffusion. - For a certain family of random empirical measures, we show that $\widetildeΘ(\sqrt{d})$ forward passes are necessary and sufficient to sample using uniform or Gaussian diffusion, yet there exist approximate score oracles for which $\widetildeΩ(d)$ forward passes are needed for masked diffusion. This establishes the first provable separation in parallelism between the three prevailing dLLM paradigms. Contrary to popular intuition that masked diffusions are harder to parallelize because they must commit to token values, the latter separation instead comes from the fact that the critical windows in masked diffusion sampling are asymptotically narrower than those in uniform and Gaussian diffusion sampling.

Authors: Heng Guo, Hongyang Liu, Xiongxin Yang, Yitong Yin, Yiyao Zhang

In this note, we give a simple analysis of a non-adaptive simulated annealing algorithm for estimating the partition function of Gibbs distributions. This yields the most efficient reduction of this kind so far. We also establish lower bounds for both general and non-adaptive algorithms, showing that our algorithm is optimal over a broad range of parameters.

Authors: Eric Angel, Evangelos Bampas, Evripidis Bampis, Vincent Chau, Johanne Cohen, Alexander Kononov, Yizheng Zhang

The Minimum Vertex Cover problem is a fundamental combinatorial optimization problem, aiming to identify a minimum subset of vertices in a graph such that every edge is incident to at least one vertex in this subset. Among its variants, the Min-Power-Cover problem stands out due to its practical applications, such as camera placement at intersections: in an edge-weighted graph, an edge is covered if one of its endpoints is assigned a power value at least as large as the edge's weight. In this paper, we introduce the Emergency Vertex Cover (Em-VC) problem where an edge may be covered not only by its endpoints, but also by a distant vertex, provided the vertex is given sufficient power to "cover" the cumulative weight of the edges along a shortest path to one of the edge's endpoints plus the weight of the edge. Em-VC is motivated by different practical scenarios, e.g. the need for urban disaster response, where ensuring accessibility to all road segments (edges of the graph) is crucial for effective aid delivery. We prove that Em-VC is NP-hard, derive lower bounds, and design a polynomial-time algorithm for its continuous version. Moreover, we present a 4/3-approximation algorithm for the discrete case and identify several special graph classes for which the problem can be solved in polynomial time.

Authors: Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi

We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, called \emph{integrality gap preserving reduction}, consists of iteratively shrinking the input universe of the problem while guaranteeing that gap-maximizing instances remain selected. When the subset of remaining instances becomes specific enough, we calculate the integrality gap explicitly. Besides applying integrality gap preserving reductions to three well-known optimization problems via their standard linear programming formulations (weighted vertex cover problem, multiple knapsack problem, and unrelated machine scheduling problem), we analyse the restricted assignment problem via its configuration LP relaxation. We prove that the integrality gap is equal to $1$ for three ``easy'' subclasses of the problem that are either solvable in polynomial time or admit a PTAS (e.g., the all-one processing time case). For some remaining cases, we improve the current lower bound using our technique.

Authors: Matic Požar

Computing influence spread under the Independent Cascade (IC) model is #P-hard, and influence maximization is commonly approached using Monte Carlo or reverse-reachable-set sampling. We study IC diffusion on bounded-treewidth graphs. Using probability distributions over separator reachability relations, we obtain exact influence evaluation in $O(n2^{O(w^2)}\operatorname{poly}(w))$ time for a graph with $n$ nodes and treewidth $w$. Our main contribution is an exact all-marginal-gains algorithm. We introduce variable artificial source edges and show that, at a deterministic seed set, the derivative with respect to each source-edge probability equals the corresponding greedy marginal gain. Reverse-mode differentiation therefore computes all marginal gains simultaneously with the same asymptotic complexity as one exact influence evaluation. This yields an exact implementation of classical greedy influence maximization in $O(Kn2^{O(w^2)}\operatorname{poly}(w))$ time, linear in graph size for fixed $w$ and seed budget $K$. We also show that the separator-relation representation has tight $2^{Θ(w^2)}$ state complexity within exact context-independent compositional separator summaries. This contrasts with the NP-hardness of globally optimal IC influence maximization already on graphs of treewidth one and pathwidth two. Experiments on synthetic bounded-treewidth networks are consistent with linear scaling for fixed width and show that runtime is largely insensitive to propagation and seed-activation probabilities. In demanding diffusion regimes, the method substantially outperforms reverse-reachable-set and optimized Monte Carlo greedy baselines while computing greedy marginal gains exactly.

Authors: Sourav Chakraborty, Debarshi Chanda, Arijit Ghosh, A. Pavan, Chhaya Trehan, N. V. Vinodchandran

Most existing graph streaming algorithms assume the ideal scenario where each edge arrives only once. Real-world graph streams, such as communication or transaction logs, often contain many repeated occurrences of the same edge. In general, the algorithms developed for the single-edge arrival case can fail when edges can arrive multiple times. Motivated by this, we study the {\em repeated-edge arrival graph streaming model} where an edge is allowed to arrive multiple times. In this work, we study the triangle counting problem in the repeated-edge arrival model: approximate the number of triangles in the underlying {\em simple graph} despite arbitrary edge repetitions. We design the first algorithms for triangle counting with optimal space complexity. In particular, we present a single-pass algorithm that computes an $(\varepsilon,δ)$-approximation of the number of triangles with optimal space complexity. We introduce {\em right-to-be-forgotten graph streaming} (RFGS) model, where a forget operation can cause all previous occurrences of an edge to disappear. We show that our single-pass algorithm can be extended to the RFGS model with optimal space complexity. Finally, we present optimal constant-pass algorithms that compute an $(\varepsilon,δ)$-approximation of the number of triangles and cliques for the repeated-edge arrival graph streams.

Authors: Vanessa Kosoy

In previous papers, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. In particular, we defined a complexity measure called Arithmetic Repetition Complexity (ARC) which admits a polynomial-time prediction algorithm with a mistake bound quasilinear in the complexity. Here, we show a weaker complexity measure related to ARC that admits an especially efficient prediction algorithm: an algorithm that runs in quasilinear time and polylog space for appropriate highly-structured sequences. The complexity measure is defined via a restricted class of "zipline programs" (a variant of straight-line programs), which we call layered. We thus get a less expressive measure with a more efficient algorithm (compared to our results for ARC), demonstrating a possible tradeoff.

Authors: Ling Li, Daniel Gibney, Sharma V. Thankachan, Rahul Shah, Grigorios Loukides, Solon P. Pissis

There is increasing interest in queries about the context of a string $P$ in a longer text $T$, i.e., the set of all string pairs $(L,R)$, with $|L|=|R|=q$, for a given $q$, such that the string $LPR$ occurs in $T$. Such contextual queries are important in several domains but are challenging to answer efficiently. This is because the length of $T$ in applications is massive and existing indexes do not directly encode the context of a given $P$, which is key for answering retrieval queries efficiently. Our work introduces the ZigZag Trie (ZZT), a new full-text index to specifically address these challenges. This index reorganizes the text so that, for any $P$, all possible strings $L$ and $R$ growing symmetrically around $P$ are grouped into a common subtree of the index, allowing their efficient retrieval. We show how to construct the ZZT of $T$, which has size $\mathcal{O}(n)$ where $n=|T|$, in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(n)$ space. On top of ZZT, we design specialized indexes that, for a query pattern $P$, answer four new types of contextual queries: (I) finding the longest string $LPR$ that occurs at least $τ$ times in $T$, for a fixed $τ$; (II) finding the longest string $LPR$ that occurs in at least $τ$ texts of a text collection, for a fixed $τ$; (III) reporting the total number of distinct contexts of $P$ in $T$; and (IV) retrieving, for a given $q$, the $k$ pairs $(L,R)$ of $P$ with the highest scores according to a given scoring function. Our indexes answer queries of type I, II, and III in optimal time, and of type IV in near-optimal time. Moreover, their size, construction space, and construction time are linear or near-linear in $n$, given ZZT. Using real billion-letter datasets, we show that our indexes answer queries orders of magnitude faster than baselines and perform similarly or better in index size and construction space and time.

Authors: Zhao Song, Song Yue

Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions. We provide polynomial-time algorithms for the Kadison--Singer problem. For Hermitian matrices $A_1,\ldots,A_m\in\mathbb C^{n\times n}$ of rank at most one, we give two algorithms that find signs $σ\in\{\pm1\}^m$ satisfying $\|\sum_i σ_iA_i\|\le C\|\sum_i A_i^2\|^{1/2}$. The deterministic algorithm achieves $C=3.3443$ using $\widetilde O(mn^2+n^{56})$ arithmetic operations. The randomized algorithm achieves $C=4.8628$ using $\widetilde O(mn^2+n^{5.88})$ arithmetic operations in expectation. For vectors satisfying $\sum_i a_ia_i^*=I$ and $\|a_i\|^2\leα$, the algorithms yield partitions $[m]=I_1\cup I_2$ satisfying $\|\sum_{i\in I_j}a_ia_i^*-I/2\|\le (C/2)\sqrtα$ for $j=1,2$.

Authors: Naonori Kakimura, Yoshihiko Terai

A splay tree is a self-adjusting binary search tree that allows access, insertion, and deletion to be performed in amortized $O(\log n)$ time, where $n$ is the number of stored elements.The sequential access theorem states that, when the elements of a splay tree are accessed in increasing order, the amortized cost per operation becomes a constant. In this paper, we show that the upper bound for this constant is at most $5.5$ by refining the existing analysis and introducing a new potential function. Furthermore, we complement our result by showing that there exists a splay tree for which the constant is lower-bounded by almost $4$.

Authors: Dylan J. Altschuler

We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\in\{0,1\}^{m\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let $\log^*$ denote the iterated logarithm and $\ell_j$ denote the $j$-fold composition of log. Assume $s\le\exp(O(\sqrt d))$. We provide an efficient algorithm that, for arbitrary sparsity $d$, gives $O(\sqrt d(1+\log^*n))$ discrepancy. Moreover, if $d\ge\ell_j(n)$ for a fixed integer $j\ge1$, the algorithm gives $O_j(\sqrt d)$ discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.

Authors: Jingyang Zhao, Yuxi Liu, Mingyu Xiao

The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost tour covering all clients in a metric graph. The metric multiple-depot TSP (MD-TSP) is a natural extension, where the graph contains depots and clients, and the objective is to compute a minimum-cost set of tours covering all clients, with each tour starting and ending at the same depot. When the number of depots is part of the input, an adaptation of the Christofides--Serdyukov heuristic yields an approximation ratio of $2$. In this paper, we introduce a $(1+1/\sqrt{2})$-approximation algorithm. Like the Christofides--Serdyukov heuristic, our algorithm first computes a rooted spanning forest (RSF), then a matching to correct its odd degrees, and finally obtains a solution by shortcutting. However, instead of using a minimum-cost RSF, we construct an RSF by a primal-dual algorithm for a natural cut relaxation. The algorithm grows rootless components and the component containing all depots at different rates, adding an edge when its dual constraint becomes tight. Vertex labels record the times at which clients first become connected to a depot. The two-speed growth provides a joint bound on the forest cost and two label-dependent terms that also arise in bounding the parity-correction cost. Balancing the coefficients of these two terms by setting both to $\sqrt{2}-1$ yields the claimed approximation ratio.

Authors: Chandra Chekuri, Richard Ueltzen, Jan Vondrak

We consider the question of designing a universal family of sets $F \subset 2^{[n]}$ such that for any function $f:2^{[n]} \to R_{\geq 0}$ in a certain class, we have $$\max_{S \in F} f(S) \geq c(n) \cdot \max_{S \subset [n]} f(S).$$ We prove that there is a family of subpolynomial size such that for any nonnegative submodular function, $c(n) = Ω(\frac{\log \log n}{\log n})$, and there is a family of logarithmic size such that $c(n) = Ω(\frac{1}{\log n})$. We also prove that pairwise independence (which achieves a constant factor for graph cut functions), or even $k$-wise independence, does not imply a bound better than $O(\frac{1}{\sqrt{\log n}})$ for submodular functions. On the other hand, we prove that for any polynomially representable subclass of nonnegative submodular functions (such as the matroid connectivity functions for matroid representable over $F_q$), a constant-factor universal family of polynomial size always exists. For absolute XOS functions (a class that we introduce, in the form $f(S) = \max_i |\sum_{j \in S} w_{ij} + c_i|$ where $w_{ij}, c_i \in R$), we design a family of polynomial size such that $c(n) \geq \sqrt{\frac{\log n}{n}}$, and prove that there is no polynomial-size family achieving a factor better than $O(\sqrt{\frac{\log n}{n}})$.

Authors: Xiaoyu Chen, Kuikui Liu

Local-to-global techniques for establishing spectral gaps have played a central role in the modern theory of Markov chain mixing times and the theory of high-dimensional expanders. One of the most striking results in this burgeoning literature is that a spectral gap for the global down-up walk on the facets of a pure simplicial complex can be reduced to sufficiently strong spectral expansion of just the codimension-2 links of the complex, a phenomenon colloquially referred to as "trickle-down". These types of theorems have had many important applications, including rapid mixing of the exchange walk on the bases of any matroid. In this primarily expository article, we give streamlined proofs of two such theorems in the literature, one by Oppenheim (2018) and one by Leake and Oveis Gharan (2025), via an integrated Bochner method. Moreover, in the latter setting, we quantitatively strengthen the dependence of the global spectral gap on the dimension of the complex and the spectral influence, resolving an open question of Leake and Oveis Gharan. Disclaimer: The proofs were developed through a couple of rounds of interaction with GPT-5.6 Sol Ultra. We later discovered that Guo and Zhang (2026) had independently proven the same strengthening of the trickle-down theorem of Leake and Oveis Gharan using an extremely similar argument, also found by GPT-5.6 Sol Ultra. The focus of their paper is the complexity of approximating the partition function of spin systems on planar graphs, not on the trickle-down phenomenon itself. In contrast, our motivation is primarily expository, and we hope to bring Bochner-type methods and their connections with the trickle-down phenomenon to the attention of a wider community of researchers.

Authors: Evan Unit Lim

Figured-bass realization can be described as a sequence of choices constrained both within each sonority and between successive sonorities. This paper gives an explicit mathematical model of a restricted, examination-style four-part realization problem. Pitch spelling, range, chord membership, doubling, omission, spacing, crossing, overlap, melodic motion, consecutive perfect intervals, and selected resolution requirements are expressed as predicates. We distinguish hard constraints from optional preference costs. Four labeled notes are represented visually as the vertices of a quadrilateral and computationally as one ordered voicing state. Legal progressions become paths through a layered graph. We prove that feasibility and minimum-cost realization are polynomial-time problems for a fixed number of voices with explicit finite note domains and fixed local rules. For fixed ranges, a fixed note alphabet, and adjacent-event rules, the number of graph operations is linear in the number of events. Worked two-, four-, and eight-beat examples illustrate legality, optimization, and the failure of a greedy choice. The result concerns the stated formal model; it is not a claim that every musical judgment is captured by local predicates.

A fully-funded PhD position is available with Sajin Koroth at UVic starting Jan 2027. Research focuses on theoretical CS (circuit & communication complexity, quantum info). A solid TCS background is required. As the official deadline has passed, please email your CV, transcripts, and background summary to skoroth@uvic.ca by Sept 30, 2026.

Website: https://web.uvic.ca/~skoroth/
Email: skoroth@uvic.ca

By shacharlovett

The UC San Diego Department of Computer Science and Engineering (CSE) invites applications for tenure-track faculty positions at the Assistant Professor rank. The department is looking for exceptional candidates in all areas of Computer Science and Engineering.

Website: https://apol-recruit.ucsd.edu/JPF04649
Email: nbarr@ucsd.edu

By shacharlovett

October 17-18, 2026 Rochester, NY https://www.cs.rochester.edu/u/shossei2/eagl2026website/index.html Submission deadline: October 1, 2026 Registration deadline: October 1, 2026 The purpose of this annual workshop is to bring together researchers in theoretical computer science, who work in the vicinity of the eastern great lakes region. For 2026, this event is held at the University of Rochester.

By shacharlovett

Cryptographic combiners take $n$ candidate schemes for some primitive $P$, and realize it securely provided that at least $k$ candidates are secure. Intuitively, we expect that if we plug $n$ independent instances of a $\delta$-weak candidate for $P$ into the combiner, assuming $\delta \ll (n-k)/n$, security should be amplified and the resulting candidate should exhibit a significantly smaller weakness. This intuition relies on the implicit “all-or-nothing” assumption that each candidate fails with probability $\delta$ and is otherwise perfectly secure, allowing us to bound the failure probability of the combiner using a simple binomial tail bound. However, this intuition often fails for standard security notions where, for example, a weak candidate may consistently leak partial information rather than exhibit a clean all-or-nothing failure. Recently, Applebaum, Bitansky and Geier (CRYPTO 2026) showed that indistinguishability combiners inherently act as security amplifiers. However, this general result incurs a multiplicative loss of roughly $2^{n-k}$ in the error parameter relative to the natural all-or-nothing bound. Moreover, the combiner-is-amplifier approach is fundamentally restricted to the regime $\delta < 0.5$. Consequently, both the resulting error rate and the amplification threshold $\delta_0$ are suboptimal. In this work, we overcome these limitations by establishing a new specialized framework of bias-resilient indistinguishability combiners. This formulation allows us to achieve the optimal all-or-nothing bound without the exponential penalty. We observe that bias-resilience provides a unifying abstraction for security amplification across different primitives, neatly capturing prior ad hoc results such as those for weak PRGs and weak NIZK. As our main application, we use this framework to establish a generalized XOR lemma over prime fields $\mathbb{F}_p$, showing that the sum modulo $p$ of independent weakly pseudorandom elements becomes computationally indistinguishable from uniform. This improves upon a recent work by Shimizu and Yasunaga (STOC 2026) by achieving a sample complexity that is independent of the field size. Finally, we explore the idealized notion of an all-or-nothing amplifier. We establish a tight characterization of the multiplicative penalty incurred when applying such an amplifier to candidate schemes that only guarantee standard weak indistinguishability error.

The permanent and mixed discriminant of positive matrices are classic problems for which we do not expect an efficient algorithm for exact computation. Thus much work has been done to understand how well we can bound and approximately compute these quantities. One line of research in this area begins with the results of the first author, where van der Waerden lower bounds of $\frac{n!}{n^n}$ are proven for doubly stochastic inputs for both problems, using a simple proof via stable polynomials. Along with the bound itself, the same techniques are used to show that the permanent and mixed discriminant are uniquely minimized at a certain natural symmetric input. In this paper, we generalize those results in two ways. First, we extend the unique minimization results beyond doubly stochastic inputs to other marginals which are near doubly stochastic. This yields the first such unique minimization results for the mixed discriminant beyond the doubly stochastic case. We also discuss why one cannot hope similar results to hold in general for all marginals. Second, we extend the unique minimization result for real stable polynomials to strongly log-concave (aka Lorentzian) polynomials in the doubly stochastic case. This captures an analogous previous result on unique minimization for the mixed volume. Finally, we discuss various open problems related to these results.