Theory of Computing Report

The world of mathematics, including theoretical computer science, is in turmoil. Even the Millennium Prize Problems, and, worse still, our beloved FOCS/STOC open problems, are no longer beyond the reach of LLMs. Watching this unfold inspires genuine awe and excitement, yet it also brings a real sense of loss. In the stages of mourning, the community seems to have moved away from denial. No more “models are nice, but they cannot do real math.” Instead, within our different mathematical communities, we now live in some combination of anger, bargaining, and depression.

If you are a junior mathematician, you have every right to take your time processing this shift. You have my deep sympathies, and we must both support you and ensure you have a central voice in shaping the future of our field. But to senior colleagues, myself included, I say: Snap out of it.

This moment is not simple, but there is no time to waste. We need to rise to the challenge. The world is changing at an incredible pace, and our response needs to be decisive and continuous. That may not be the traditional forte of academics, but the magnitude of this moment demands it.

Among the reactions exhibited by senior mathematicians, I find bargaining and depression particularly harmful. Bargaining, a close cousin of denial, is the hope that our work can stay more or less the same with just a little adjustment. If only we could get the frontier labs to pause or stop proving our theorems, or if we slightly adjusted the rules of our publication venues, things wouldn’t be too bad. Sure, pushing back on frontier labs and addressing urgent concerns about the viability of our publication system are important. But we should not mistake these measures for a way to avoid a fundamental transformation of our profession.

Bargaining slows real action. It also prevents us from enjoying the positive aspects of the AI revolution, including progress on mathematical questions that we genuinely care about. We cannot suddenly move the goalposts and pretend that proving theorems was never the point, or that our open problems were merely proxies for building mathematical understanding. Those theorems are still of deep interest, and studying their proofs remains central to how we gain understanding in the first place. As for me, there are quite a few conjectures whose proofs I would absolutely love to understand, regardless of the source.

As for depression: the next time you have the urge to lament, or even celebrate, being “the last generation of human mathematicians,” perhaps keep it to yourself. Contemplating the end of your profession from the relative comfort of an established, tenured career is a privilege, and it comes with responsibilities. Senior academics are not merely individual researchers; we are stewards of our field, and we owe our junior colleagues active leadership rather than abandonment.

So, what do we need to do, and keep doing again and again?

Right now, the immediate, practical questions of how to adapt our institutions are getting the most attention, and we are already seeing thoughtful suggestions and encouraging initial steps. Today, this means increasing the recognition and incentives we provide for communication, understanding, and community building, and reflecting those priorities in our hiring, promotion, funding, and publication practices. For example, many are pointing out that we should no longer accept badly written papers just because we value the theorems. Similarly, we may now value conceptual work, such as new definitions, novel questions, and fresh techniques, more than ever before.

Yet we cannot treat these reforms as a one-time adjustment. We face the daunting task of continuously recreating our institutions as capabilities evolve. Tomorrow, models may surpass us at communicating their results, and eventually at conceptual work as well, which will force us to shift our core operations yet again. The same applies to how we educate future generations of mathematicians. If the human role increasingly centers on judgment, taste, and a broad perspective, how can newcomers reach that point? All of these questions are on everyone’s mind, and I urge us to be brave enough to pursue dramatic, ongoing transformations.

To guide those transformations, however, we need something deeper. Above all, we need to reevaluate our identity. What is it that makes mathematical knowledge and research valuable? What are we offering society, and how much of it survives in a world where models match or exceed humans in some or all relevant mathematical skills? For quite some time, the implicit social contract has been that society pays us to exercise our intellectual curiosity and we, in return, provide useful skills to the next generations and practical knowledge for the world. The current crisis is driven not only by the power of LLMs, but also by how rarely we have had to examine or articulate this contract. Now that the deal needs to be renegotiated, we should approach it with humility rather than entitlement.

It is easy to feel bleak when confronting these questions, so it helps to ask what a positive vision might look like, even in a future with artificial superintelligence (ASI). We are not there yet, as today’s models still make mistakes and flawed proofs can actively harm learning, but suppose we reach a world where models are much more capable. One optimistic possibility I have been toying with is a future that opens the best parts of the academic experience to everyone. Not that everyone would hold an academic job or create knowledge that is new to the world, but everyone could participate in serious intellectual exploration, in mathematics and beyond. Conversations with reliable models could be truly Socratic: helping us ask questions, develop ideas, and discover things for ourselves, rather than simply supplying answers. In this vision, everyone would have access to forms of intellectual creativity that are now reserved for a fortunate few. Within this world, professional academics (in mathematics and elsewhere) would need to find our own distinct role, and I believe we could. Even if this future supports fewer professional mathematicians, it could nevertheless support a much richer mathematical life.

Finally, we must look further than just our own small piece of heaven. Accelerating mathematics can bring tremendous good to the world if it speeds up applied fields, medicine, and other concrete benefits for society. At the same time, the disruptions and dangers extend far beyond academia: a professional driver losing their job is no less important than a professional mathematician whose work has become less enjoyable. We therefore have a duty to take our professional responsibility toward AI alignment seriously.

AI models are mathematical objects, and their development could not have happened without our collective work. Furthermore, mathematicians, especially theoretical computer scientists, have a critical role to play in helping to govern AI models so that they serve individuals and society rather than harm them. Of course, AI alignment is not merely a mathematical problem, but the mathematical perspective is invaluable. Some of us have long been calling for more significant involvement in navigating the interface between computation and society. It is time for many more to heed that call.

Acknowledgments: Thank you to Sílvia Casacuberta, Lee Cohen, Jabari Hastings, and Charlotte Peale for many meaningful conversations and thoughtful comments on earlier drafts, though the views expressed here are entirely my own. I also want to thank a couple of unnamed models that graciously helped me clarify my perspective.

By Omer Reingold

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

A bizarre central tenet of “rational decision-making” is that all optimal decisions can be made by computing an appropriate cost-benefit analysis. I riff on this in the introduction to The Irrational Decision, and always lead with more absurd examples when I talk about the book. Should you have a surgery? Should you force your kid to take violin lessons? Should you go for it on 4th down? According to the tenets of rational choice theory, you can answer all of these questions by forecasting a dollar value and probability of every outcome.

With these facts in hand, optimal decision making is merely a mechanical chain of sums and multiplications. This is ludicrous if you think about it for two seconds. And yet it’s become a standard social convention that utilitarian calculation is not only possible but the optimal way to live your life, run a business, or govern a nation.

In today’s class, we try to get at the roots of where this came from and how it became institutionalized. My two favorite references on the history are Theodore Porter’s Trust in Numbers and Elizabeth Popp Berman’s Thinking Like an Economist, both of which trace the history in the United States.

Porter starts before the war, looking at how cost-benefit analyses were formalized to justify water projects by the Army Corps of Engineers. He has a nice short article summarizing the book’s in-depth study. Water projects were crucial for preventing flood damage, routing water to farms, and making waterways more navigable. However, they were also classic pork-barrel projects, where elected officials would funnel money back to their districts. The Corps looked for means to “remove the politics” and demonstrate that each project was worth doing. They settled on cost-benefit analysis, establishing a rigorous system to enumerate all of the potential upsides and itemize all of the potential costs.

These calculations were eventually mandated in the 1936 Flood Control Act:

“...the Federal Government should improve or participate in the improvement of navigable waters or their tributaries, including watersheds thereof, for flood-control purposes if the benefits to whomsoever they may accrue are in excess of the estimated costs, and if the lives and social security of people are otherwise adversely affected.” (italics mine)

Cost-benefit analyses would leave them with a simple, clean, unitary number — the ratio between these costs and benefits — that they could present for project approval. All of the complexity could be reduced to two digits. These digits sufficed to make governance decisions. Significant expertise was needed to ensure these calculations held up to adversarial scrutiny. As Porter writes:

“Objectivity, then, meant above all the standardization of quantitative methods and the training up of people capable of performing them. Every failure of clarity, every gap in the reasoning, every loophole that left space for the quantifier to alter the results in a preferred direction, was a potential weakness, which opponents of the agency were certain to exploit, often in hearings before judges and administrators who would probably be ignorant of the fine points of economic quantification.”

Interestingly, no economists were consulted in constructing the estimates. The engineers prided themselves on their ruthless objectivity and ability to decouple their preferences from the cold hard facts. Moreover, the public preferred cost-benefit analyses to opaque expert judgment. Standard, transparent processes feel like they rule out arbitrariness and capriciousness of bureaucrats. Porter casts cost-benefit analysis as “a quantitative decision technology, practiced mainly in public bureaucracies, often in a highly politically-charged context.”

Popp Berman details how this technology spread through the government, with the establishment of various executive-branch offices staffed by experts to oversee complex problems like healthcare and education. It became institutionalized in policy schools, founded in the 1970s to provide graduates to staff said agencies.

Fast forward to the present, and we just take these cost-benefit analyses for granted. They give an institutionalized illusion of objectivity, but of course all of the calculations are subject to institutionalized norms of expert judgment. These norms tell you where you can commit rounding errors, ignore missing data, or disregard the unenumerable. But these are just institutional norms, and they don’t really hold up to scrutiny. As Larry Lohman details, the “objective” methods of institutionalized cost-benefit analysis are riddled with value-laden assumptions, and objectivity rests on absurd ideas of commensurability and the ability to price all preferences.

Moreover, Charles Manski describes the incredible uncertainty inherent to cost-benefit calculations.1 Manski notes that experts all know these uncertainties are present but choose not to report them for political reasons. You’ll often find cost-benefit analyses reported to three or four digits of precision, creating a further illusion of precision. Manski has a long list of critiques:2

• Conventional certitude: A prediction that is generally accepted as true but is not necessarily true.

• Dueling certitudes: Contradictory predictions made with alternative assumptions.

• Conflating science and advocacy: Specifying assumptions to generate a predetermined conclusion.

• Wishful extrapolation: Using untenable assumptions to extrapolate.

• Illogical certitude: Drawing an unfounded conclusion based on logical errors.

• Media overreach: Premature or exaggerated public reporting of policy analysis.

Together, these conventions conspire to communicate certainty where there is none. They justify decisions as rational by sweeping all of the uncertainty under the rug.

Subscribe now

By Ben Recht

WVU’s Lane Department invites applications for a 2-year Postdoctoral Fellow in theoretical computer science starting Jan 1, 2027. Funded by NSF (Algorithmic Foundations), research focuses on algorithm design and computational complexity in mathematical programming. Duties include combinatorial optimization research and teaching one course. A PhD in CS or operations research is required.

Website: https://wvu.taleo.net/careersection/faculty/jobdetail.ftl?job=30378&tz=GMT-04%3A00&tzname=America%2FNew_York
Email: k.subramani@mail.wvu.edu

By shacharlovett

Postdoc position available in Tom Gur’s group at Cambridge on topics including (but not limited to) Classical and/or Quantum aspects of: Complexity, Sublinear Algorithms, Coding Theory, Cryptography, Learning Theory, and connections to Harmonic Analysis & Additive Combinatorics.

Website: https://www.cam.ac.uk/jobs/research-assistantassociate-in-theoretical-computer-science-fixed-term-nr51230
Email: tg508@cam.ac.uk

By shacharlovett

Greetings from Providence!

Next week there will be a conference at Rutgers University in honor of Jeff Kahn. Jeff is a great mathematician whose contributions span all areas of combinatorics. He has also been my friend for four decades and is my closest collaborator. Here is the conference description:

Probabilistic combinatorics lies at the heart of modern discrete mathematics, with deep connections to probability, theoretical computer science, and statistical physics. This conference will bring together leading researchers and emerging scholars to highlight recent breakthroughs, explore fundamental open problems, and recognize the profound influence of Jeff Kahn on the field.

There is a wonderful lineup of speakers, and the conference promises to be a great event. I look forward to similar events in extremal combinatorics, geometric combinatorics, matroid theory, posets, fractional combinatorics, finite geometries, and more, celebrating other aspects of Jeff’s work . In the meeting, I will talk about problems around Borsuk’s conjecture.

I was also kindly invited to visit Brown University and speak at its applied mathematics colloquium. I am very excited to talk here about my work on quantum computers and to meet many friends and colleagues. These two events, Jefffest and the lecture at Brown, are the anchors of a rather intensive, ambitious, and nostalgic tour of Providence, Boston, New Haven, New Brunswick, and Princeton.

Jeff and me, 2006

By Gil Kalai

Or click here if the above doesn’t work.

Recorded in-person in my office at UT Austin, with a bulleted list containing “ARC,” “Scalable Oversight,” and “Models” behind me on my blackboard for some reason (I no longer remember who put those there or why). 90 minutes long. Sometimes you see my disembodied arm waving in midair because of the way the cameras are combined. As always, I strongly recommend 2x speed for the correct experience.

This might actually be one of my best podcasts ever, although I wasn’t planning on that! Thanks so much to Bhavay Tyagi and Prachi Garella for driving all the way from Houston to record it.

Here’s a strict subset of the topics we covered:

• The story of AI models solving the Navier-Stokes Millennium Problem, insofar as it’s known
• Can recent AI proofs be called “truly creative”?
• The history of AI before the LLM revolution
• What do we mean when we call LLMs “black boxes”?
• The achievements of the field of interpretability
• What exactly happened in the OpenAI/HuggingFace incident
• Must we avoid all “anthropomorphizing language” when discussing the HuggingFace incident? (spoiler alert: no)
• Examples of major open problems in quantum computing theory that I cared about for decades and that AI models have recently solved
• Effects of the current AI cataclysm on the math community, especially students
• What annoys me the most when I listen to AI talks
• My experiences at OpenAI, why they hired me, and the watermarking work that I did there

Enjoy!

More AI-related content coming soon, as this blog—like much of the rest of the world—continues its transition to “all AI, all the time” (except still 100% written by an aging, deteriorating biological brain)

And for those who just can’t get enough of my rocking back and forth, using too many filler words, as I explain theoretical computer science! Here’s a second podcast, this one mainly on quantum computing, with Seb Agertoft, who I thank for doing it. Enjoy!

By Scott

Authors: Srinivasan Arunachalam, Yanlin Chen, Amin Shiraz Gilani

Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. $(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00]. $(3)$ We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for $\varepsilon$-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.

Authors: Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu

We present a protocol that estimates the quantum fidelity, up to precision $\varepsilon$, between a known target state and unknown lab-prepared state with sublinear, $o(d^{0.9908}/\varepsilon^2)$, number of Pauli basis measurements.

Authors: Uma Girish, Kunal Mittal, Barak Nehoran, Ran Raz

A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution $μ_p$, where the input bits are independent Bernoulli variables with fixed bias $p$. We show that for every fixed $p \in (0, 1)$, quantum query algorithms under the $μ_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $ν_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $ν_p$ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.

Authors: Lance Fortnow

Using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between $\mathbb{F}_2$-polynomials and the XOR of majorities, we show that $\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$, where $\mathrm{Almost}\text{-}\oplus\mathrm{P}$ is the class of languages that lie in $\oplus\mathrm{P}^R$ with probability one for a random oracle $R$. This is the parity analogue of Bennett and Gill's $\mathrm{Almost}\text{-}\mathrm{P} = \mathrm{BPP}$ and Nisan and Wigderson's $\mathrm{Almost}\text{-}\mathrm{PH} = \mathrm{PH}$. The key ingredient is a pseudorandom generator with polynomial seed length that fools $\mathbb{F}_2$-polynomials of polynomial degree on exponentially many variables. As an application we complete a random-oracle proof of the first half of Toda's theorem, $\mathrm{PH} \subseteq \mathrm{BP}\cdot\oplus\mathrm{P}$, following an approach of Regan and Royer. Relative to a random oracle, the polynomial hierarchy collapses into $\oplus\mathrm{P}$ by applying Valiant-Vazirani and Papadimitriou-Zachos level by level, with no probabilistic quantifier ever moved through an oracle. Our result then removes the oracle. We compare this argument with the simple proof of Toda's theorem by Fortnow (2009).

Authors: Keisuke Fujii

A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in $\mathrm{NP}\cap\mathrm{BQP}$ and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at $k=1$, recovering the repetition number contains finite-field discrete logarithm over $\mathbb{F}_{2^r}^{\times}$. In general, restricting every exponent to $\{0,1\}$ removes the Abelian-group closure and makes feasibility NP-complete for variable $k$, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.

Authors: Frank Vallentin

In this note, we prove that the covering radius problem for Euclidean lattices is complete for the second level of the polynomial hierarchy. The note also documents the author's first experiment with generative AI as a tool for mathematical research.

Authors: Priyanshu Pant

Let $G_{2n}$ be a complex symmetric random matrix whose entries above the diagonal are independent standard circular complex Gaussians, and let $H_n=\operatorname{haf}(G_{2n})$. We prove the uniform shifted anticoncentration bound $$ \Pr\!\left( \left| \frac{H_n}{\sqrt{(2n-1)!!}}-z \right| \le \varepsilon \right) \le 2\sqrt{\frac nπ}\,\varepsilon^2 $$ for every $z\in\mathbb C$ and $\varepsilon>0$. This establishes a local anticoncentration property that supports hardness arguments for quantum advantage in Gaussian boson sampling.

Authors: Sebastian Ben Daniel

We study the consequences of membership comparators that exclude one possible membership vector, deterministically or with a relative advantage over uniform guessing. For every polynomially bounded arity, a randomized polynomial-time comparator of error at most $(1-1/poly(n))2^{-t}$ gives $ NP/ poly\cap coNP/ poly$ recognition with common advice. The proof uses limited independence, polynomial occurrence certificates, and a self-contained positive-relation advice transfer. For SAT at arity $O((\log n)^d)$, both this relative-gap hypothesis and deterministic comparability imply $PH=S^{NP}$, the uniform bound $PH\subseteq BPTIME(2^{O((\log n)^{d^2})})$, and symmetric verification with polynomial-length certificates and an oracle-free deterministic $2^{O((\log n)^d)}$ predicate. Polynomial-advice deterministic decoding has the same exponent $d$. Applying the randomized simulation to an unconditional diagonal language yields, for every fixed $\varepsilon>0$, $\mathrm{BPP}\subsetneq BPTIME(2^{O((\log n)^{d^2+\varepsilon})})$, without advice. The larger clock remains subexponential under every fixed number of self-compositions. A layered oracle satisfies deterministic comparability and $NP^O=coNP^O$ but excludes randomized NP algorithms with smaller logarithmic power, establishing a relativized limit on the SAT exponent $d$. This expanded version also develops the full weak-advantage regime, where saving $2^{-O((log n)^d)}$ gives randomized SAT exponent $d$ and PH exponent $d^k$ at fixed level $k$; the quasipolynomial and exponential hierarchy consequences; binary-comparator advice bounds; and the certificate-length boundary between the randomized regimes. Under deterministic comparability, uniform deterministic promise-unique search additionally gives $UEXP=EXP$. The ordinary second-level collapse $PH=Σ_2^p$ for $d>1$ remains unproved.

Authors: Francisca Vasconcelos

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

Authors: Aris Filos-Ratsikas, Charalampos Kokkalis, Mohamad Latifian

We introduce and study Auctions with Pacing Strategies (APS) games, a full-information model in which utility-maximizing bidders compete across many simultaneous first-price auctions, each choosing a single pacing multiplier that uniformly scales their values into bids. We settle three central questions. First, we show that there are instances that admit no approximate pure Nash equilibria. Then, we prove that the problem of deciding whether an APS game admits an (approximate) equilibrium is NP-complete in general, but can be solved in polynomial time if either the number of bidders or the number of items is fixed. Finally, when an equilibrium does exist, we characterize its inefficiency exactly, showing that both the Price of Anarchy and the Price of Stability equal $\frac{e}{e-1}$.

Authors: Mrinal Kumar, Ben Lee Volk

We prove an $Ω(n^2)$ lower bound on the determinantal complexity of the power sum polynomial $\sum_{i=1}^n x_i^n$ over the field of complex numbers. A similar result was claimed in a recent paper of Sheshadri (arXiv:2606.13628), via an AI-assisted and AI-written proof. Assuming its correctness, this was the first super-linear lower bound for this fundamental algebraic problem for any explicit polynomial. However, the authors of this note were unable to follow the details and verify the argument in arXiv:2606.13628, in spite of considerable effort on their part. The proof we provide here is short, (almost) self-contained and seemingly simpler.

Authors: Shubham Bhardwaj, Ramprasad Saptharishi

We give an explicit hitting set of size $\text{poly}(n,d,r)$ for the class of $n$-variate degree-$d$ polynomials whose partial derivative space is bounded by $r$, over any field $\mathbb{F}$ of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-$3$ powering circuits. The main technical insight is the construction of a "formal derivation'' and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura [Moura_2004] in a very different context. The proofs in this paper are elementary and completely self-contained. AI disclosure: The proof of this result was obtained during conversations [astra_proof] with OpenAI GPT-6 Astra. The proof presented in this writeup is a rewriting (in the authors' words) of the proof obtained by the AI model in a form that we believe is understandable to researchers.

Authors: Victor Lecomte, Prasanna Ramakrishnan

Four decades on, Håstad's classical $2^{Ω(n^{1/(d-1)})}$ lower bound for depth-$d$ circuits computing Parity remains the best known $\mathrm{AC}^0$ circuit lower bound for any explicit function. Majority has long been a compelling candidate for stronger lower bounds: the most natural circuits computing it are substantially larger than those for Parity and have repeatedly been conjectured to be optimal. We present a simple construction, found by GPT-6 Astra, of depth-$d$ circuits of size $2^{O(n^{1/(d-1)})}$ for any symmetric function. This result settles the asymptotic $\mathrm{AC}^0$ circuit complexity of Majority, matching Håstad's lower bound.

Authors: Nathan Dalaklis, Beckett Fields

Riftbound: League of Legends Trading Card Game is a trading card game about capturing and holding locations in a king-of-the-hill style contest. Originally released in China in August of 2025, and later released in the United States in October of 2025, the game has been well received for its depth and complexity. In this paper we demonstrate a facet of this complexity by providing sequences of valid game states which construct Universal Turing machines within the game. Each of these machines are constructed with tournament legal decks at the time of writing and strategies assigned are directed by the game state. We also show that given an appropriate board state the machine may be constructed and the computation may be performed in one game turn.

Authors: Gil Kalai

In this paper I revisit my 2006 conjecture on correlated errors in entangled physical qubits, originally proposed as a potential obstruction to quantum fault tolerance. The conjecture asserts that, in any physical implementation of a quantum computer, the effective noise channel acting on entangled physical qubits contains a joint fully depolarizing component, with a rate comparable to that of two-qubit gate errors. This hypothesized structural constraint goes beyond standard noise models and, if valid, would pose a significant challenge to scalable quantum fault tolerance. The conjecture remains open, but recent advances in experimental quantum computing bring it within reach of empirical testing on current devices. I also discuss two related directions in my critical study of quantum computation: the role of noise sensitivity and computational complexity in noisy intermediate-scale quantum systems, and the statistical analysis of experimental claims of quantum advantage. Finally, since this paper is written for a volume honoring Yuri Gurevich, I include some reflections on the ways in which my scientific and personal trajectory became intertwined with Yuri's.

Authors: Yin, Liu

We classify the exact evaluation of $\operatorname{Holant}(f\mid=_3)$ for every fixed complex algebraic symmetric Boolean ternary signature $f$. An input is a cubic bipartite multigraph: every vertex on one side carries $f$, every vertex on the other side carries ternary equality, and no auxiliary signatures are freely available. The tractable signatures are precisely rank-one tensors, generalized equalities, and equality-preserving cube-root diagonal transformations of six affine signatures, together with nonzero scalings and reversal. Every other signature gives a $\#\mathrm{P}$-hard problem under polynomial-time Turing reductions. We also identify the exact real intersection: it consists of the same tractable families as in the rational classification, with real algebraic parameters. The proof preserves degree exactly three on both sides of every oracle instance. A rank-one matrix extracted by interpolation supplies one unary signature only after its unused factor has been absorbed in triples. Over the complex numbers this absorption has three exceptional projective directions. We combine this constraint with projective matrix-group orbits, explicit ternary replacements, and an exhaustive treatment of finite projective orders. The cases of orders three and five include exact polynomial certificates; the certificate identities and a rational-arithmetic verifier are supplied as supplementary material.

Authors: Ioannis Anagnostides, Ioannis Panageas, Jingming Yan

We show that computing a Nash equilibrium is CLS-complete for linear network congestion and network coordination games. As a result, finding a KKT point of a bilinear polynomial is CLS-complete.

Authors: Ondřej Kuželka

We observe that the classical $n\log n$ time threshold for one-tape Turing machines is also a threshold for their accepting-path counts. Below it, every nondeterministic one-tape machine running in strong $o(n\log n)$ time has a rational ordinary generating function of accepting-path counts. At strong $O(n\log n)$ time, the situation changes completely: there is a fixed one-tape machine whose accepting-path function is complete for $\#\mathsf P_1$, the tally analogue of $\#\mathsf P$, under parsimonious polynomial-time tally reductions. A second construction within the same time bound gives positive accepting-path counts with a noncomputable exponential growth rate. The rationality result combines the one-tape time gap with the linear-time counting theorem of Tadaki, Yamakami and Lin. The completeness proof adapts the linear-time universal counting machine of Beame et al. to the one-tape setting.

Authors: Gil Cohen, Dean Doron, Noam Goldgraber

A subspace design is a collection of subspaces $H_1,\ldots,H_n$ of $\mathbb{F}_q^k$ with the property that no low-dimensional subspace $W$ intersects the collection "too much". Subspace designs and related objects in linear-algebraic pseudorandomness have found a broad range of applications, ranging from list decoding, to derandomizing algorithms. We construct explicit strong subspace designs over every finite field. In the extremal case where the co-dimension $t$ of each $H_i$ is equal to the dimension of $W$, for every constant field size our construction attains $n=Ω(k)$ and matches the probabilistic intersection bound up to a constant factor. All previous constructions required the field size to grow with $t$ (or $k$). Our subspace designs also imply new construction of rank condensers over arbitrary finite fields. This result is the first to achieve an optimal dependence on $k$ while maintaining both a constant output entropy rate and a constant field size. As an application, we construct lossless rank extractors for linear sources of rank $r$, for all $r < q$, with parameters matching those of Guo, Raj, Shangguan and Zhang (FOCS '26), thereby generalizing their result to prime fields and smaller field sizes. Our construction is based on an algebraic-geometric version of the Parvaresh-Vardy codes (Parvaresh-Vardy FOCS '05, Guruswami ECCC '05), extending the framework underlying the condensers of Guruswami, Umans and Vadhan (JACM '09). We view our construction as a linear-algebraic analysis - tailored to affine sources - of the GUV construction, generalized to functions over algebraic curves. More specifically, inspired by Ta-Shma and Umans (CCC 12') we develop a two-level evaluation scheme, where we first evaluate a function on a curve at extension-field points, and then evaluate a corresponding affine-linear polynomial to obtain outputs over the base field.

Authors: Chenyu Wang

We prove a lifting theorem from two-party public-coin one-way communication to multiparty public-coin one-way number-on-forehead (NOF) communication. For every fixed $k\ge2$ and prime $q>2k$, there is a generalized inner product gadget $\GIP_{q,r}^k:(\F_q^r)^k\to\F_q$ with $r=O_k(q/\log q)$ such that, for every partial Boolean function $f:D\to\bits$, where $D\subseteq\F_q\times\F_q$, \[ R_{1/3}^1(f)-O(1) \le R_{1/6}^{1,\NOF}\bigl(f\circ\GIP_{q,r}^k\bigr) \le R_{1/6}^1(f). \] Thus, composition with the gadget preserves one-way randomized communication complexity up to an additive constant and a change in the error parameter. The lower bound holds in the general one-way NOF model, where the last player sees the entire gadget input. This extends the deterministic one-way NOF lifting theorem of Yang and Zhang to randomized protocols, and extends the randomized lifting result of Wang and Wu from the conservative model to the general one-way NOF model. Our proof introduces a one-way cylinder partition bound that lower bounds public-coin one-way NOF communication complexity. We show that, for the lifted function, this bound is at least half the one-way partition bound of the outer function. The main technical step transfers a dual solution between the two bounds, using Möbius inversion and a discrepancy estimate for generalized inner product to control the loss. Combining this transfer with the characterization of two-party one-way randomized communication complexity by the one-way partition bound yields the lifting theorem.

Authors: Geoffroy Couteau, Nikolas Melissaris, Tamara Paris

We study interactive proofs of proximity (IPPs) for model evaluation, where a resource-limited verifier interacts with an untrusted prover, typically the model owner, to certify statistical properties of a model under an unknown input distribution. Our formulation separates sampling the input distribution from querying the model and evaluating its output; distinguishes real audit data (black-box sampling) from generated data (chosen-randomness, or gray-box, access to the sampler); and allows the prover and verifier to use different evaluators. We focus on doubly-sublinear IPPs, where both the verifier and honest prover use sublinear resources, and on (weighted) Hamming weight properties. For ordinary Hamming weight, we give a tolerant doubly-sublinear IPP. For completeness and soundness radii $\varepsilon_c<\varepsilon_f$ and gap $g=\varepsilon_f-\varepsilon_c$, a logarithmic-round instantiation uses $\widetilde{O}(1/g)$ verifier queries and $O(1/g^2)$ honest-prover queries, improving the cubic dependence of Amir, Goldreich, and Rothblum (ITCS 2025). We prove matching query lower bounds up to polylogarithmic factors. For distribution-weighted Hamming weight, black-box sampling requires $Θ(1/g^2)$ verifier samples but only $\widetilde{O}(1/g)$ evaluations; the quadratic sample complexity is necessary in the interior regime. With chosen-randomness access, the problem reduces to ordinary Hamming weight, yielding $\widetilde{O}(1/g)$ calls and evaluations. If the parties' evaluators disagree arbitrarily on a $ρ$-fraction of the distribution and by at most $γ$ elsewhere, our protocols remain doubly sublinear whenever $g>2κ$, where $κ=ρ+(1-ρ)γ$. Applications include auditing accuracy, group fairness, calibration, harmlessness, usefulness, and average-case robustness.

Authors: Thomas Schuster, Andreas Elben

A confluence of recent works has shown that many quantum circuits and dynamics are efficiently simulable by classical algorithms that track local information, even when conventional complexity measures such as the entanglement and magic are high. Here, we introduce a novel measure of complexity, the reactivity, to capture this new method of classical attack. Unlike conventional complexity measures, the reactivity does not capture a property of a quantum state or operator in isolation, but rather a quantum experiment as a whole. We provide numerical and rigorous evidence that quantum experiments with low reactivity are simple by a host of measures: they are efficient to classically simulate, learn, and fast-forward. This motivates the search for quantum experiments with high reactivity, which may evade these simplistic features. To this end, we introduce easily implementable experimental protocols---dubbed Pauli path spectroscopy---that allow one to efficiently measure the reactivity of any quantum experiment of interest. Our protocols are applicable even when the experiment itself is beyond the reach of classical simulation.

Authors: Aayush Rath, Lakshya Jindal, Antony Thomas

Motion planning in robotics requires not only computing collision-free paths but also certifying infeasibility when no such path exists. Complete methods are limited to low-dimensional spaces, while sampling-based planners scale efficiently but cannot provide finite-time infeasibility certificates, leaving this problem largely unresolved in high-dimensional spaces. In this letter, we present a geometry-driven framework for certifying infeasibility through an explicit resolution-dependent analysis of configuration space topology. Leveraging signed distance field representations, the proposed method traces separating manifolds induced by obstacle boundaries directly in configuration space, enabling both detection of infeasibility and identification of the specific geometric cause. To address computational challenges, we develop a parallel frontier-expansion algorithm that exploits GPU acceleration for efficient simplicial reconstruction in high-dimensional spaces. We validate the approach on 4-DOF and 5-DOF robot scenarios, certifying infeasibility within seconds for 4-DOF cases and under four minutes for 5-DOF cases. We further discuss avenues for improving scalability to higher-dimensional spaces.

Authors: Siyi Wang, Alexandre Leblanc, Paul D. McNicholas

We introduce \emph{curve band depth} (CBD), a band-based data depth for samples of \emph{unparameterized} planar curves. CBD is motivated by band depth and modified band depth for functional data, but targets trajectory data. Unlike the halfspace-based curve depth of \citet{de2021depth} and the curve stabbing depth of \citet{durocher2023csd}, CBD is defined through a geometric band region generated by two curves, and measures the arc-length proportion of a target curve lying inside such bands. We develop a CBD family consisting of an integral version (int-CBD), an infimal version (inf-CBD), and a fast-walk variant (FW-CBD). The fast-walk band is a narrower band construction contained in the global convex-combination band. We establish boundedness, vanishing at infinity, and similarity invariance for these constructions, together with a Borel-measurability result for the induced depth maps under a mild measurability assumption. A length-penalized variant is proposed for samples with heterogeneous curve lengths. We implement the methods via arc-length sampling and polygonal approximations, and evaluate them through classification of overlapping handwriting data and MNIST-derived digit curves, online-signature screening on \texttt{MOBISIG}, and an exploratory clustering task based on decomposed band contributions.

Authors: Kevin Woytowich, Nkechi Nnadi, Elizabeth Munch

In this paper, we provide a construction of an acyclic discrete vector field that is compatible with a total order associated with a lower star filtration on a simplicial complex, called the colex vector field. We show that the colex vector field induces a filtered acyclic vector field, whose resulting Morse complex computes the persistent homology of the lower star filtration on the underlying simplicial complex. We show that the colex vector field can be recomputed quickly when the vertex function that induces the lower star filtration is modified via order-adjacent vertex swaps. We provide a framework for storing and computing the number of paths between cells in the simplicial complex, as well as a method to update these values quickly when the colex vector field changes. Finally, we provide publicly available proof-of-concept code for the ideas shown. When applying it to the Persistent Homology Transform, we show that its runtime is comparable to a more standard matrix reduction approach.

Authors: Xiao Zhan, Chrystiano Araújo, Kangle Deng, Maneesh Agrawala, Hsueh-Ti Derek Liu, Mina Konaković Luković

We present a neural method for adaptive triangle mesh refinement, in which an autoregressive model adds geometric detail to selected regions of an input mesh while leaving the rest unchanged, a key capability for efficiently allocating mesh budget. Existing upsampling methods struggle to achieve this. Classical subdivision schemes refine triangulation without semantic awareness of the underlying shape or the ability to recover geometric details missing from a coarse input. Recent neural mesh models generate shapes globally, sacrificing region-specific control. We propose a novel tokenizer that yields combinatorially many valid upsampling trajectories from a single mesh. Trained on such data, our locally-conditioned autoregressive architecture allows for direct manipulation of topology and geometry within target regions of an input mesh. We validate our method against state-of-the-art approaches and demonstrate its ability to perform adaptive upsampling with region-selective control, a capability absent from existing approaches. This unlocks inference-time view-dependent refinement, physics-aware region refinement, and coarse-shape conditioned novel mesh synthesis. We provide code at https://github.com/seanxzhan/learned-localized-mesh-refinement/.

Authors: Sarah Tymochko, Gillian Grindstaff, Abigail Hickok, Jiajie Luo, Mason A. Porter

We develop a framework to use multiparameter persistent homology (PH) to examine access to heterogeneous-quality resources and exposure to heterogeneous-severity nuisances in a geographic region. Persistent homology, which is a type of topological data analysis {(TDA)}, has been employed previously to examine resource coverage. Unlike prior approaches, which used one-parameter PH to study resource coverage and nuisance exposure, our method accounts for heterogeneous-quality resources. Our framework, which employs a computationally-efficient approximation of multiparameter PH, allows one to study access to any resource ({or} exposure of any nuisance) using any notion of quality (or severity). Using the city of Chicago as an example region, we employ our framework to detect clusters of poor access to public parks, overexposure to landfills, and both underexposure and overexposure to pubs and bars.

Authors: Konstantin Sorokin, Aleksandr Levin, Maxim Beketov, Anton Ayzenberg

Vietoris-Rips filtrations, which are standard in topological data analysis, are flag complexes, and a simplex tree stores these without any attaching data. In this paper we ask what survives of this economy when a flag complex $K$ is divided by a subcomplex $A$, each connected component of $A$ being crushed to a point. Such a quotient is a CW complex whose cells are the simplices of $K\setminus A$, but their attaching maps are no longer implicit. We show that for flag $K$ the face order of the quotient is strictly graded exactly when $A$ is flag, and that the surviving labelled cells are determined by those of dimension at most 3. For $m$-flag pairs the threshold is $2m+1$, and it drops to $m+2$ when $K$ is flag. The prescribed cells form a regular CW decomposition only when $A$ is full in $K$. These results justify the QF-tree: a cell table that stores, for each surviving simplex, its ordered list of $d+1$ facets with collapsed facets flagged, indexed by a trie of quotient-vertex words. For bounded dimension its size is linear in the number of surviving simplices plus the retained provenance, and we derive and verify a simple formula for the collapsed fraction above which it is smaller than the homotopy-equivalent cone model. Because a collapse changes the attaching data only on the closed star of $A$, the QF-tree can also be applied locally inside a simplex tree. For a ball-shaped $A$ in the sampled Vietoris--Rips regime the closed star is a thin shell, and the median compact budget is below the cone model at every sampled radius. An accompanying library, modelled on Gudhi, implements the QF-tree, its local variant, an editable layer with local quotient updates, gluing, disc attachment, induced maps, cup products, fundamental-group presentations and zigzag persistence, and provided experiments separate the cost of maintaining a quotient from the cost of the algebra computed on it.

Authors: Millend Roy, Soham Samal, Ivan Zelich, Krzysztof Marcin Choromanski

We present a new class of near-linear algorithms for efficiently integrating general tensor fields defined on trees with distance dependent kernels, the Structure-Adaptive Tree Field Integrators (STAD-TFIs). STAD-TFIs exploit the tree's underlying structure through decompositions built around path backbones and single vertex separators, and use two-dimensional fast Fourier transforms to compute interactions jointly. By exploiting this structural information, STAD-TFIs achieve more computationally efficient integration than their regular efficient tree field integrators (TFI) counterparts. We provide a detailed theoretical analysis of our proposed approach and complement it with an exhaustive empirical evaluation, ranging from speed tests on synthetic trees, through accelerated Sinkhorn-based relaxations of the Optimal Transport algorithms on real meshes, to Topological Attention Transformers for vision tasks. To the best of our knowledge, we provide some of the first results showing that efficient to compute and accurate relaxations of the geodesic Sinkhorn-based solutions of the Optimal Transport problem can be derived by applying fast TFI methods.

Authors: Yichen Huang, Yuqi Pan, Michael Mitzenmacher, Milind Tambe, Yiling Chen

We study the trade-off between squared-error accuracy and incentive compatibility in linear regression. Agents report private labels associated with publicly known features and prefer predictions close to their true labels. Ordinary least squares (OLS) need not elicit truthful reports. For regression with $d$ parameters, we design a deterministic group-strategyproof mechanism achieving a $(d+1)$-approximation to the least-squares optimum and prove optimality even among universally strategyproof randomized mechanisms, answering an open question of Chen et al. (EC 2018). Relaxing universal strategyproofness to strategyproofness in expectation reveals a sharp separation: squared individual loss retains the factor $d+1$, while absolute individual loss admits the tight ratio $2-1/(\lceil d/2\rceil+1)$.

Authors: Sandip Das, Sweta Das, Sk Samim Islam, Ritam Manna Mitra, Aashirwad Mohapatra, Arkaprava Paul

The vertex integrity of a graph $G$ is the minimum of $|S|+\max_{C\in\operatorname{cc}(G-S)}|V(C)|$ over all vertex sets $S\subseteq V(G)$, where the maximum is zero if $G-S$ is empty. We study its exact exponential complexity in terms of $n=|V(G)|$. First, we give a reduction from Vertex Cover on subcubic graphs that increases the number of vertices by only a constant factor. Consequently, unless the Exponential Time Hypothesis fails, Vertex Integrity admits no $2^{o(n)}n^{O(1)}$-time algorithm. We also give a deterministic exact algorithm running in $O(1.9602^n)$ time and space, improving on the direct $O^*(2^n)$ algorithm. Its key ingredients are a balanced partition of the components left by an optimal irredundant separator and a subset dynamic program restricted to sets of at most $\lceil 2n/5\rceil$ vertices. An optimal separator can be recovered within the same bounds.

Authors: Ijay Narang, Yukai Tang

We give a randomized polynomial-time algorithm that, for every fixed $\varepsilon > 0$, colors every $3$-colorable $n$-vertex graph using $O\bigl(n^{(13-\sqrt{97})/18+\varepsilon}\bigr) \approx O\bigl(n^{0.17506+\varepsilon}\bigr)$ colors, improving upon the previous best bound of $O(n^{0.19539})$ from Bansal, Huang, and Lee. Our improvement comes from analyzing higher-level neighborhoods through a recursive description of failure in Gaussian SDP rounding. If the rounding returns too small an independent set, it produces local Gaussian certificates at every vertex of a nonempty induced subgraph. We propagate these certificates along walks to higher-level neighborhoods by defining a recursive certificate structure and proving a strengthened cover-composition lemma, which refines the one of Arora, Chlamt{á}{č}, and Charikar. We then construct a bounded potential function that increases by a fixed positive amount at every propagation step, yielding a contradiction. Consequently, the rounding must produce a sufficiently large independent set.

Authors: Junho Hwang

In offline temporary tasks assignment, each job has a time interval and a positive weight and is assigned to one of $r$ identical machines for its entire interval; the goal is to minimize the peak load, the largest total weight of jobs that are simultaneously active on one machine. For every fixed $r$, we give an efficient polynomial-time approximation scheme (EPTAS) with running time $f(r,1/\varepsilon)\cdot N^{O(1)}$, where $N$ is the input length. The previous approximation scheme, by Azar, Regev, Sgall, and Woeginger (2002), runs in time $n^{O(r^3\log r/\varepsilon^3)}$ on $n$ jobs. We also show that for every fixed $r\ge2$ the problem is strongly NP-hard, so it has no FPTAS unless P=NP, and that under the Exponential Time Hypothesis no deterministic $(1+\varepsilon)$-approximation runs in time $2^{o(1/\varepsilon)}\cdot N^{O(1)}$. The key idea is to bound the loads of each group of simultaneously active jobs by a few weighted intervals whose positions are fixed in advance; a dynamic program over the time line then only has to record which machine carries each interval.

Authors: Raoof Zare Moayedi, Amir R. Asadi, Mohammad Hossein Yassaee, Gholamali Aminian

Generating differentially private synthetic data with meaningful Wasserstein utility guarantees is challenging in high dimensions. For datasets of size \(n\) on $[0,1]^d$ with $d\ge2$, existing pure \(\varepsilon\)-differentially private mechanisms achieve expected $1$-Wasserstein error of order $(\varepsilon n)^{-1/d}$, reflecting the curse of dimensionality. While this rate is optimal in the worst case, it can be overly pessimistic when the data are supported on a lower-dimensional set. We formalize this through a multiscale packing-growth dimension $k$, which captures the geometric complexity of the support via the growth of packing numbers across scales. We propose \emph{Adaptive Pruned-PMM}, a pure $\varepsilon$-differentially private mechanism that combines private depth selection with our pruned variant of the Private Measure Mechanism (PMM) of He et al.\ (2023). The mechanism supports deeper, geometry-adapted hierarchies with expected running time $O\!\left(d(n+d)\log(\varepsilon n)\right)$, which is near-linear in $n$ for fixed dimension and privacy budget. Under an external multiscale packing-growth condition with dimension $k$, we show that, for fixed positive privacy budgets and fixed geometry, the expected $1$-Wasserstein error is of order $(\varepsilon n)^{-1/k}$ for $k>1$ as $n$ grows. We also prove a lower bound under a corresponding internal packing-growth condition, showing that the exponent $1/k$ is sharp within this framework.

Authors: Tatsuya Gima, Yasuaki Kobayashi, Hiraku Morimoto, Yota Otachi

For an instance of a combinatorial optimization problem, a \emph{forcing set} is a set of elements such that there is a unique optimal solution including it. Symmetrically, an \emph{anti-forcing set} is a set of elements such that there is a unique optimal solution excluding it. In this paper, we study the problems of computing smallest forcing and anti-forcing sets for two classical cut problems, \textsc{Global Min Cut} and \textsc{Min $s$--$t$ Cut}. We also consider variants in which the optimal cut to be uniquely determined is given as input. For each of these problems, we either give a polynomial-time algorithm or prove \NP-completeness.

Authors: Nikhil Bansal

We give an exposition of the recent polynomial time algorithm of Guo, Fang, and Lu for the Komlos problem. We simplify various arguments, and highlight the key new spectral potential idea and how the algorithm follows naturally from it.

Authors: Mayank Goswami, Adarsh Srinivasan

We study the problem of generating diverse solutions to Max-$k$-CSP and bounded-degree $k$-SAT, focusing on two distinct metrics: constraint diversity and variable diversity. For constraint diversity, the goal is to output $s \geq 2$ assignments to the CSP such that each assignment satisfies a $c$-fraction of the constraints, while maximizing the diversity among the $0$-$1$ indicator vectors of satisfied constraints in the Hamming metric. By reducing this to a multi-criteria optimization problem, we design $poly(n,s)$ time approximation algorithms that return s assignments achieving provable bi-criteria guarantees on both the fraction of satisfied constraints and diversity of the constraint vectors. For variable diversity, the objective is to maximize the Hamming distance between the assignments, while also maximizing the number of constraints satisfied. For Max-$k$-CSP instances when the desired number of solutions is $s=2^{O(n)}$, we implicitly represent these diverse approximate solutions by constructing linear codes within the solution space. Finally, we investigate variable diversity for $k$-SAT in the Lovász Local Lemma regime. In this setting, we establish NP-hardness for the exact diversity problem (computing the diameter of the solution space) and provide a polynomial-time approximation algorithm to efficiently generate diverse satisfying assignments.

Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Silvio Lattanzi, Danny Mittal

Graph Neural Networks (GNNs) are widely used for representation learning on graphs, but most methods assume static topologies, making them inefficient on evolving networks where edges change over time. Existing dynamic approaches either model graph evolution through temporal GNN architectures without focusing on efficient dynamic maintenance, or are restricted to linear propagation models based on Personalized PageRank. In this work, we study how to efficiently maintain node representations for non-linear GNN propagation under edge insertions and deletions. The propagation has no learned parameters, and only a classifier applied afterward is trained. For a broad class of standard activation functions, we develop a residual-based dynamic algorithm that selectively propagates local errors via push operations, maintaining an approximation to the evolving fixed point without full recomputation. We prove that our method achieves amortized $O(1/ε)$ update time per graph change under a degree-normalized error guarantee. Our approach uses a potential-based analysis in a degree-scaled norm and, in contrast to prior work on the linear case, requires no randomness assumptions on either the update sequence or the input vector. For the linear special case, we additionally provide an exact dynamic algorithm via low-rank matrix inverse updates. Experiments on benchmark datasets show that incorporating non-linearity improves accuracy while preserving efficient update performance, yielding a scalable and theoretically grounded method for maintaining this propagation on dynamic graphs.

Authors: Krzysztof Marcin Choromanski, Derek Long, Ananya Parashar, Dwaipayan Saha

\textit{Gromov-Wasserstein Distances} (GWDs) provide quantitative ways of comparing probabilistic distributions defined on different metric spaces by applying techniques from the optimal transport theory. As such, GWD can be potentially useful in a large variety of applications ranging from graph matching problems to 3D object detection. However its practical use at scale is significantly limited by cubic time complexity computations involving dense intra-space distance matrices. Even though in the Euclidean metric spaces several techniques (e.g. involving scalable kernel methods) were proposed to address it, to the best of our knowledge, analogous techniques for general geodesic distances on manifolds, or shortest-path distance on graphs in their discretized variants, were not developed. In this paper, we present \textbf{E}fficient \textbf{G}eodesic \textbf{Gro}mov-\textbf{W}asserstein methods (EGGroW), a new class of efficient algorithms designed to calculate geodesic Gromov-Wasserstein distances with entropic Sinkhorn-like approaches, leveraging recently introduced \textit{GenusSink} methods \citep{genussink} and the theory of random features. We provide important downstream applications, namely: 3D pose estimation and 3D template detection. In the latter setting, we formulate a partial 3D template recovery as a staged problem: capacity-constrained scene selection is followed by semi-relaxed recovery of template visibility and correspondence. Our empirical findings show that EGGroW provides accurate solutions when standard Euclidean-based techniques fail and is characterized by light computational footprint, as our theoretical analysis predicts.

Authors: Ron Kupfer

In the unrestricted polynomial decision-tree model, only the number of polynomial sign tests is charged. A parity test asks for the sign of a product of pairwise differences. Such tests underlie low-depth randomized algorithms for maximum finding and top-$k$ selection, but their usual analysis assumes distinct inputs because a tie makes the product vanish. We give a black-box lifting theorem that removes this assumption. After $O(\log n)$ polynomial tests determine the number of nonzero pairwise differences, every subsequent parity test is simulated by one polynomial test, consistently with a fixed lexicographic tie-breaking order. The simulator is an elementary symmetric polynomial in masked first and second powers of all pairwise differences. Thus a depth-$D$ parity-test tree on distinct inputs becomes a polynomial decision tree of depth $D+O(\log n)$ on arbitrary inputs, with no increase in randomized pointwise error for order-selection problems. We obtain maximum finding in depth $O(\log n[\log n+\log(1/δ)])$ with error $δ$, and top-$k$ selection in depth $O(\log^2 n+k\log n)$ with inverse-polynomial error, both without any promise on ties.

Authors: Wojciech Wawrzyniak

We give a deterministic $(8+\varepsilon)$-approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every $\varepsilon>0$. This improves the previous ratio $11+\varepsilon$ obtained by Heydt et al. The ratio is near-optimal in this model: its leading constant is only one above the known lower bound of $7$. Our result closes three quarters of the previous gap, reducing it from $4$ to $1$. Our main contribution is a sharp structural bound. For any dominating set $D$, assigning each vertex outside $D$ to a neighboring center gives disjoint owner blocks. If $k_x$ counts the other blocks containing a neighbor of $x$, then $\sum_{x\notin D}(k_x-2)^+\le(4|D|-12)^+$, where $z^+=\max\{z,0\}$. The bound holds for every such assignment, and equality holds for arbitrarily large minimum dominating sets. We use this bound in their three-phase framework, with new parameters and the same final linear-programming procedure. The algorithm requires neither a planar embedding nor the graph size, and its round bound depends only on $\varepsilon$. The transfer theorem of Bonamy et al. also gives a deterministic $(25+\varepsilon)$-approximation on graphs of bounded Euler genus, with a round bound depending only on $\varepsilon$ and the genus.

Authors: Daniel Lokshtanov, Saket Saurabh, Jie Xue

We consider Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size $k$. We give a randomized algorithm with one-sided error running in time $(2+\sqrt5)^k n^{O(1)}= 4.24^k n^{O(1)}$, and a deterministic algorithm running in time $8.04^k n^{O(1)}$. Both algorithms use polynomial space. To the best of our knowledge, these are the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs. This contrasts with general digraphs, where the best known algorithms run in time $2^{O(k\log k)}(n+m)$, and whether a $2^{o(k\log k)}n^{O(1)}$-time algorithm exists remains a major open problem. Our main tool is an exact Euler-type counting identity for plane digraphs. It shows that every small solution must carry a large share of the vertices whose in- and out-arcs alternate in the embedding, while solutions avoiding such vertices can be computed by reducing to Directed Feedback Arc Set, which is known to be solvable in polynomial time on planar digraphs via the Lucchesi-Younger theorem.

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu

We study online covering in which each instantaneous service pays its purchase cost and one maximum waiting time, with no effect on future requests. For static realizable services, monotone subadditivity suffices for optimal competitive ratios; submodularity is unnecessary. A normalized monotone subadditive lower-bound oracle with realization factor $ρ$ yields ratios $ρ+1$ deterministically and $1/(1-e^{-1/ρ})$ randomly against an oblivious adversary. Exact batch optimization gives the optimal constants $2$ and $e/(e-1)$. The randomized algorithm uses one global threshold on a seed-independent virtual-height trajectory, whose active time is a lower bound on the offline optimum. Weighted vertex cover gives a strict separation from submodularity on a three-edge bipartite path, with polynomial-time batch implementations through min-cut and LP rounding. An offline consecutive-batch normal form also transfers static approximation guarantees to the offline problem.

Authors: Bar Mahpud, Daniel Omer, Or Sheffet

We study the problem of approximating the John ellipsoid (JE) of a given (centrally symmetric) polytope of $n$ constraints in a Euclidean space under differential privacy (DP). We give the first differentially private algorithm for this problem under the standard model, where neighboring datasets may differ arbitrarily in one a single constraint. Our work also extends to the complimentary problem of Minimum Enclosing Ellipsoid of $n$ points in the Euclidean space. Our approach is based on the recent non-private multiplicative-weights algorithm of~\cite{pmlr-v99-cohen19a}. First we introduce a non-private generalization of the Cohen et al algorithm, yielding a $(1+γ)$-approximation of the JE problem while violating at most $κn$ constraints in $O(\log(1/κ)/γ)$ iterations. This variant works by projecting the intermediate weights assigned to the constraints onto the set of $κ$-dense distributions, similarly to~\cite{bun2020efficientnoisetolerantprivatelearning}. We then design a $ρ$-zCDP variant of this algorithm by adding Gaussian noise to the weighted covariance matrix aggregated in each step of the algorithm. Under a mild goodness assumption on the data we can assert that the resulting noisy matrix is close to the true matrix, thereby achieving essentially the same guarantee as the non-private algorithm provided sufficiently many input points. Thus our method achieves an efficient DP poly-time algorithm under concrete sample complexity bounds.