Theory of Computing Report

In case you’ve been worrying that the recent publicity blitz of LLM solutions to open mathematics problems is causing us to run short, there are two more mixed in among my usual links here. Because I haven’t solved them, they are not very precisely formulated, and I don’t know how difficult or interesting they are nor even whether someone else might have already considered them; that’s often the way at the start of research.

• I think maybe I need to start bringing my DSLR along again when I go to the beach (\(\mathbb{M}\)) rather than relying on my cell phone camera (Pixel 6 Pro, yes I know it’s getting old now). Here’s what it thinks a crashing wave looks like, without additional processing except for a bit of a crop. To me it more resembles the kind of molded privacy glass that one uses for a bathroom window.

  

• Amazon buys rare books to destructively scan them for AI training (\(\mathbb{M}\)).

• An abbreviation of abbreviation, misspelling of misspelling, and more of the kind from the depths of Wiktionary.

• Rotating points on four circles form a polygon of constant length by Jim Propp, inspired by Chuck Hoberman’s “Nested Loops” exhibit at the Museum of Mathematics.

• A cursed triangle in the Moulton plane.

• If you’ve been working with tagged pdf files in Adobe Acrobat (\(\mathbb{M}\)), you may have noticed an annoying banner that it displays at the top of the window whenever it opens a tagged pdf file: “This file claims compliance with the PDF/A standard and has been opened read-only to prevent modification”. If this banner were only in the default view of Acrobat it might be more easily ignored, but it has no checkbox to make it go away and remains visible even in presentation mode (like, if you’re trying to present a lecture using a tagged pdf file). The only obvious way to make it go away is to click a button labeled “enable editing”, which you might think you don’t want to do.

  It turns out that you can disable these banners entirely. In the preferences window for Acrobat, go to the “Documents” page and change the setting for “PDF/A View Mode” from “Only for PDF/A documents” to “Never”. I suspect that this also disables the automatic read-only setting for these files but I don’t think that’s a problem.

• Editorial board of Games and Behavior, the journal of the Game Theory Society, resigns (\(\mathbb{M}\)), after its publisher Elsevier replaces its editor-in-chief without consultation with the board, for “closer alignment with Elsevier strategic priorities”. The link leads me to wonder: where is the involvement of the society itself in these decisions?

• I created this image over a year ago for my CCCG 2025 talk “Decremental greedy polygons and polyhedra without sharp angles” (\(\mathbb{M}\)), but I don’t think I posted it (or the talk slides) online until now. This is what you get from the following process: start with the infinite set of integer points in the positive quadrant, and then repeatedly clip off the point that makes the sharpest angle on the convex hull. As you do this, at certain points you will reach curves for which the sharpest angle is less sharp than for any earlier curve; those are the ones shown in blue. The yellow quarter-circle is added separately for comparison.

  

  Research problem 1: I don’t understand why the blue curves are so irregularly spaced nor why some of them appear so visually close to quarter-circles. Explain?

• Physics papers are written in LaTeX (\(\mathbb{M}\)), video by Angela Collier. I doubt anyone here doesn’t already know all this, but it’s a good explainer of why researchers in mathematics/physics/theoretical computer science/linguistics etc. almost universally prefer LaTeX to Word, how the two differ, and why you can infer that a paper in Word was probably not written by a professional. Also with an entertaining rant about why Word is bad, how it’s getting both worse and more expensive, and why you should not pay for it.

• Digit Party: Three years of lying about high scores (\(\mathbb{M}\)), and how authors Robert Brignall and Vince Vatter switched to integer linear programming in order to finally compute exact high scores for their online digit-clustering puzzle, digit.party.

• A set of five 60-sided go-first dice (\(\mathbb{M}\), via), found in 2023 by Paul Meyer through efforts coordinated by Auburn University lecturer Eric Harshbarger. These are five dice, labeled so that no two include the same numbers, with equal probabilities of rolling the highest number in all combinations of up to five dice. More strongly Wikipedia states that these dice are “permutation fair”: each permutation of the rolling players is equally likely. Now their discovery is commemorated by a giant set of these dice installed in the Auburn University STEM + Agricultural Sciences Complex.

• Tsuidoku (\(\mathbb{M}\)),a sudoku variant in which you must fill in the usual 9x9 sudoku grid with both nine digits and nine colors, and must end up with one of each digit-color combination.

  To me the biggest drawback is that the solved puzzles tend to have a stripy pattern like the patterns visible in the sudoku grids packed with 3x3 Latin squares from my recent blog post (both in their colors and digits) and when you detect this pattern it makes the puzzle much easier to solve. Also I’m not a fan of the style of gameplay that announces your mistakes immediately and lets you correct them; I think it makes puzzles trickier (and therefore more interesting) when you have to figure out that you’ve made a mistake yourself and undo back to where you made it. I checked that the nine colors appear distinguishable under the most common form of color blindness (at least to my normal vision eyes using a simulator) but their color contrast was not great, and there are three pairs of indistinguishable colors under blue-blind color blindness (tritanopia).

  All that said, I think the higher levels are tricky enough to be interesting. And (research problem 2) I am intrigued by the question of whether the stripiness is an implementation flaw or a necessary emergent feature of these game rules at this board size.

• Video on the motion and rigidity of hyperboloids made from sticks (\(\mathbb{M}\)), by Sabetta Matsumoto, Tim Reinhardt, Jürgen Richter-Gebert, and Henry Segerman, in part centered on a large public artwork with this form, Mae West in Munich.

• Hyperchoreography (\(\mathbb{M}\)), solutions for \(n\)-body problems in more than three dimensions.

By David Eppstein

Hi there, argmin readers! As the fall semester picks up, posting volume will, too. So I’m going to commit to writing short descriptive headers to help you sort through the different threads.

Today’s post is by Jessica Dai, writing up her thoughts on the microconference on “public feedback for AI and beyond” that she ran at UC Berkeley in August. -Ben

Much of the conversation on A(G)I’s “risks and opportunities” centers on as-yet unrealized near- (or far-) future possibilities. Yet AI is already changing the world; its societal impact is already being felt in real time by real people. There’s a yawning gap between “AI elites” — frontier labs and academics and the online AI commentariat — and everyone else, in both beliefs and priorities. I think this is bad — medium- and long-term outcomes will also depend on how society experiences the near-term.1

My vision for dealing with this is something I’ve started calling “public feedback for AI.” The logic goes something like this:

Proposition 1. “The public” has interesting and important things to say about their experiences with AI, but are not typically listened to by decision makers.

Proposition 2. “Evaluations” — and aggregated information, more broadly — are useful, in the sense that they can influence consequential decisions.

Corollary. AI evaluations from public feedback can be a meaningful way to “do something” about the emergent misalignment between those who control AI development and literally everyone else.

I’ve spent the past few years working on this from various angles — trying to articulate why this might be a good idea, methods work for concrete audit instantiations, finding empirical evidence that user-generated content can tell us something useful about AI safety. But the more I think about these problems, the clearer the gaps in my own knowledge; there are many people who are smarter than me, who have worked on related problems for longer than I have, or who have new and different perspectives than those I’m exposed to in my local circles. And while there are a wide range of research questions that I find intellectually interesting, this clearly can’t remain a thought experiment.

Thus, microconference. (You can see a blurb, agenda, and list of attendees at publicfeedback.ai.)

I had a lot of fun at this workshop because while there were some fundamental philosophical questions threaded throughout the two days, everyone was ultimately interested in doing things beyond sending PDF preprints around to one another. And I’m really grateful for everyone’s engagement, because it helped me refine my thinking around each of the foundational ‘propositions’ underpinning the broader vision.

This write-up will be structured around the two ‘propositions’ I outlined above (rather than following the agenda directly). Additionally, I’ll stick closely to what was actually discussed at the workshop, so there is certainly lots of relevant literature that I’m not including here. Editorializing here is mostly mine, and if something is stupid or upsetting, blame me and not whichever speaker I’m referencing!

The first major question I wanted to cover is a core tension that ‘Proposition 1’, as written, glosses over: Who is the public?

While I won’t attempt to do armchair democratic theory here — though if there are any political philosophers reading this, I would love to chat — having clearer and better-motivated answers to this question seems important, because who is considered relevant also directly affects what concerns are substantively important, and also how their views can be understood.

Users?

I started us off on Monday by sharing a few plots from my paper analyzing r/ChatGPT, where we argue that anonymous Reddit data can help us understand broader societal impact; the claim is that the population of “r/ChatGPT posters” can help us simultaneously access a true “population of ChatGPT users” and something about the topics they cared about. I think this was broadly true for the time period we analyzed, but “ChatGPT users” is a very particular choice for defining a “public.”

Nevertheless, if we think AI impacts are largely realized through their users, then usage data is critical to measuring that impact. To this point, the first half of Shayne Longpre’s talk covered the newly launched AI Observatory project, a heroic effort to pull together as many real transcripts as one might reasonably find available on the internet, and to release and analyze them together as a corpus of usage data. Still, there are fundamental challenges with trying to reconstruct proprietary data from the outside; I’m cautiously optimistic about Anthropic’s (very new! Hot off the presses!) data release program.

Study participants or poll respondents?

A common adjective I’ve seen people use to describe chatlogs and other usage data is naturalistic: it reflects the real context in which users were engaging with the AI product. But this data has limitations; it is purely observational, which makes representativeness concerns all the more salient, and cannot provide context beyond the interaction itself (e.g., motivation or outcomes of usage). Instead, the typical approach to “human data collection” in academic contexts is to run more structured studies: recruitstudy participants and ask them to answer survey questions or complete tasks. While this allows researchers the ability to study more detailed questions, these studies have their own limitations; Serina Chang’s talk traced this tradeoff explicitly, with naturalism and control substituting directly for one another.

One issue that came up in discussion was about who these study participants were. Why should we expect that the data they generate is in any way “representative” of the constructs that researchers are trying to measure? A typical academic study promises a pay rate of up to $10/hour (the current standard recruitment platform is Prolific); this is below minimum wage in 30 US states. While $10 USD can be significant in a global context, we were unsure how to reason about the impact of this pay rate on the people who choose to participate.

This is a fundamental problem shared by public opinion polling (which is one reason why Ben hates it), and while it’s probably best not to read into more than one sigfig of poll results, there is reason to believe polls can be useful for coarse-grained judgments of vibe — especially when the vibes are off. Emma Pierson opened her talk with poll results showing the divergence between AI experts/ Claude users, who are generally positive about AI, and a demographically representative sample of the American population, who are generally negative. Jasmine Sun’s datacenter reporting was also motivated in part by national polls showing new datacenter construction polling on par with, or worse than, nuclear and coal. This stood in stark contrast to the SF tendency to dismiss datacenter opposition as merely a problem of misinformation.

Anyone who wants to report?

The approaches described above begin by recruiting people, then gathering their feedback within the explicit context and scope of a study (or poll). An alternative is an inversion of that paradigm: waiting for people to organically share feedback of their own volition, so that ‘the public’ is itself defined by the act of submitting a report. The second half of Shayne’s talk covered a flaw- reporting workflow that lets anyone create a report for an AI-related flaw, vulnerability, or incident, broadly construed, then sends it off to relevant parties. In terms of reporting accessibility, this system rhymes with a public incident reporting portal administered by the California Office of Emergency Services. As Deb Raji explained, this was created as part of SB53’s implementation. While this legislation was mainly directed at companies to self-report severe incidents (more on that later), there is also a provision for enabling public reporting.

Neither of these portals have shared the submissions received thus far, but they have similar design decisions that I suspect also lead to similar challenges (Algorithmic Justice League also has a harm reporting portal, and also hasn’t shared findings, as far as I can tell). Since literally anyone with the link can submit reports, these portals are likely susceptible to ‘low-quality’ submissions or spam. On the other hand, I would guess that overall submission volume is low, since awareness that these platforms exist is also low. I didn’t know about the SB53 portal until Deb’s talk, even though this is kind of my whole thing right now!

Start with an explicitly scoped community in mind, and go talk to them directly.

All three notions of ‘public’ described above involve a very convenient slippage between “public feedback” and “data collection”: they require configuring “the public” as a generic, anonymous mass from which data points can be sampled, and for which summary statistics can be computed. I don’t think this is always a bad thing, but it was striking to me that some of the most compelling case studies for effectively capturing “public feedback” started with an explicitly scoped community, and gathered information by having conversations with individuals within that community.

HCI researcher Samantha Dalal spoke about her work with the Workers’ Algorithm Observatory, which builds tools with gig workers to help identify, measure, and contest algorithmic systems. They bootstrapped worker outreach by collaborating with unions — existing legal entities with corresponding social networks. However, it was still necessary to have face-to-face conversations with workers to build trust and understand their needs.

Humphrey Obuobi shared his work with BLOOM, a nonprofit that is actively facilitating community dialogues in three counties in central Oregon. In this case, while BLOOM develops its own deliberative platform, I see the substance of their work as downstream of the specific, situated collaborations with local civic organizations which — like the unions in Samantha’s work — naturally scope participants to a more specific community.

Finally, Jasmine’s datacenter reporting was focused on understanding the popular backlash; this meant traveling to locations where backlash was visible or brewing. Of course, she talked to local elected officials, who were broadly responsible for decisions at the level of contracts and permitting, as well as activists who were leading more organized opposition. But she also spent a lot of time hanging out at county fairs and beer gardens, talking to people for whom datacenters may not have been the absolutely most salient issue in their lives, but who, nevertheless, turned out to have opinions when asked.

But wait, what about “unknown unknowns”?

I’ve often claimed that the major practical benefit of “public feedback” is the ability to support harm discovery — i.e., to surface unknown unknowns that a centralized decisionmaker (policymaker, company, etc.) might otherwise never think to look for. This seems, to some extent, at odds with the provocation above: doesn’t starting with a specific community in mind inevitably constrain the content of “public feedback” to known unknowns?

One reasonable response is that unknown unknowns exist even within well-scoped communities; prespecifying what groups of people one might be interested in doesn’t necessarily also require committing to particular outcomes or topics, especially if individuals are given the space to express their perspectives in their own voices (e.g., via semi-structured interviews instead of, or in addition to, providing yes/no answers or numerical ratings).

On the other hand, bottom-up community formation can and does already happen. Social media platforms are a natural and well-studied example: networks of like-minded people find each other through a mixture of organic encounters, algorithmic nudges, and moderation choices. For instance, after the initial release of GPT-5, a decentralized campaign to “bring back 4o” emerged on social media (mostly Reddit and Twitter); The Human Line is a research and advocacy group for survivors of AI spirals that emerged from initial encounters on Reddit.

Therefore, if working within communities (rather than a generic abstraction of “users” or “recruited participants”) can be uniquely effective, then perhaps we should try to build systems that explicitly help guide the development of communities based on common concerns. One of the projects covered in Wesley Deng’s talk was an end-user auditing tool called WeAudit, which intentionally included a deliberative and semi-social element that helped individuals contextualize their observations with other user-auditors. A similar motivation is behind an early-stage study shared by Eve Fleisig, where participants see other people’s experiences and can explicitly compare them to their own. In the universe of these projects, the community itself might emerge as an unknown unknown.

The other thing about “community” is that it’s likely of some intrinsic value to a participant — a very different source of motivation from the $10/h paid by Prolific. I’ll write more on the question of “what someone might get out of participating” in the next post.

Subscribe now

By jessica dai

BILL: Lance, I have a question and a meta question:

a) List all the presidents and vice presidents who were colorblind.

b) Do you know this sort of thing since you are colorblind, and hence

might have looked this up in the past?

LANCE: (b) No. And if Marco Rubio runs for president in 2028 he will need to earn my vote. He won't get it just for being colorblind. As for (a) I asked Claude.

Only one case is reasonably well documented, and it isn't a vice president. Bill Clinton is red-green colorblind: during the 1996 presidential debates, both Clinton and Bob Dole needed a modified cue-light system, since individual colored lights would have been hard for either of them to read, so a three-light arrangement was used instead — an anecdote that traces back to the Encyclopedia of Genetic Disorders and Birth Defects. Dole, of course, was Ford's running mate in 1976 and lost, so he never made it to the vice presidency.

Eisenhower is the other plausible case. His grandson David wrote that Ike confused browns and greens, sometimes asking for a brown suit when he meant green, and couldn't tell what color his golf balls were — someone had to write "DDE" on them. That's a family recollection rather than a diagnosis, but it's the kind of detail people don't invent.

Everything else you'll find online — Madison, Chester Arthur, Washington failing to distinguish crimson from scarlet, Lincoln calling lavender blue — comes from content-farm pages that cite nothing checkable, and I'd treat it as noise. Lincoln's documented eye problem was strabismus (eyes do not line up), not color vision.

As for vice presidents: I can't find a single one with any credible claim. That's a bit surprising statistically — roughly 8% of men of Northern European descent are red-green deficient, and with fifty-odd vice presidents you'd expect several. The explanation is almost certainly that nobody was looking. Color blindness is invisible unless someone asks, the Ishihara test only dates to 1917, and a nineteenth-century politician had no occasion to disclose it. Clinton's case surfaced only because television lighting forced the issue.

BILL: They left out Hubert Humphrey whose colorblindness was well known and well documented. It was why he was unable to serve in WW II. His not serving was used against him early in his career.

LANCE: I asked Claude about that and here is what it said:

Good catch — that's the vice-presidential case I missed, and it's better documented than anything on the presidential side. Humphrey tried to enlist after Pearl Harbor and was turned down three times, twice by the Navy and once by the Army, on account of color blindness along with other physical problems. Biographical accounts add that he also had a double hernia and lung scarring, possibly from unpasteurized milk.

This one holds up because it left a paper trail: military induction physicals in the 1940s included Ishihara-style screening, so his condition was formally tested and recorded rather than inferred from someone's recollection about suits or golf balls. It also mattered politically — the failed enlistment dogged him, since he was a young man of draft age who spent the war teaching and working for the WPA, and opponents used it against him in his early Minneapolis campaigns.

So the honest tally is one vice president (Humphrey), one president (Clinton), plus Eisenhower as a plausible unconfirmed case. Which, incidentally, undercuts the "nobody was looking" explanation I gave a moment ago — the real filter was that the condition surfaces only when an institution forces a test, and the military did that for exactly the cohort of politicians who came of age around the world wars.

BILL: SO, why did it get it wrong? This is not something  obscure which requires guesswork like speculating on whether Washington was colorblind (I can't tell scarlet from Crimson either).

LANCE: Google AI did even worse.

BILL-AI can solve Erdős problems, but it can't track down that Hubert Humphrey was colorblind. Why is that?

LANCE- Claude was just too lazy to check over the military records of every vice-president. AI are people too!

By gasarch

Authors: Azem Adibelli, István Tomon

We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tildeΩ(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.

Authors: Sidhant Saraogi

Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial method argument that controls collisions in sumsets of matching vectors.

Authors: Manuel Fernandez

We study $\ell_0$ isoperimetry for a convex body $K\subset \mathbb{R}^n$, $n\ge2$. For a Borel set $S\subset K$, let $\partial_0^K S$ be the set of points in $K \setminus S$ that can be reached from $S$ by changing at most one coordinate (i.e. the $\ell_0$ boundary of $S$). Suppose that, for some unconditional convex body $Q \subset \mathbb{R}^n$, numbers $r,R>0$, and possibly different centers $x_0,y_0$, \[ x_0+rQ \subset K\subset y_0+RQ. \] Writing $s=\text{vol}(S)/\text{vol}(K)$, we prove that whenever $0 0$ is an absolute constant. Consequently, the associated $\ell_0$-isoperimetric coefficient is at least $cr/(n^2R)$. Previous direct lower bounds were only known for $\ell_2$ and $\ell_\infty$ regularity whereas our lower bound holds directly for any $Q$-regularity, where $Q$ is an unconditional convex body. Compared to $\ell_2$ and $\ell_\infty$ regularity, our lower bound result improves upon the previously best known lower bounds, for any $s$, by a factor of $n$. As an application of our result, we give improved mixing time bounds for the Coordinate Hit and Run walk (CHAR). Our proof of the lower bound is based on a modification of the method of canonical paths applied to a continuous Hamming graph over our convex body. Our construction of canonical paths can be viewed as a suitable coordinate discretization of certain mass transport maps from $S$ to $S^c$. We also give complementary upper-bounds for any $Q$-regularity, with an overall factor of $n$ gap between the two.

Authors: Pedro M. M. de Castro

We consider an online geometric connection rule that stores one point of state. After processing $p_i$, the state is updated by $x_i=γx_{i-1}+(1-γ)p_i$, and the two segments from $x_{i-1}$ to $x_i$ and from $x_i$ to $p_i$ are retained. The design parameter $γ$ controls the persistence of the state. We minimize the sum of the $α$-powers of the resulting edge lengths under independent uniform input and under arbitrary input sequences. For uniform points in the unit ball, the stationary problem has a transition at $α=1$. Its continuous extension is minimized at the boundary for $0<α\leq1$, and every global minimizer is interior for $α>1$. The main result determines the finite optimizer in the joint window $α_N=1+\varepsilon_N$, $\varepsilon_N\log N\toλ$. Below an explicit threshold it lies on the $N^{-1/2}$ scale. At the threshold its scale is $\sqrt{\log N/(N\log\log N)}$, and above the threshold it approaches an explicit stationary root with two computable corrections. A second threshold identifies which correction governs the location, and differentiated estimates prove eventual uniqueness. At $α=3d+8$, the linear coefficient at the stationary endpoint changes sign and a branch of strict local maxima enters the parameter interval. Under arbitrary input sequences, the optimal parameter and asymptotic worst-case edge-power cost per processed point are explicit for $0<α\leq3$. At high powers, periodic blocks and a separation argument show that this optimized cost is asymptotic to $2\log2/\logα$. Exact results for powers two and four, a rational recursion for all even powers, and a high-dimensional expansion provide additional descriptions of the optimizer.

Authors: Gabriel de Azevedo, Ulysse Hennebelle

In ranked-choice voting, a Condorcet-winning set is a group of candidates for which no outside candidate is preferred to every member of the group by a majority of voters. We study Condorcet-winning sets in planar metric elections, where voters rank candidates according to their distance under a given norm. We formulate general metric elections, peer selection, and the one-round Voronoi game as instances of a two-player Stackelberg game and place these problems in a common hierarchy. We also introduce a new variant, which we call strong peer selection. Our main result concerns peer selection under the $\ell_1$ and $\ell_\infty$ norms. We prove that every planar instance admits a Condorcet-winning set of size at most three, even under strong peer selection. This follows from a new result for strong rectangular $\varepsilon$-nets. We show that, for every set of points in the plane, one can choose at most three input points that intersect every axis-parallel rectangle containing more than half of the points, improving the previous threshold of $9 / 16$ due to Ashok et al. Under the $\ell_2$ norm, we prove that every planar metric election admits a Condorcet-winning set of size at most four, improving on the general bound of five due to Song et al. Finally, we give new norm-independent bounds for the one-round Voronoi game.

Authors: Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein

The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has been known since the early 1970s that the optimal competitive ratio for any deterministic online allocator is $Θ(\log M)$, where $M$ is the volume high-water mark of the underlying request sequence. This paper begins with a simple observation: many real-world allocators seem to bypass the 1971 lower bound by adopting a slightly different model for memory allocation. These allocators use what we call $k$-aggregate request fragmentation, meaning that the memory allocator is permitted to break requests into multiple fragments, so long as the all-time maximum number of simultaneous fragments is at most $k$ times the all-time maximum number of simultaneous requests. We consider the following basic question: Does request fragmentation fundamentally change the problem of memory allocation, and if so, how? Our results come with several surprises. Among these, we find that even using $k = 1 + o(1)$ request fragmentation, the optimal competitive ratio---which was $Θ(\log M)$ in the classical setting---collapses to $Θ(\log \log M)$. This result is shown to be tight with matching upper and lower bounds, applying to both deterministic and randomized algorithms.

Authors: Nikhil Bansal, Haotian Jiang

A conjecture of Komlós states that the combinatorial discrepancy of any matrix $A\in\mathbb R^{m\times n}$ whose columns have Euclidean norm at most one is bounded by a universal constant. We prove that the combinatorial discrepancy of every such matrix is at most $O((\log n)^{1/4}(\log\log n)^{7/4})$. This is the first asymptotic improvement over the $O(\sqrt{\log n})$ bound established by Banaszczyk [Banaszczyk, Random Struct.\ Algorithms, 1998], and it refutes a conjecture of Hajela [Hajela, European J.\ Combin., 1988] that a lower bound of order $Ω(\sqrt{\log n})$ should hold.

Authors: Karthekeyan Chandrasekaran, Raymond Jiang, Krishna Kalathur

Motivated by non-uniform edge failures in network design, we introduce a multi-tier model of flexible graph connectivity. In k-tier Flexible Graph Connectivity (k-tier FGC), the input is an undirected graph G=(V, E) with non-negative edge costs, along with a classification of the edges into nested tiers T_1 subseteq T_2 subseteq ... subseteq T_k = E and non-negative integral tier requirements q_1 <= q_2 <= ... <= q_k. A non-empty proper subset R of vertices is safe if it is safe along one of the tiers, i.e., there exists i in [k] such that |delta(R) cap T_i| >= q_i. The goal is to find a minimum cost subset F subseteq E of edges such that the subgraph (V, F) has no unsafe cuts. The case of k=1 corresponds to the min-cost p-edge-connected spanning subgraph problem which is APX-hard. We design approximation algorithms for every fixed constant k for three variants of k-tier FGC: (i) for k-tier FGC, we design an LP-based logarithmic approximation, (ii) for min-cardinality k-tier FGC, we design a combinatorial approximation whose factor depends only on the tier requirements q_1 and q_k, and (iii) for k-tier Flexible Multi-Graph Connectivity, where we are allowed to use multiple copies of each edge while paying the cost of the edge for each chosen copy of the edge, we design an LP-based 2-approximation.

Authors: Lorenzo Beretta, Cameron Musco

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

Authors: Kushagra Chatterjee, Rojin Rezvan, Ali Vakilian

We study the \emph{connected $k$-median} clustering problem, a clustering problem that augments the classical $k$-median objective with connectivity constraints. We focus on the \emph{overlapping} variant of the problem, where clusters are allowed to share vertices. In addition to a metric space $(V,d)$, the input contains a connected graph $G$ on the same vertex set $V$ of size $n$. The goal is to select at most $k$ centers $C$ and assign vertices to them so as to minimize the $k$-median cost (i.e., $\sum_{v\in V} d(v,C)$), subject to the constraint that each cluster induces a connected subgraph of $G$. Since the metric space and the connectivity graph are independent, the problem is significantly more challenging than standard clustering. Eube et al.~\cite{eube2025esa} showed that even the assignment version is $Ω(\log n)$-hard to approximate and gave approximation algorithms with guarantees depending polynomially on $k$. We develop a configuration-LP-based framework that combines covering LP techniques with a rooted minimum-density oracle. For the assignment version, we obtain an $O(\log^2 n)$-approximation. For the general version, we develop a bicriteria framework that opens $O(k\log n)$ centers while achieving an $O(\log^2 n)$-approximation in cost. %Our results provide a different LP-based approach for handling connectivity constraints in clustering problems and demonstrate that configuration LPs, covering LPs, and rooted density oracles can be combined effectively to obtain approximation guarantees for clustering objectives under graph-theoretic constraints.

Authors: Nima Anari

The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of $(\sqrt{2})^n$. We improve the base of this exponential factor: for some absolute constant $c<\sqrt{2}$, there is a deterministic polynomial-time $c^n$-approximation for the permanent of every nonnegative matrix. This shows that the canonical Bethe guarantee is not a barrier for deterministic approximation of the permanent. The proof augments the Bethe lower bound with a new certificate tailored to matrices on which that lower bound loses nearly the full factor. The author supplied the high-level plan of attack, and the proof was developed in an interaction with ChatGPT 5.6 Sol Pro. The author subsequently verified the results. Codex assisted with proof checking, manuscript assembly, and typesetting.

Authors: Jiaheng Cheng, Agastya Vibhuti Jha, Haotian Jiang

Numerical integration---approximating the integral of a function $f$ using $n$ point evaluations---is a central task in science and engineering. The two main paradigms for this problem, the Monte Carlo and quasi-Monte Carlo methods, have distinct strengths and limitations, and a fundamental question is to design a method that combines the benefits of both. \smallskip Building on recent algorithmic advances in discrepancy theory, Bansal and Jiang \cite{BJ25a} gave a randomized QMC method that naturally bridges the MC and QMC error guarantees. Their method also achieves a surprising improvement over the classical Koksma--Hlawka inequality for QMC methods: it attains an error bound of $\widetilde{O}(σ_{\mathsf{SO}}(f)/n)$, where $σ_{\mathsf{SO}}(f)$ is a new notion of \emph{smoothed-out variation} that they introduced and showed to be substantially smaller than the Hardy--Krause variation governing the classical bound. \smallskip However, the analysis in \cite{BJ25a} is quite involved: it must carefully exploit the structure of the dyadic decomposition and the randomness of the algorithm inside a sufficiently fine discretization of the Hlawka--Zaremba formula to obtain cancellations among the high-frequency components in the Fourier decomposition of $f$. The contribution of this article is twofold: (1) We give an equivalent characterization of $σ_{\mathsf{SO}}(f)$ in terms of the Haar--Besov seminorm of $f$, relating this new notion of smoothed-out variation to classical quantities. (2) Through this characterization, we provide a conceptually simpler and more direct analysis of the Bansal--Jiang QMC method via Haar decomposition, bypassing the use of the Hlawka--Zaremba formula, Fourier decomposition, and the delicate cancellation arguments of \cite{BJ25a} that heavily exploit the structure of dyadic decomposition.

Authors: Edith Cohen, Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Alexander Knop, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Adam Sealfon, Marika Swanberg

We study differentially private (DP) $k$-means and $k$-median clustering in the online streaming setting. In this model, points arrive sequentially, and at each time step, we need to output a set of $k$ centers that optimizes the clustering objective for all points seen so far. We give a generic reduction that transforms the (sensitive) input stream into a private stream, which is a semi-coreset of the input stream. This implies that any (non-private) online clustering algorithm, run as a post-processing step, can achieve good utility for the original clustering objective. Our algorithm matches or improves upon the approximation ratio, space usage, and running time of existing algorithms [Epasto et al., 2026, Dupré la Tour et al., 2024]. A key aspect of our reduction is that it inherits desirable properties of the underlying non-private clustering algorithm, such as consistency [Lattanzi and Vassilvitskii, 2017]--a property not satisfied by previous DP algorithms.

Authors: Jiale Chen

We study dynamic maximum weight matching (MWM) under edge insertions and deletions in two settings: maintaining a $(1\pm\varepsilon)$-approximation to the optimum weight, and maintaining an explicit $(1-\varepsilon)$-approximate matching. Our main result is a reduction that transforms instances of polynomial aspect ratio into instances of aspect ratio $O(\varepsilon^{-1})$. The reduction applies to general graphs in both settings and is compatible with partially dynamic updates. The reduction is based on a structural property of local marginals. After grouping edges into weight classes, the global marginal contribution of one class relative to all lower classes is approximated by its marginal contribution within a local weight window of aspect ratio $O(\varepsilon^{-1})$. Summing these local marginals yields a value composition lemma that uses only approximate optimum values of the local windows. This improves the value reduction of Gupta and Peng (FOCS 2013), whose local aspect ratio is $\varepsilon^{-Θ(\varepsilon^{-1})}$. The same structural property yields an improved matching composition lemma for explicit matchings, reducing the local aspect ratio of Bernstein--Chen--Dudeja--Langley--Sidford--Tu (SODA 2025) from $O(\varepsilon^{-2})$ to $O(\varepsilon^{-1})$.

Authors: Navid Eslami, Ioana O. Bercea, Niv Dayan

Range filters are compact probabilistic data structures that answer approximate range emptiness queries. They are used in many domains, e.g., in key-value stores, to quickly rule out the existence of keys in a given query range and avoid searching for them in storage. However, all existing range filters exhibit at least one of three shortcomings: (1) they do not provide any false positive rate or performance guarantees, (2) they do not support variable-length keys and query ranges, and (3) they do not allow dynamic updates. We introduce Diva, the first range filter to address all the above challenges simultaneously. Diva learns the dataset's distribution by sampling keys and storing them in a cache-efficient trie. It compresses keys in-between samples by removing their longest common prefix and truncating their suffixes while leaving enough bits in the middle (i.e., an infix) to differentiate the keys in sorted order. It stores infixes in constant-time dynamic data blocks, which it splits to handle insertions and expansions. It processes a range query by traversing the trie and checking for the inclusion of infixes in the target query range. We mathematically prove that Diva provides the best possible trade-off between memory and false positive rate on many common real-world data distributions. We extend these benefits to a wider range of real-world workloads by introducing Diva++, an enhanced Diva variant. Diva++ saves memory by removing redundancies among infixes using order-preserving entropy encoding. It then removes any remaining identical infixes and uses the freed space to store more bits of the original keys within compact binary tries. We compare Diva and Diva++ to all prior range filters, and show that they achieve a false positive rate on par with the state of the art on real-world datasets while supporting dynamicity and variable-length queries and keys.

Authors: Hong Li

We give an approximation algorithm for the rural postman problem with approximation ratio strictly smaller than $3/2$. We obtain this result by adapting to the rural postman problem the technique of sampling from maximum entropy distributions for the metric traveling salesman problem of Karlin, Klein, and Oveis Gharan. We also observe that, for every fixed $\varepsilon>0$, any $α$-approximation algorithm for the metric traveling salesman problem yields an $(α+\varepsilon)$-approximation algorithm for the rural postman problem; this implication is already implicit in the treatment of edges that must be traversed in the work of Lampis on the inapproximability of the traveling salesman problem.

Authors: Karl Bringmann, Ariel Kulik, Karol Węgrzycki

We revisit the $d$-dimensional Vector Knapsack problem ($d$-Knapsack): Given a $d$-dimensional capacity vector and a set of items, each with a $d$-dimensional weight vector and a profit, the goal is to select a set of items that maximizes the total profit without exceeding the capacity in any dimension. For any $d\ge2$, the best known approximation scheme for $d$-Knapsack runs in time $O(n^{\lceil d/\varepsilon\rceil-d})$ [Caprara, Kellerer, Pferschy, Pisinger '00]. We improve this running time to $\widetilde O_{d,\varepsilon,ρ}(n^{\lceil\frac{d-1}{2\varepsilon}-\frac12+ρ\rceil}+n^d)$ for any $\varepsilon\in(0,1)$ and every parameter $ρ\in(0,1)$. We achieve this speedup by designing the first meet-in-the-middle algorithm for $d$-Knapsack. This requires replacing the LP solver used in prior algorithms by a highly efficient dynamic programming algorithm to generate representative solutions, building on an LP-based structural argument. This is the first improvement in over 25 years, and the first result that improves the exponent by a constant factor. We complement this by a fine-grained lower bound based on $k$-SUM showing that 2-Knapsack requires time $n^{\lceil\frac1{2\varepsilon}-\frac12 \rceil-o(1)}$. This establishes the optimal exponent of 2-Knapsack as $\frac1{2\varepsilon}\pm O(1)$, which is precise up to an additive $O(1)$. To the best of our knowledge, this is the first result that determines the optimal exponent more precisely than up to a factor $O(1)$, for any problem that admits a PTAS but no EPTAS. For the special case of 2-Knapsack we further attain a $(1-\varepsilon-δ)$-approximation in time $\widetilde O_{δ,\varepsilon}(n^{\lceil\frac1{2\varepsilon}-\frac12\rceil})$. This nearly matches our lower bound, as for a slightly better approximation ratio a slightly better running time is impossible -- so our algorithm is bicriteria-optimal.

Authors: Xifan Yu

In this work, we present the first analysis of low degree polynomial threshold functions for the natural hypothesis testing problem of detecting the noisy random lift of a base $d$-regular graph from a uniformly random $d$-regular graph. Along the way, we obtain a new result for the distribution of short cycle counts in noisy random lift up to logarithmic lengths, which generalizes results by McKay, Wormald, and Wysocka and by Johnson in the case of random regular graphs, and the result by Fortin and Rudinsky in the case of random lift.

Authors: Yuansi Chen, Yunbum Kook

We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Our first result gives a general total-variation mixing bound under strong self-concordance, $\barν$-symmetry, and mixed-trace regularity on the local metric. The key idea is to control the Metropolis--Hastings acceptance probability on a high-probability region rather than at every point. Applying this framework to the Lee--Sidford, Lewis-weight, and John metrics yields an $\widetilde O(d^2)$ mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an $\widetilde O(d^4)$ mixing bound for sampling from truncated PSD cones. Our second result establishes stronger $χ^2$-divergence guarantees and pointwise acceptance control using a new fourth-order bootstrap condition. For a suitably scaled Lee--Sidford metric, this yields an $\widetilde O(d^2)$ mixing bound in $χ^2$-divergence, improving on the previous $\widetilde O(d^{9/4})$ bound.

Authors: Yang Hu, William Kuszmaul, Jingxun Liang, Stefan Walzer, Huacheng Yu, Renfei Zhou

First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectured that, at load factor $1 - ε$, the hash table achieves $O(ε^{-1})$ expected insertion time. But even proving a bound of the form $f(ε^{-1})$ for any function $f$ has remained open. In this paper, we prove that the expected insertion time is $ε^{-(1 + o(1))}$. This settles the complexity of the data structure up to sub-polynomial factors in $ε^{-1}$.

The recent paper \cite{chatterjee2026bipartite} showed that deciding whether a bipartite graph has a perfect matching can be reduced to deciding whether a determinant, whose value may be assigned to any sufficiently large field $\mathbb{F}$, equals to zero. In the second part of their work, \cite{chatterjee2026bipartite} also generalized the algebraic method and proposed an $\mathsf{NC}$ algorithm that computes the maximum \emph{weighted} perfect matching of bipartite graphs. However, the method they used relies on the positivity of non-zero sum of squares and does not generalize to finite fields. In this paper we further leverage their ideas and show that the algebraic method works in finite fields as well, therefore maximum weighted perfect bipartite matching is in $\text{Mod}_p \mathsf{L}$.

In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coordinate marginals decay geometrically with their rank. This additional structure removes the dependence on the maximum set size in random-containment estimates. We prove width-free hitting and weighted-concentration theorems for ranked-spread set systems, together with an elementary kernel-extraction theorem showing that ranked spreadness arises naturally in arbitrary distributions on small sets. Our main application is to the simulation of nonadaptive property testers by sample-based testers. If a one-sided tester has average query complexity $d$ and rejects every far input with probability at least $\delta$, then, for every integer $c>d/\delta$, it admits a one-sided sample-based simulation with expected sample complexity $O_{d,\delta,|\Sigma|}\bigl(n^{1-1/c}\bigr)$. More generally, if positive inputs are rejected with probability at most $\gamma$ and far inputs with probability at least $\delta>\gamma$,the same conclusion holds for every $c>d/(\delta-\gamma)$. In particular, for constant-query nonadaptive testers we obtain an exponent $1-\Theta(1/q)$, matching, up to the dependence on the rejection gap, the exponent conjectured by Fischer, Lachish, and Vasudev.

It is a major challenge in quantum fault-tolerance to obtain low-overhead protocols for performing non-Clifford gates. In this vein, we construct quantum codes with low-weight stabilizers that support transversal (i.e. low-depth) implementations of the non-Clifford $C^{r-1}Z$ gate, for every constant $r\geq 3$. In particular, we obtain length-$n$ quantum LDPC codes (with constant-weight stabilizers) of polynomial distance $d\geq n^{(1-\epsilon)/r}$ supporting transversal $C^{r-1}Z$ gates on a close-to-linear number $k\geq n^{1-\epsilon}$ of disjoint tuples of logical qubits, for arbitrarily small $\epsilon>0$. Our construction is the first with constant-weight stabilizers that obtains $dk\gg n$, and as a consequence achieves arbitrarily small magic state overhead exponent $\gamma=\log(n/k)/\log(d)>0$. Comparable prior constructions instead required at least polylogarithmic stabilizer weight. We also show how to obtain linearly many $k=\Omega(n)$ logical $C^{r-1}Z$ gates, though with stabilizer weight and physical circuit depth $n^\epsilon$. We show that our transversal gates also support addressing (i.e. targeting) of specific logical qubits. To obtain our codes, we develop a general transformation based on cup products that maps classical codes satisfying a multiplication property to quantum codes with transversal $C^{r-1}Z$. We apply this transformation to a new family of classical Tanner codes that we construct from punctured tensor products of algebraic codes.

Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ \Theta(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Gr\"unbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $\Omega(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.

We prove exponential lower bounds for $k$-DNF resolution on random $3$-CNF formulas throughout the range $k=O(\sqrt{\log n})$ at every constant clause density above the elementary first-moment bound for unsatisfiability. For random $3$-CNFs this improves Alekhnovich's range $k=O(\sqrt{\log n/\log\log n})$, and matches the $O(\sqrt{\log n})$ range obtained by Sofronova and Sokolov for random CNFs of sufficiently large constant width. We also obtain higher-density tradeoffs. In particular, random $3$-CNFs with $n\log^h n$ clauses are exponentially hard for $k=O(\sqrt{\log n/\log\log n})$ for every fixed $h>0$, while for every fixed $K$ the same conclusion holds simultaneously for all $1\le k\le K$ with $n^{1+\varepsilon}$ clauses whenever $\varepsilon<1/(4K^2+2)$.

In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a substring. Its best known approximation ratio is $2.466$, whereas the currently strongest upper bound on the approximation guarantee of the maximum-overlap greedy algorithm is $3.396$ (Englert, Matsakis, and Vesel{\'y}, 2023), though it is conjectured to be 2. We improve both approximation guarantees: SCS admits a $\frac{7}{3}$-approximation and the approximation guarantee of the greedy algorithm is at most $3$. The main technical ingredient of our proof is a certain inequality for optimum cycle covers of an overlap graph associated with the input strings. Every previous improvement of greedy's worst-case guarantee and the two recent record guarantees for general SCS are driven by it. We improve this inequality by pushing it to its limit: for a particular coefficient of this inequality, we show a new upper bound and prove that it cannot be improved further.

Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial-method argument that controls collisions in sumsets of matching vectors.

We prove an exponential separation between zero-sided-error randomized and two-sided-error pseudodeterministic communication complexities of partial boolean functions. This qualitatively improves and simplifies the proof of the separation by Göös, Harms, Riazanov, Sofronova, Sokolov, and Yuan (STOC 2026), which had a two-sided-error randomized upper bound. Then, we generalize our technique to separate the communication complexity analogues of MA and NP^BPP.

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

Authors: Martin Kassabov, J. M. Landsberg, Victor Souza, Philip Speegle

This paper addresses centroids, which are fundamental invariants of tensors. Our main results are as follows: (i) The construction of explicit tensors with very large centroids, whereas previously it had been conjectured that none such exist. (ii) An upper bound on the dimension of the centroid that is essentially attained by our examples. (iii) The development of a geometric technique to write down border rank decomposition of tensors using centroids and "extended centroids". (iv) The technique is applied to tensors of this paper to prove they are of minimal border rank. The technique is versatile and enables us to geometrically derive and improve upon previous ad hoc decompositions. (v) The construction of symmetric tensors with large centroids and proof that they are wild in the sense of Buczyńska-Buczyński. Our results also pave the way for new upper bounds on the exponent of matrix multiplication. The geometric technique also constructs new "better" tensors for Strassen's laser method from old, and we apply this to the tensors of Strassen and Schönhage to get better tensors in the sense that they give better upper bounds on the exponent than the original tensors.

Authors: Thomas Watson

We prove an exponential separation between zero-sided-error randomized and two-sided-error pseudodeterministic communication complexities of partial boolean functions. This qualitatively improves and simplifies the proof of the separation by Göös, Harms, Riazanov, Sofronova, Sokolov, and Yuan (STOC 2026), which had a two-sided-error randomized upper bound. Then, we generalize our technique to separate the communication complexity analogues of MA and NP^BPP.

Authors: Benedikt Kolbe, Tim Mayr

We present results on the approximate computation of stable invariants for filtrations of finite metric spaces in the context of persistent homology. We establish novel approximation algorithms in the setting of $n$-point metric spaces where the growth of the doubling dimension is in $o(\log n)$ and the diameter is bounded. In the $1$-parameter case, by revisiting known techniques (greedy permutations) in a new way, we derive the first linear-time algorithms for the problem of computing additive $\varepsilon$-approximations of any stable barcode. By deriving bounds on the convergence rate and the approximation quality of uniform samples, we extend the approach to selected multiparameter filtrations. We show that for normalized measure bifiltrations, including the multicover and subdivision-Rips bifiltration, any stable invariant can be probabilistically approximated in time constant in $n$. The constants in the running times of our algorithms depend on the doubling dimension, the diameter and the success probability. We further study the problem through the lens of fine-grained complexity and show that computing the rank of a matrix reduces to that of approximating the barcode of the Vietoris--Rips or Čech filtration. We present two variants of the reduction, one for sufficiently good additive approximations and the other for any constant factor multiplicative approximations.

Authors: Ondřej Draganov, Herbert Edelsbrunner, Sophie Rosenmeier, Morteza Saghafian

Motivated by the recent introduction of chromatic persistent homology, we generalize the Euclidean minimum spanning tree (EMST) for $n$ points in $\mathbb{R}^2$ to the lunar EMST for the case in which the points come in $s+1$ colors. Calling the intersection of $s+1$ disks of radius $r$ centered at points with pairwise different colors a \emph{lune}, the generalized EMST reflects the history of the union of lunes as $r$ goes from $0$ to $\infty$, and its \emph{cost} is twice the difference between the radii when the arcs and nodes of the tree are formed. If the points are chosen uniformly at random in $[0,1]^2$ and colored randomly, the expected cost converges to some constant (that depends on $s$) times $\sqrt{n}$, as $n$ goes to infinity. The main contribution of this paper is a proof that this constant exists, however similar to the case of the classic EMST, its precise value remains elusive.

Authors: Eunku Park

We study nearest and farthest Voronoi diagrams of lines in $\mathbb{R}^3$ under the Euclidean metric when all $n$ lines belong to one ruling of a smooth doubly ruled real quadric. For arbitrary line sites, the combinatorial complexity of the nearest Voronoi diagram is known only to lie between $Ω(n^2)$ and $O(n^{3+\varepsilon})$. Under general-position assumptions, we prove that both diagrams in the ruling class have at most $4n(n-3)$ vertices and $O(n^2)$ total combinatorial complexity. Conversely, for every $n \ge 4$, one ruling of a fixed non-rotational one-sheeted hyperboloid contains a general-position set of $n$ lines with at least $(n-2)(n-3)/2$ distinct regular nearest vertices, where regular means that exactly four lines support the vertex and their three defining bisectors meet transversely. Thus the worst-case complexity of the nearest Voronoi diagram in this class is $Θ(n^2)$, while the farthest diagram has $Θ(n^2)$ complexity for every general-position input, since it has exactly $n(n-1)$ three-dimensional cells. Under the Plücker embedding, the ruling is a conic, and the condition for a line to be tangent to a Euclidean sphere restricts to a binary quartic. At a regular vertex, the four supporting parameters exhaust its roots, and sign alternation forces two arcs of the parameter circle to be site-free. This leaves only $n(n-3)/2$ possible cyclic support types, while Bézout's theorem bounds the number of centers for each type by eight. The same reduction yields an exact $O(n^2)$-time algorithm that, after cyclically sorting the site parameters, enumerates all finite nearest and farthest vertices as constant-degree real univariate representations.

Authors: Joshua A. Grochow, Gülce Kardeş, Michael Levet

In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Isomorphism: namely, we show that every family of depth-$2$ Boolean circuits deciding Group Isomorphism requires quasipolynomial-size. We complement this with upper bounds of uniform depth-$2\frac{1}{2}$ circuits of quasipolynomial-size. A sequence of previous results from 1970-2025 progressively reduced the circuit depth from polynomial to $3\frac{1}{2}$; all of these results relied on the generator-enumerator strategy and, in fact, applied more generally to quasigroups. In contrast, our depth-$2\frac{1}{2}$ construction follows a fundamentally different strategy that exploits structure more specific to groups. We guess a composition series for each group, together with generators for its terms and the isomorphism types of its composition factors. We then inductively verify that the corresponding extensions at each level of the two composition series are compatible. A central part in this approach brings to bear the extensive work on the Short Presentation Conjecture, in tandem with the algorithmic theory of group extensions and cohomology.

Authors: Julian Teusch, Jörg Philipp Müller, Monika Sester

Operational requirements developed with the City of Braunschweig frame municipal micromobility planning under geofenced exclusions, mandatory retained sites, spacing rules, and area-level caps. Each policy edit requires a new feasible plan; full-set greedy takes tens of seconds per alternative at city scale. We present CLIPPER (Constraint-exact Low-latency Iterative Planning with Pooled Evaluation and Replay). It forms bounded candidate pools but recomputes exact current gains and checks every active constraint before selection. Coverage from each candidate alone sets the initial order. Offline full-set scans measure gains omitted by the pool; online, a conservative bound triggers expansion or audit. CLIPPER-F gives each proposal group the same number of candidate slots. Across Braunschweig, Munich, and Berlin, its mean coverage over complete chains stays within 0.245 percentage points of full-set greedy under the same policy, with 13.6--28.9 times lower mean rollout time. CLIPPER-A instead distributes one shared candidate budget across the groups. Under its coverage-prioritized policy, it uses 9--15% of full-set greedy's rollout time under the same policy, with mean gaps of 1.82 percentage points in Braunschweig, 0.12 in Munich, and 0.27 in Berlin. Together, CLIPPER enables rapid, replayable comparison of recorded city-scale planning states while enforcing every encoded model constraint.

Authors: Frederic Koehler, Youngtak Sohn

We establish a sharp phase transition for fitting random vectors by an ellipsoid. The random vectors have independent subgaussian coordinates with mean zero, variance one, and a common fourth moment, and the number of vectors is proportional to the square of the dimension. We identify an explicit satisfiability threshold such that, with high probability, a positive definite ellipsoid passes through every data point below the threshold, whereas no positive semidefinite fit exists above it. We also determine the optimal squared fitting error throughout the unsatisfiable regime. In particular, the threshold depends on the coordinate distributions only through their common fourth moment, revealing a fourth moment universality phenomenon. For standard Gaussian data the threshold is $1/4$, resolving the ellipsoid fitting conjecture.

Authors: Francesco Paolo Nerini, Francesco Bonchi, Arijit Khan, André Panisson

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

Authors: Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, Michael Kaufmann

A track layout of a graph is a partition of its vertices into linearly ordered independent sets, called tracks, such that no two edges between the same pair of tracks cross. Given a graph, the goal in this context is to determine its track number, that is, the minimum number of tracks required for the graph to admit a track layout. In this work, we present upper bounds on the track number of graphs admitting a product structure. Our main contribution is an algorithm that computes a track layout with at most $(2h+1) \cdot r \cdot tn(H)$ tracks for every subgraph of the strong product $P^h \boxtimes K_r \boxtimes H$, where $P^h$ is the $h$-th power of a path $P$, $K_r$ is the complete graph on $r$ vertices, and $H$ is a graph with track number $tn(H)$. Combined with existing product-structure results from the literature, this algorithm yields upper bounds on the track number of several graph classes. For planar graphs, the obtained bound matches the current best-known upper bound of $225$. For $1$-planar and optimal $2$-planar graphs, our algorithm yields track layouts with at most $375$ tracks, while for genus-$k$, $k$-planar, $k$-framed, $k$-map, and $k$-string graphs it provides track layouts with a number of tracks that depends solely on $k$, thus establishing new upper bounds on the track number for these graph classes. The algorithm runs in linear time for planar graphs and, more generally, in $O(n + h \cdot r \cdot t + f_t(H))$ time whenever a corresponding product-structure decomposition of the input $n$-vertex graph is provided as part of the input, where $t=tn(H)$ and $f_t(H)$ is the time needed to compute a $t$-track layout of $H$. Furthermore, our algorithm only uses elementary linked-list data structures.

Authors: Luyao Fan, Jiayang Zou, Jiayang Gao, Jia Wang

We study the zero-error randomized query complexity of finding all minimal elements in an unknown $n$-element poset of width at most $w$. Previous work of Daskalakis, Karp, Mossel, Riesenfeld, and Verbin established a randomized upper bound with leading term $\frac{w+1}{2}n$, while the corresponding lower bound left a multiplicative gap in the leading constant that approaches a factor of 2 as $w$ grows. We prove the finite lower bound \( R^{\mathrm{LV}}_{n,w}\ge \frac{w+1}{2}n-\frac{w(w+3)}4 +w\left(1-\frac1w\right)^n +\frac{w(w-1)}4\left(1-\frac2w\right)^n. \) Consequently, for every fixed $w$, \( R^{\mathrm{LV}}_{n,w} = \left(\frac{w+1}{2}+o(1)\right)n. \) Thus the known randomized upper bound has the correct asymptotic leading constant for every fixed width. The argument is based on a pairwise accounting of incomparable queries under a random-chain hard distribution, using a component-flip involution and a unique ownership property for incomparable comparisons. Generative AI was used in the preparation of this manuscript.

Authors: Matic Požar

Recent work by Haeupler, Hladík, Rozhon, Tarjan, and Tětek on the instance optimality of shortest-path algorithms established several results concerning Dijkstra's algorithm and bidirectional Dijkstra's algorithm in weighted and unweighted graphs. Motivated by these results, we revisit the question of instance optimality for shortest $st$-path algorithms in the standard query model. We identify several issues in the analysis of the instance optimality of both unidirectional and bidirectional Dijkstra's algorithms and provide corresponding counterexamples. We then propose a minimal simple modification of the bidirectional Dijkstra algorithm and prove that the resulting variant is instance optimal in the weighted setting. Furthermore, we revisit the unweighted case, provide a simplified proof of the lower bound showing that no algorithm can achieve instance optimality up to a factor better than $O(Δ)$, where $Δ$ denotes the maximum degree of the graph, and discuss the implications of this result for approximation algorithms. Finally, we make progress on the open problem of instance optimality in simple graphs. We show that if the problem instance satisfies $n\ge m/16$, where $n$ is the number of nodes and $m$ is the number of edges queried by our algorithm, then it is optimal up to a constant factor. Additionally, we show instance optimality for a broad class of instances, in particular when the largest degree in the graph is at most the square root of the number of explored edges, our algorithm exhibits optimality up to a constant factor.

Authors: Omer Gurevich, Maor Matityahu, Tal Mor, Aryeh Lev Zabokritskiy

We revisit a degree-only arc Hamiltonian for fixed-fleet, homogeneous, uncapacitated vehicle routing. Because its local penalties define only a cycle cover, ground states may contain customer cycles disconnected from the depot. We construct a polynomial-size quadratic unconstrained binary optimization (QUBO) repair using capped single-commodity flow and prove that every ground-state routing is connected and cost-optimal under explicit penalty assumptions. For $N-1$ customers and $K$ nonempty routes, the unreduced encoding uses exactly $|E|(1+\lceil\log_2(N-K+1)\rceil)$ logical problem qubits. A reversible compute--phase--uncompute realization evaluates the flow penalties in $O(N^2\log N+N\log^2N)$ logical gates on a complete graph with $O(\log N)$ reusable workspace and no product register. On complete loopless graphs, a depot-delimited single-sequence position encoding uses fewer problem qubits and fewer written terms when the flow-word length grows. Conversely, the flow model achieves a smaller structured logical-gate upper bound under a common reversible accounting model. Exact audits of the Hamiltonian and circuit implementation, combined with a $1{,}200$-matrix classical benchmark, verify the formulation and quantify the connectivity gap. Finally, a 32,000-shot Amazon Braket task on IQM Emerald characterizes depth-one termwise Ising circuits on a diagnostic $N = 4,\, K = 1$ counterexample instance. In the degree-only circuit, $78.05\%$ of selected $p=1$ shots realize the invalid disconnected ground state; the reduced 14-qubit flow-augmented circuit yields no fully feasible sample. These device results characterize mapped Hamiltonians and compilation rather than an asymptotic routing solution advantage.

Authors: Xiaoyu Chen, Eric Vigoda, Xiongxin Yang

The permanent of an $n\times n$ $0/1$ matrix $A$ equals the number of perfect matchings in the bipartite graph with edges defined by $A$. Jerrum, Sinclair, and Vigoda (2004) presented an FPRAS for approximating the permanent of any nonnegative matrix using a novel simulated-annealing algorithm. The running time was improved by Bezáková, Štefankovič, Vazirani, and Vigoda (2008) to $O(n^7\log^4 n)$ for $0/1$ matrices, for any fixed approximation and success parameters. We present the first asymptotic improvement over this running time bound, obtaining an $O(n^6\log^5 n)$-time algorithm. As in the previous works, our algorithm extends to arbitrary nonnegative matrices. The analysis of Bezáková et al. yields an $O(n^4)$ relaxation time bound for the JSV Markov chain on perfect and near-perfect matchings with ideal hole weights, under which each hole pattern (the unmatched vertices, if any) is equally likely in the stationary distribution. We introduce a restricted Poincaré inequality for the partition into hole patterns and prove an $O(n^3)$ bound on the corresponding restricted relaxation time. Our proof uses a coupled multicommodity flow argument inspired by a recent transport-flow argument of Chen et al.~(2025) for the Jerrum-Sinclair chain on all matchings.

Authors: Zhao Song, Lichen Zhang

Randomized sketch-and-solve algorithms accelerate overconstrained $\ell_2$ regression by replacing the input with a smaller problem. Standard subspace embeddings guarantee that the cost of the regression is nearly preserved, but coordinate-wise accuracy of the solution is more delicate: we want the solution vector itself to be close to the optimal solution in $\ell_\infty$ norm. In particular, we want to find a vector $x'\in \mathbb{R}^d$ such that $\|x'-x^*\|_\infty\leq \fracε{\sqrt d}\cdot \|Ax^\star-b\|_2\cdot \|A^\dagger\|_{\rm op}$. Price, Song and Woodruff initiated the study of this problem and showed that the subsampled randomized Hadamard transform (SRHT) with $O(ε^{-2} d^{1+Θ(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee. A subsequent work of Song, Ye, Yin and Zhang claimed to improve the row count to $O(ε^{-2}d\log^3 n)$. Unfortunately, their proof relies on an independence assumption that does not hold in general, and we exhibit an explicit instance on which it fails. To achieve a truly nearly-linear-in-$d$ row count, we introduce a new fast, dense randomized transform, which combines a randomized Hadamard flattening, a random permutation, and balanced, disjoint Gaussian pooling. Conditioned on the Hadamard-and-permutation stage, the sketched problem becomes an exact Gaussian regression in which the noise is independent of the entire sketched design; this conditional independence is exactly what the earlier argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(ε^{-2}d\log d)$ rows, uses one Hadamard pass with a padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$, and is efficient to apply: the sketched pair $(SA, Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.

Authors: Aaron Li, Yifan Li, Drew DeHaas, Giulia Guidi

Updating a graph by inserting or replacing nodes while preserving semantics and reusing existing structure is a recurring computational problem. In population genetics, this problem arises in the genotype representation graph (GRG), a directed acyclic graph that losslessly encodes phased genetic variation across hundreds of thousands of samples by sharing subgraph structure for individual mutations. In a GRG, each mutation's carrier set is implicitly encoded as the set of leaf nodes reachable from the node it is assigned to. Updating a mutation is therefore a structural editing problem, and current approaches remap mutations individually. This paper introduces a batched mutation-remapping algorithm that replaces independent reuse-aware traversals with a single shared reverse-topological pass, identifying reuse candidates for an entire batch at once. The pass propagates compact bit-parallel per-mutation state and uses an adaptive sparse/dense carrier set representation spanning rare-to-common variant densities. Batching is the memory-scalable complement to split-based parallelism, which instead replicates graph and traversal state per worker. Our remapping is evaluated on a controlled update workload and on end-to-end allele polarization, a bulk carrier set update that is common in population genetic analysis. Our approach is up to 10.5$\times$ faster than independent remapping while preserving exact carrier-set semantics.

Authors: Somya Nigam, Johan Springael, Kenneth Sörensen

The problem of finding a fair consensus ranking is an active research topic in the domain of fair rank aggregation and has been well studied; however, existing studies predominantly consider both the input rankings and the output ranking to be permutations where elements are always strictly ordered. In practice, however, a ranking with ties is far more common. This study bridges this gap by presenting a post-processing approach to determine the closest fair consensus ranking when an unfair tie-aware consensus ranking is provided. It proposes an exact algorithm and a fast heuristic to achieve this.

Authors: Francisco J. Soulignac

The time-dependent traveling salesman problem with time windows (TDTSPTW) generalizes the well-known traveling salesman problem with time windows by accounting the effects of congestion on travel times. In this paper, we develop an exact framework for the TDTSPTW with a makespan objective that extends the range of instances solvable to optimality under loose time windows while remaining effective across all levels of time-window tightness. Our framework relies on a dynamic-programming labeling algorithm and combines column generation, ng-memory augmentation, and exact search, using completion bounds for state-space sparsification, variable fixing, and exact search pruning. Embedded within a branch-and-price method, the framework solves all instances with up to 45 customers in a benchmark comprising more than 10,000 instances, including all instances without time windows with up to 50 customers.