Theory of Computing Report

Authors: Víctor Blanco, Victor Magron, Miguel Martínez-Antón

This manuscript explores novel complexity results for the feasibility problem over $p$-order cones, extending the foundational work of Porkolab and Khachiyan. By leveraging the intrinsic structure of $p$-order cones, we derive refined complexity bounds that surpass those obtained via standard semidefinite programming reformulations. Our analysis not only improves theoretical bounds but also provides practical insights into the computational efficiency of solving such problems. In addition to establishing complexity results, we derive explicit bounds for solutions when the feasibility problem admits one. For infeasible instances, we analyze their discrepancy quantifying the degree of infeasibility. Finally, we examine specific cases of interest, highlighting scenarios where the geometry of $p$-order cones or problem structure yields further computational simplifications. These findings contribute to both the theoretical understanding and practical tractability of optimization problems involving $p$-order cones.

Authors: Annika Oehri, Philipp Herholz, Olga Sorkine-Hornung

We propose a modification of the As-Rigid-As-Possible (ARAP) mesh deformation energy with higher order smoothness, which overcomes a prominent limitation of the original ARAP formulation: spikes and lack of continuity at the manipulation handles. Our method avoids spikes even when using single-point positional constraints. Since no explicit rotations have to be specified, the user interaction can be realized through a simple click-and-drag interface, where points on the mesh can be selected and moved around while the rest of the mesh surface automatically deforms accordingly. Our method preserves the benefits of ARAP deformations: it is easy to implement and thus useful for practical applications, while its efficiency makes it usable in real-time, interactive scenarios on detailed models.

Authors: Thomas C. Hull

The field of rigid origami concerns the folding of stiff, inelastic plates of material along crease lines that act like hinges and form a straight-line planar graph, called the crease pattern of the origami. Crease pattern vertices in the interior of the folded material and that are adjacent to four crease lines, i.e. degree-4 vertices, have a single degree of freedom and can be chained together to make flexible polyhedral surfaces. Degree-4 vertices that can fold to a completely flat state have folding kinematics that are very well-understood, and thus they have been used in many engineering and physics applications. However, degree-4 vertices that are not flat-foldable or not folded from flat paper so that the vertex forms either an elliptic or hyperbolic cone, have folding angles at the creases that follow more complicated kinematic equations. In this work we present a new duality between general degree-4 rigid origami vertices, where dual vertices come in elliptic-hyperbolic pairs that have essentially equivalent kinematics. This reveals a mathematical structure in the space of degree-4 rigid origami vertices that can be leveraged in applications, for example in the construction of flexible 3D structures that possess metamaterial properties.

Authors: Artur Czumaj, Gopinath Mishra, Anish Mukherjee

We initiate the study of graph algorithms in the streaming setting on massive distributed and parallel systems inspired by practical data processing systems. The objective is to design algorithms that can efficiently process evolving graphs via large batches of edge insertions and deletions using as little memory as possible. We focus on the nowadays canonical model for the study of theoretical algorithms for massive networks, the Massively Parallel Computation (MPC) model. We design MPC algorithms that efficiently process evolving graphs: in a constant number of rounds they can handle large batches of edge updates for problems such as connectivity, minimum spanning forest, and approximate matching while adhering to the most restrictive memory regime, in which the local memory per machine is strongly sublinear in the number of vertices and the total memory is sublinear in the graph size. These results improve upon earlier works in this area which rely on using larger total space, proportional to the size of the processed graph. Our work demonstrates that parallel algorithms can process dynamically changing graphs with asymptotically optimal utilization of MPC resources: parallel time, local memory, and total memory, while processing large batches of edge updates.

Authors: Johannes Rauch, Dieter Rautenbach

We provide theoretical insights around the cutwidth of a graph and the One-Sided Crossing Minimization (OSCM) problem. OSCM was posed in the Parameterized Algorithms and Computational Experiments Challenge 2024, where the cutwidth of the input graph was the parameter in the parameterized track. We prove an asymptotically sharp upper bound on the size of a graph in terms of its order and cutwidth. As the number of so-called unsuited pairs is one of the factors that determine the difficulty of an OSCM instance, we provide a sharp upper bound on them in terms of the order $n$ and the cutwidth of the input graph. If the cutwidth is bounded by a constant, this implies an $\mathcal{O}(2^n)$-time algorithm, while the trivial algorithm has a running time of $\mathcal{O}(2^{n^2})$. At last, we prove structural properties of the so-called crossing numbers in an OSCM instance.

Authors: Thomas Baruchel

We present a new algorithm for iterating over all permutations of a sequence. The algorithm leverages elementary operations on recursive lists. Within each recursive call, only two operations are required to generate all permutations (albeit in an unusual order): swapping the first two elements of the list or moving the last element to the front. As a result, no new nodes are allocated during the computation. Instead, all elements are rearranged within the original nodes of the singly linked list throughout the process. A proof of concept written in the Lisp programming language is proposed and discussed.

Authors: Felix I. Stamm, Mehdi Naima, Michael T. Schaub

In this paper, we extend the classical Color Refinement algorithm for static networks to temporal (undirected and directed) networks. This enables us to design an algorithm to sample synthetic networks that preserves the $d$-hop neighborhood structure of a given temporal network. The higher $d$ is chosen, the better the temporal neighborhood structure of the original network is preserved. Specifically, we provide efficient algorithms that preserve time-respecting ("causal") paths in the networks up to length $d$, and scale to real-world network sizes. We validate our approach theoretically (for Degree and Katz centrality) and experimentally (for edge persistence, causal triangles, and burstiness). An experimental comparison shows that our method retains these key temporal characteristics more effectively than existing randomization methods.

Authors: Gautam Chandrasekaran, Vasilis Kontonis, Konstantinos Stavropoulos, Kevin Tian

We study the problem of PAC learning $\gamma$-margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the Perspectron, that has sample complexity $\widetilde{O}((\epsilon\gamma)^{-2})$ and achieves classification error at most $\eta+\epsilon$ where $\eta$ is the Massart noise rate. Prior works [DGT19,CKMY20] came with worse sample complexity guarantees (in both $\epsilon$ and $\gamma$) or could only handle random classification noise [DDK+23,KIT+23] -- a much milder noise assumption. We also show that our results extend to the more challenging setting of learning generalized linear models with a known link function under Massart noise, achieving a similar sample complexity to the halfspace case. This significantly improves upon the prior state-of-the-art in this setting due to [CKMY20], who introduced this model.

Seven Assistant Professor positions in Computer Science, including two Samuel Eilenberg Assistant Professor positions with reduced teaching and increased salary, and one position dedicated for researchers specializing in Distributed Systems or Programming Languages. Starting on 1st October 2025 or 1st February 2026. Join a faculty with 7 ERC grants running and stunning performance in ACM ICPC!

Website: https://jobs.uw.edu.pl/en-gb/offer/WMIM_2025/field/ADIUNKT/
Email: f.murlak@uw.edu.pl

By shacharlovett

We prove a time hierarchy theorem for the promise-BPTIME. This is considered to be a folklore problem and was thought to follow from the existence of complete problems or through direct diagonalization. We observe that neither argument carries through in some immediate way in the promise version. However, the hierarchy theorem can be proved by the standard delayed diagonalization for the nondeterministic time hierarchy theorem [Coo72, SFM78, Zak83], or, as it was observed by Rahul Santhanam, from the established BPTIME hierarchies with advice [Bar02, FS04, GST11, FST05, Per05, vMP07, San25].

I made up a quiz about the American Presidents here.  

It has 40 questions. In the modern electronic age you can probably look up most or even all of the answers. So what to do about that?

1) The quiz is not for money or credits or anything, so if you ``cheat'' you only cheat yourself.

2) Be honest with yourself and take it in three hours.

3) USE the web and see how long it takes you to finish it. You can make up some way to measure how well you did by combining how many you got right with how long it took.

4) The answers, that I will post later in the week or next week, have lots of other information of interest. So  whichever of 1,2,3 you do or something else, read the solutions (even those you got right) and be enlightened. 

It is actually titled Prez Trivia Quiz. This might not be accurate.

What is trivia? I think it is knowledge that does not connect to other knowledge and hence is not important. Some of my questions are trivia, and some are not. I give examples of each:

What is the most common middle initial for a president? This is clearly trivia. I don't know the answer and its no on the quiz, but I might put it on the next time I do this, four years from now.

Five presidents ran again for president four or more years after leaving office. Name them and how thy did. This is not trivia (what word means the opposite of trivia? See later). Since Trump ran four years later and won it is of interest to see what circumstances in the past  lead to a former prez (a) running again, and (b) winning. 

If you are so inclined you can, for each question on the quiz, say if its trivia or not. YMMV.

I googled "opposite of trivia" and got this informative website (I am not being sarcastic) here.

By gasarch

Authors: Jarosław Błasiok, Linus Meierhöfer

We consider a problem of approximating the size of the largest clique in a graph, with a monotone circuit. Concretely, we focus on distinguishing a random Erd\H{o}s-Renyi graph $\mathcal{G}_{n,p}$, with $p=n^{-\frac{2}{\alpha-1}}$ chosen st. with high probability it does not even have an $\alpha$-clique, from a random clique on $\beta$ vertices (where $\alpha \leq \beta$). Using the approximation method of Razborov, Alon and Boppana showed in 1987 that as long as $\sqrt{\alpha} \beta < n^{1-\delta}/\log n$, this problem requires a monotone circuit of size $n^{\Omega(\delta\sqrt{\alpha})}$, implying a lower bound of $2^{\tilde\Omega(n^{1/3})}$ for the exact version of the problem when $k\approx n^{2/3}$. Recently Cavalar, Kumar, and Rossman improved their result by showing the tight lower bound $n^{\Omega(k)}$, in a limited range $k \leq n^{1/3}$, implying a comparable $2^{\tilde{\Omega}(n^{1/3})}$ lower bound. We combine the ideas of Cavalar, Kumar and Rossman with the recent breakthrough results on the sunflower conjecture by Alweiss, Lovett, Wu and Zhang to show that as long as $\alpha \beta < n^{1-\delta}/\log n$, any monotone circuit rejecting $\mathcal{G}_{n,p}$ while accepting a $\beta$-clique needs to have size at least $n^{\Omega(\delta^2 \alpha)}$; this implies a stronger $2^{\tilde{\Omega}(\sqrt{n})}$ lower bound for the unrestricted version of the problem. We complement this result with a construction of an explicit monotone circuit of size $O(n^{\delta^2 \alpha/2})$ which rejects $\mathcal{G}_{n,p}$, and accepts any graph containing $\beta$-clique whenever $\beta > n^{1-\delta}$. Those two theorems explain the largest $\beta$-clique that can be distinguished from $\mathcal{G}_{n, 1/2}$: when $\beta > n / 2^{C \sqrt{\log n}}$, polynomial size circuit co do it, while for $\beta < n / 2^{\omega(\sqrt{\log n})}$ every circuit needs size $n^{\omega(1)}$.

Authors: Ilias Diakonikolas, Nikos Zarifis

We study the problem of PAC learning $\gamma$-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be $\widetilde{\Theta}(1/(\gamma^2 \epsilon))$. Prior computationally efficient algorithms for the problem incur sample complexity $\tilde{O}(1/(\gamma^4 \epsilon^3))$ and achieve 0-1 error of $\eta+\epsilon$, where $\eta<1/2$ is the upper bound on the noise rate. Recent work gave evidence of an information-computation tradeoff, suggesting that a quadratic dependence on $1/\epsilon$ is required for computationally efficient algorithms. Our main result is a computationally efficient learner with sample complexity $\widetilde{\Theta}(1/(\gamma^2 \epsilon^2))$, nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses.

Authors: Chi-Yeh Chen

Coflow represents a network abstraction that models communication patterns within data centers. The scheduling of coflows is a prevalent issue in large data center environments and is classified as an $\mathcal{NP}$-hard problem. This paper focuses on the scheduling of coflows in heterogeneous parallel networks, defined by architectures featuring multiple network cores operating concurrently. We introduce two pseudo-polynomial-time algorithms and two polynomial-time approximation algorithms to minimize the maximum completion time (makespan) in heterogeneous parallel networks. We propose a randomized algorithm that offers an expected approximation ratio of 1.5. Building upon this foundation, we provide a deterministic algorithm that utilizes derandomization techniques, which offers a performance guarantee of $1.5 + \frac{1}{2 \cdot LB}$, where $LB$ is the lower bound of the makespan for each instance. To address time complexity concerns, we implement an exponential partitioning of time intervals and present a randomized algorithm with an expected approximation ratio of $1.5 + \epsilon$ in polynomial time where $\epsilon>0$. Additionally, we develop a deterministic algorithm with a performance guarantee expressed as $\max\left\{1.5+\epsilon, 1.5+\frac{1}{2 \cdot LB}\right\}$ within polynomial time. These advancements markedly enhance the best-known approximation ratio of $2+\epsilon$.

Authors: Surbhi Goel, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

We pose a fundamental question in computational learning theory: can we efficiently test whether a training set satisfies the assumptions of a given noise model? This question has remained unaddressed despite decades of research on learning in the presence of noise. In this work, we show that this task is tractable and present the first efficient algorithm to test various noise assumptions on the training data. To model this question, we extend the recently proposed testable learning framework of Rubinfeld and Vasilyan (2023) and require a learner to run an associated test that satisfies the following two conditions: (1) whenever the test accepts, the learner outputs a classifier along with a certificate of optimality, and (2) the test must pass for any dataset drawn according to a specified modeling assumption on both the marginal distribution and the noise model. We then consider the problem of learning halfspaces over Gaussian marginals with Massart noise (where each label can be flipped with probability less than $1/2$ depending on the input features), and give a fully-polynomial time testable learning algorithm. We also show a separation between the classical setting of learning in the presence of structured noise and testable learning. In fact, for the simple case of random classification noise (where each label is flipped with fixed probability $\eta = 1/2$), we show that testable learning requires super-polynomial time while classical learning is trivial.

Authors: Syamantak Das, Andreas Wiese

We study the classical scheduling problem of minimizing the makespan of a set of unit size jobs with precedence constraints on parallel identical machines. Research on the problem dates back to the landmark paper by Graham from 1966 who showed that the simple List Scheduling algorithm is a $(2-\frac{1}{m})$-approximation. Interestingly, it is open whether the problem is NP-hard if $m=3$ which is one of the few remaining open problems in the seminal book by Garey and Johnson. Recently, quite some progress has been made for the setting that $m$ is a constant. In a break-through paper, Levey and Rothvoss presented a $(1+\epsilon)$-approximation with a running time of $n^{(\log n)^{O((m^{2}/\epsilon^{2})\log\log n)}}$[STOC 2016, SICOMP 2019] and this running time was improved to quasi-polynomial by Garg[ICALP 2018] and to even $n^{O_{m,\epsilon}(\log^{3}\log n)}$ by Li[SODA 2021]. These results use techniques like LP-hierarchies, conditioning on certain well-selected jobs, and abstractions like (partial) dyadic systems and virtually valid schedules. In this paper, we present a QPTAS for the problem which is arguably simpler than the previous algorithms. We just guess the positions of certain jobs in the optimal solution, recurse on a set of guessed subintervals, and fill in the remaining jobs with greedy routines. We believe that also our analysis is more accessible, in particular since we do not use (LP-)hierarchies or abstractions of the problem like the ones above, but we guess properties of the optimal solution directly.

I have another new arXiv preprint: “Computational geometry with probabilistically noisy primitive operations”, arXiv:2501.07707, with Mike Goodrich and his student Vinesh Sridhar. Many computational geometry algorithms are designed around the use of primitives, subroutines that access the coordinate data of the input and convert it into combinatorial information, with the assumption that all access to the input goes through these primitives. For instance, a key primitive often used for computing convex hulls (and central to my book on forbidden configurations) takes as input an ordered triple of points in the plane and determines whether they are ordered clockwise around the triangle they generate, counterclockwise, or collinear. The premise of the new preprint is that this primitive could randomly produce the wrong result, with some constant probability, independent of any past errors or successes.

(The title of this post comes from a related paper by Dhagat, Gács, and Winkler, from SODA 1992, using a different model in which the primitive is incorrect adversarially rather than randomly.)

You might like to perform a bigger computation using these noisy primitives, with high probability of a correct overall outcome despite their errors. An easy way to get more accurate results would be to repeat each primitive many times and take its majority outcome. Repeating a logarithmic number of times would make the failure probability polynomially small, so small that you could make a polynomial number of calls to these repeated primitives and have a good chance of never seeing an error. That polynomially small failure probability is what we mean by “high probability”. But this trivial repetition strategy has a cost: it slows everything down by a logarithmic factor. The goal of our preprint is to find geometry problems for which more sophisticated methods can avoid this slowdown. We achieve this no-slowdown goal for some problems (like constructing convex hulls) and show that it is not possible for others (like finding closest pairs of points, which has a linear-time conventional algorithm but requires \(\Omega(n\log n)\) noisy primitives).

Although we think the application of this model to computational geometry is new, the model of randomly erroneous primitives is not new. It has been applied for instance to comparison-based algorithms for sorting and searching, where the primitive is a comparison between two input numbers.

You might well wonder whether this is just an intellectual puzzle, or whether there is some application for algorithms designed to work with faulty comparison primitives. One application comes from a paper by Manu Viola on communication complexity: “The communication complexity of addition”, Combinatorica 2015, doi:10.1007/s00493-014-3078-3. In one of the problems studied by Viola, two communicating parties (Alice and Bob) each hold an \(n\)-bit binary number. They want to know whose number is bigger, and they don’t care about the secrecy of their numbers, but they would like to find out the result of this numerical comparison by exchanging as few bits of information as possible. You could do this by having Alice tell Bob her whole number, but this would take \(n\) bits of communication. It turns out that Alice and Bob can do much better than this.

Viola considers an algorithm in which Alice and Bob collaborate to perform a binary search for the first bit position where their numbers differ from each other. Once they both know this, they also know who has a 0 in that position and who has a 1, and therefore whose number is larger. If Alice and Bob could test, for a given \(k\), whether their numbers are the same in the first \(k\) bits, then they could compare their numbers by using \(\log_2 n\) of these tests. So the question becomes: how can Alice and Bob perform an equality test of two bitstrings using only very few bits? And when phrased in this way, the obvious answer is: hashing! Do some initial computation to generate a random hash function, then do the equality tests on the hashes of the two bitstrings. These hash values could potentially be much shorter than \(n\) bits, reducing the communication needed per test. But there’s a chance of an error when the two strings collide, hashing to the same value even when they’re unequal.

In a model of computation where Alice and Bob have a shared source of randomness, this method can be made to work with hash functions whose hash values have only a constant number of bits, performing each equality test with a constant number of bits of communication but with a constant probability of error. The trivial repetition strategy would then give an equality test with high probability of correctness but \(O(\log n)\) bits of communication, making the binary search use \(O(\log^2 n)\) bits of communication. Alternatively, using \(O(\log n)\)-bit hash values would again get high probability of correctness (low probability of a hash collision) but again lead to \(O(\log^2 n)\) bits of communication in the binary search. Instead, Viola replaces a standard binary search by a search algorithm that uses a logarithmic number of calls to a noisy primitive, the primitive that uses one hash value with a constant number of bits. This allows Alice and Bob to find which of their numbers is bigger, using only \(O(\log n)\) bits of communication.

The main idea of Viola’s noisy binary search algorithm is for each step of the search to walk up or down in a binary search tree, stepping downward on the basis of noisy comparisons and stepping upward when a test result makes it appear that you’ve made a mistake somewhere earlier. Of course that test result could itself be erroneous! But if you balance the error probabilities correctly you’ll walk downward more often than you walk upward, and by adding logarithmically-long tails below the leaves of the search tree you can have high confidence that when you reach the end of one of these tails it will be the correct one. This same idea of walking upward and downward based on test results and apparent mistakes turns out to be key to our geometric algorithms, as well, but with the twist that the structure we are walking around in is a directed acyclic graph rather than a tree. (For those familiar with randomized incremental algorithms in geometry, it’s the history DAG of a randomized incremental construction.)

(Discuss on Mastodon)

By David Eppstein

The legacy of the Y2K bug tells a story about prevention at large scale, but the Preparedness Paradox applies to individuals as well. There is no shortage of advice out there for how to live a long and healthy life. It comes at us from all directions. Governmental agencies and self-help podcasters preach their ideas of what you can do to live forever.

And yet, some people who do everything right still die early, be it from freak accidents or fateful disease. Some people do everything wrong and live to see 100. How can we know whether preventative medicine will be worth it in the end?

Longevity Guru Peter Attia wrote a whole book based on the idea that mimicking the internal homeostatic mechanisms of centenarians can unlock universal longevity. But Attia admits very early in his mammoth how-to-book/memoir mashup Outlive that he’ll never be able to prove that his ideas actually achieve his goals. Because of the timescales involved, the multifactorial inputs required, and the complete lack of understanding of mechanism, there can be no randomized trial of his longevity protocols. You can’t do “evidence-based” medicine to live forever. Instead, Attia unironically calls his approach “evidence-informed” medicine. Evidence-informed means he reads a lot of papers, talks to people on his podcast, and comes up with what he currently thinks is best based on these experiences. This rings hollow. Given the vastness of the scientific literature and the confirmation bias provided by talking to his friends, “evidence-informed” is just an arrogant, nerdy euphemism for “I go with my gut.”

Indeed, the evidence-based medicine crowd is diametrically opposed to Attia. Evidence-based medicine preaches a medical conservatism that is loath to treat healthy people as patients and argues for only employing interventions that have been demonstrated effective by randomized clinical trials. One of the pioneers of the evidence-based medicine movement, David Sackett, wrote an impassioned editorial decrying “The arrogance of preventive medicine” in the Canadian Medical Association Journal in 2002. He vents:

“First, it is aggressively assertive, pursuing symptomless individuals and telling them what they must do to remain healthy… Second, preventive medicine is presumptuous, confident that the interventions it espouses will, on average, do more good than harm to those who accept and adhere to them. Finally, preventive medicine is overbearing, attacking those who question the value of its recommendations.”

Like in the case of the Y2K story, Attia and Sackett are correct at the same time. How we balance their perspectives and make sense of our lives is what’s challenging.

What makes Sackett more right than Attia is his honesty and humility about what is out of our control. Our bodies, which work so hard to maintain homeostasis, can only do so for so long. And if we spend all of our time preventing the worst, even Attia admits that this makes life stressful and miserable.

A beautiful meditation on how homeostasis can hold for only so long is Siddhartha Mukherjee’s essay “My Father’s Body, at Rest and in Motion.” Mukherjee mourns the death of his father, describing the efforts required to keep him in order until everything falls apart. In a poignant scene, Mukherjee describes how his mother and his father’s nurse worked to create a simulation of his father’s old life in hopes that it might remind his bodily systems of how they used to interoperate:

“And then, quietly, a new kind of physiology started to coalesce around him. The fruit and vegetable sellers began to turn up at home. The daytime nurse—a scraggly young man nicknamed Bishnu: the god, among other things, of maintenance and preservation—made a habit of propping him up in his rocking chair on the balcony every morning, and having the various venders congregate below like a worshipful throng. My father was delighted to be back among the believers. He would banter with them from above—a king under house arrest, but a king nonetheless—berating them about their prices; protesting the abysmal quality of the eggplants; asking why he, at his age, must suffer the sins of their bruised cauliflowers; and why the fish was never quite fresh. It was a small miracle: Mr. Mukherjee could no longer go to the market, and so the market came to Mr. Mukherjee.

“In retrospect, I understood that this, too, was homeostasis of a sort. The little rituals saved him.”

Trying to keep elements of his daily routine together was a way to sustain his life. This simulation wasn’t necessarily what we would call medical intervention. It was an attempt to experiential maintain constancy to maintain physiological constancy.

Mukherjee sees homeostasis in everything, from his father’s body to India’s infrastructure. Homeostasis is about regulation and control, and one of the ways we aim to prolong life is by externally maintaining homeostasis to help our internal homeostatic mechanisms. He raises an interesting question about preventative medicine.

In the tale of the Y2K bug, there were competing alternatives: the expensive fix-everything approach and the fix-on-failure alternative. Some mix was probably required to mitigate the effect of the problem. The same is true with ourselves. No matter how complicated the modern evidence-informed scientist life gurus make it out to be, some measures of prevention are likely helpful. If you look past Attia’s kookier, more expensive advice like getting full-body cancer scans or taking rapamycin prophylactically, then Outlive’s prescriptions amount to eating well, exercising, sleeping well, and living a low-stress lifestyle. Sounds good to me!

But how can you know your measures of prevention did the right thing? Did your daily jogging and healthy diet get you to a healthy 9th decade? Was everything you did to sustain your life worth it because of how you were able to live it? Will you run a statistical regression to prove you lived your life to the fullest?

Subscribe now

By Ben Recht

For any constant $\alpha > 0$, we construct an explicit pseudorandom generator (PRG) that fools $n$-variate decision trees of size $m$ with error $\epsilon$ and seed length $(1 + \alpha) \cdot \log_2 m + O(\log(1/\epsilon) + \log \log n)$. For context, one can achieve seed length $(2 + o(1)) \cdot \log_2 m + O(\log(1/\epsilon) + \log \log n)$ using well-known constructions and analyses of small-bias distributions, but such a seed length is trivial when $m \geq 2^{n/2}$. By combining our new PRG with work by Chen and Kabanets (TCS 2016), we get an explicit PRG that fools circuits of size $2.99\cdot n$ over the $U_2$ basis with error $2^{-\Omega(n)}$ and seed length $(1 - \Omega(1)) \cdot n$. Our approach for fooling decision trees is to develop a new variant of the classic concept of almost $k$-wise independence, which might be of independent interest. We say that a distribution $X$ over $\{0, 1\}^n$ is $k$-wise $\epsilon$-probably uniform if every Boolean function $f$ that depends on only $k$ variables satisfies $\mathbb{E}[f(X)] \geq (1 - \epsilon) \cdot \mathbb{E}[f]$. We show how to sample a $k$-wise $\epsilon$-probably uniform distribution using a seed of length $(1 + \alpha) \cdot k + O(\log(1/\epsilon) + \log \log n)$.

Authors: Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, Vincent Conitzer

Strategic interactions can be represented more concisely, and analyzed and solved more efficiently, if we are aware of the symmetries within the multiagent system. Symmetries also have conceptual implications, for example for equilibrium selection. We study the computational complexity of identifying and using symmetries. Using the classical framework of normal-form games, we consider game symmetries that can be across some or all players and/or actions. We find a strong connection between game symmetries and graph automorphisms, yielding graph automorphism and graph isomorphism completeness results for characterizing the symmetries present in a game. On the other hand, we also show that the problem becomes polynomial-time solvable when we restrict the consideration of actions in one of two ways. Next, we investigate when exactly game symmetries can be successfully leveraged for Nash equilibrium computation. We show that finding a Nash equilibrium that respects a given set of symmetries is PPAD- and CLS-complete in general-sum and team games respectively -- that is, exactly as hard as Brouwer fixed point and gradient descent problems. Finally, we present polynomial-time methods for the special cases where we are aware of a vast number of symmetries, or where the game is two-player zero-sum and we do not even know the symmetries.

Authors: Felicia Lucke

In the Matching Cut problem we ask whether a graph $G$ has a matching cut, that is, a matching which is also an edge cut of $G$. We consider the variants Perfect Matching Cut and Disconnected Perfect Matching where we ask whether there exists a matching cut equal to, respectively contained in, a perfect matching. Further, in the problem Maximum Matching Cut we ask for a matching cut with a maximum number of edges. The last problem we consider is $d$-Cut where we ask for an edge cut where each vertex is incident to at most $d$ edges in the cut. We investigate the computational complexity of these problems on bipartite graphs of bounded radius and diameter. Our results extend known results for Matching Cut and Disconnected Perfect Matching. We give complexity dichotomies for $d$-Cut and Maximum Matching Cut and solve one of two open cases for Disconnected Perfect Matching. For Perfect Matching Cut we give the first hardness result for bipartite graphs of bounded radius and diameter and extend the known polynomial cases.

Authors: Hirokazu Katsumasa, Emily Roff, Masahiko Yoshinaga

Magnitude is a real-valued invariant of metric spaces which, in the finite setting, can be understood as recording the 'effective number of points' in a space as the scale of the metric varies. Motivated by applications in topological data analysis, this paper investigates the stability of magnitude: its continuity properties with respect to the Gromov-Hausdorff topology. We show that magnitude is nowhere continuous on the Gromov-Hausdorff space of finite metric spaces. Yet, we find evidence to suggest that it may be 'generically continuous', in the sense that generic Gromov-Hausdorff limits are preserved by magnitude. We make the case that, in fact, 'generic stability' is what matters for applicability.

Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, Jan Olkowski

One of the classic problems in online decision-making is the *secretary problem* where to goal is to maximize the probability of choosing the largest number from a randomly ordered sequence. A natural extension allows selecting multiple values under a combinatorial constraint. Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) introduced the *matroid secretary conjecture*, suggesting an $O(1)$-competitive algorithm exists for matroids. Many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal is to obtain an $e$-competitive algorithm, and the *strong matroid secretary conjecture* states that this is possible for general matroids. A key class of matroids is the *graphic matroid*, where a set of graph edges is independent if it contains no cycle. The rich combinatorial structure of graphs makes them a natural first step towards solving a problem for general matroids. Babaioff et al. (SODA'07, JACM'18) first studied the graphic matroid setting, achieving a $16$-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). We break this $4$-competitive barrier, presenting a new algorithm with a competitive ratio of $3.95$. For simple graphs, we further improve this to $3.77$. Intuitively, solving the problem for simple graphs is easier since they lack length-two cycles. A natural question is whether a ratio arbitrarily close to $e$ can be achieved by assuming sufficiently large girth. We answer this affirmatively, showing a competitive ratio arbitrarily close to $e$ even for constant girth values, supporting the strong matroid secretary conjecture. We also prove this bound is tight: for any constant $g$, no algorithm can achieve a ratio better than $e$ even when the graph has girth at least $g$.

Authors: Alireza AmaniHamedani, Ali Aouad, Amin Saberi

We study a continuous-time, infinite-horizon dynamic matching problem. Suppliers arrive according to a Poisson process; while waiting, they may abandon the queue at a uniform rate. Customers on the other side of the network must be matched upon arrival. The objective is to minimize the expected long-term average cost subject to a throughput constraint on the total match rate. Previous literature on dynamic matching focuses on "static" policies, where the matching decisions do not depend explicitly on the state of the supplier queues, achieving constant-factor approximations. By contrast, we design "adaptive" policies, which leverage queue length information, and obtain near-optimal polynomial-time algorithms for several classes of instances. First, we develop a bi-criteria Fully Polynomial-time Approximation Scheme (FPTAS) for dynamic matching on networks with a constant number of queues -- that computes a $(1-\epsilon)$-approximation of the optimal policy in time polynomial in both the input size and $1/\epsilon$. Using this algorithm as a subroutine, we obtain an FPTAS for dynamic matching on Euclidean networks of fixed dimension. A key new technique is a hybrid LP relaxation, which combines static and state-dependent LP approximations of the queue dynamics, after a decomposition of the network. Constant-size networks are motivated by deceased organ donation schemes, where the supply types can be divided according to blood and tissue types. The Euclidean case is of interest in ride-hailing and spatial service platforms, where the goal is to fulfill as many trips as possible while minimizing driving distances.

Authors: Jonas Friemel, David Liedtke, Christian Scheffer

Shape formation is one of the most thoroughly studied problems in most algorithmic models of programmable matter. However, few existing shape formation algorithms utilize similarities between an initial configuration and a desired target shape. In the hybrid model, an active agent with the computational capabilities of a deterministic finite automaton can form shapes by lifting and placing passive tiles on the triangular lattice. We study the shape reconfiguration problem where the agent needs to move all tiles in an input shape to so-called target nodes, which are distinguishable from other nodes by the agent. We present a worst-case optimal $O(mn)$ algorithm for simply connected target shapes and an $O(n^4)$ algorithm for a large class of target shapes that may contain holes, where $m$ is the initial number of unoccupied target nodes and $n$ is the total number of tiles.

Authors: James Bailie, Ruobin Gong, Xiao-Li Meng

Through the lens of the system of differential privacy specifications developed in Part I of a trio of articles, this second paper examines two statistical disclosure control (SDC) methods for the United States Decennial Census: the Permutation Swapping Algorithm (PSA), which is similar to the 2010 Census's disclosure avoidance system (DAS), and the TopDown Algorithm (TDA), which was used in the 2020 DAS. To varying degrees, both methods leave unaltered some statistics of the confidential data $\unicode{x2013}$ which are called the method's invariants $\unicode{x2013}$ and hence neither can be readily reconciled with differential privacy (DP), at least as it was originally conceived. Nevertheless, we establish that the PSA satisfies $\varepsilon$-DP subject to the invariants it necessarily induces, thereby showing that this traditional SDC method can in fact still be understood within our more-general system of DP specifications. By a similar modification to $\rho$-zero concentrated DP, we also provide a DP specification for the TDA. Finally, as a point of comparison, we consider the counterfactual scenario in which the PSA was adopted for the 2020 Census, resulting in a reduction in the nominal privacy loss, but at the cost of releasing many more invariants. Therefore, while our results explicate the mathematical guarantees of SDC provided by the PSA, the TDA and the 2020 DAS in general, care must be taken in their translation to actual privacy protection $\unicode{x2013}$ just as is the case for any DP deployment.

• My drunken theorem (\(\mathbb{M}\)). Bill Gasarch’s open problems column in memory of Luca Trevisan brings Lance Fortnow vague memories of drinking and deriving.

• Origami black hole (\(\mathbb{M}\)). xkcd on what happens when you fold too many times.

• Sophie Schmieg’s post-quantum crypto work acquires a crank who thinks he’s “created the first software only true random number generator”. Schmieg heads the ISE Crypto team at Google. It’s not clear to me exactly which blog post led to this, but her blog at Key Material has several interesting posts on post-quantum crypto and signature schemes.

• Buddha cat dreams of Escher birds (\(\mathbb{M}\)).

  

• CodeParade tries to find another neighborly polyhedron (\(\mathbb{M}\)). The only two known ones are the tetrahedron and Szilassi polyhedron. They don’t succeed but they come surprisingly close.

• The rectifiable rectangular peg problem (\(\mathbb{M}\)). New preprint by Tomohiro Asano and Yuichi Ike claims to prove the existence of a rectangle of arbitrary given aspect ratio in any rectifiable simple closed curve.

• Recent encounters with atom-thin salami slicing (\(\mathbb{M}\), via), several case studies in bad-to-dishonest academic publishing uncovered by Reese Richardson.

• Categorifiying Nicomacus of Gerasa’s equation (\(\mathbb{M}\)). A handwavy discussion of what the identity

  \[\sum_{k=1}^n k^3 = \left(\sum_{k=1}^n k\right)^2\]

  might really be counting, with nice pictures of 4-dimensional stacks of cannon balls.

• Quanta on recent irrationality proofs for specific values of \(L\)-series (\(\mathbb{M}\)), along the lines of Apéry’s proof that \(\zeta(3)\) is irrational. Relatedly, @QuantaMagazine@mstdn.social hasn’t posted since June 2023, and @quanta_bot@social.platypush.tech hasn’t posted since November 2022. Is Quanta actually federated anywhere currently?

• Rob Corless is annoyed at the bad reference metadata provided by Google Scholar. My go-to alternatives are MathSciNet/zbMATH for mathematics, DBLP for computer science, and a command-line invocation of curl for anything with a doi.

• Mass exodus of German universities from X/twitter (\(\mathbb{M}\)).

• Andrej Bauer tests Google NotebookLM, “your plastic pal who's fun to be with” “your personalized AI research assistant”. It did not go well. “The short summary is that the tool is exactly as good as an insolent incompetent science journalist.”

• Claire Voisin: Mathematics as a private space – from the unveiling of conjectures to worldwide recognition (\(\mathbb{M}\)). Interesting interview with Voisin in the European Mathematical Society magazine, more about her life and philosophy than her mathematics.

• New Calculator template brings interactivity to Wikipedia articles (\(\mathbb{M}\)). The template basically allows the creation of small forms that allow readers to specify some numbers as input and use a formula to generate an output. It’s even possible to simulate some simple algorithms step-by-step and expand the form after each step: see for instance an example of this for the Euclidean algorithm.

By David Eppstein

We Decide Our Future: Mathematics in the Age of AI

With little computational complexity in the conference, I attended many of the AI talks. You could divide them into Math for AI and AI for Math. Mathematics of course plays critical roles in machine learning optimization, and several talks focused on provably good learning algorithms, though they overemphasized the importance of such. Do you get on a plane because you understand the physics or because air travel has a strong safety record?

But let's focus on AI for Math which generated the most discussion and angst. 

I started the conference sitting on a panel on the challenges of peer review in mathematics. Math doesn't have the replication crisis that dogs other scientific communities. But math does have papers with very specialized, long, detailed proofs and few qualified referees willing to check them over with care. 

We're not there yet, but in the "near future" we ought to have AI systems that can verify well-written proofs by compiling them using proof assistants like Lean. Referees could spend less time on checking proofs and more on deciding whether the model, theorem and/or techniques merit publication. We might get to the point that you couldn't even submit a paper to a journal until the proofs have been verified.

It's what comes next that really spooks mathematicians. While AI has made significant progress in solving competition problems with DeepMind's AlphaProof and Open AI's O3, it has only played minor roles in developing new ideas for theorems. Eventually AI systems will find critical steps for publishable theorems. Who do we give the credit to? When AI systems become stronger that typical PhD students, what kinds of problems to we give the students? 

We'll get plenty of AI slop, flooding journals with mathematical papers that technically prove new theorems but don't offer any particularly interesting or illuminating insights. But we'll also get mathematicians who can unleash an army of virtual grad students to find new connections between different subfields, or make significant progress on major open problems in the field. 

Some mathematicians don't want AI trained on their papers and using their techniques and theorems, even though they wouldn't have problems with other mathematicians doing so. In any case, they might not have much choice as many publishers are making deals with AI companies.

The future of mathematicians might follow that of artists and programmers. The best will do fine since they can find proofs beyond what an AI can do. Mathematicians who know how to ask the right questions can harness AI to make themselves far more productive. All mathematicians will have to navigate this brave new world.

"At least they'll still need us to teach the courses," one mathematician told me. Don't be so sure.

By Lance Fortnow

The Department of Computer Science at Reykjavik University invites applications for full-time, permanent faculty positions at any rank, in the fields of data science, software engineering, theoretical computer science, as well as visual computing, games, and interactive media.

Website: https://ui-jobs.50skills.app/ru/en/32303
Email: hansr@ru.is

By shacharlovett

Authors: Emile Anand

Expander graphs are among the most useful combinatorial objects in theoretical computer science. A line of work studies random walks on expander graphs for their pseudorandomness against various classes of test functions, including symmetric functions, read-only branching programs, permutation branching programs, and $\mathrm{AC}^0$ circuits. The promising results of pseudorandomness of expander random walks against $\mathrm{AC}^0$ circuits indicate a robustness of expander random walks beyond symmetric functions, motivating the question of whether expander random walks can fool more robust \emph{asymmetric} complexity classes, such as $\mathrm{ACC}^0$. In this work, we make progress towards this question by considering certain two-layered circuit compositions of $\mathrm{MOD}[k]$ gates, where we show that these family of circuits are fooled by expander random walks with total variation distance error $O(\lambda)$, where $\lambda$ is the second largest eigenvalue of the underlying expander graph. For $k\geq 3$, these circuits can be highly asymmetric with complicated Fourier characters. In this context, our work takes a step in the direction of fooling more complex asymmetric circuits. Separately, drawing from the learning-theory literature, we construct an explicit threshold circuit in the circuit family $\mathrm{TC}^0$, and show that it \emph{is} fooled by expander random walks, providing an upper bound on the set of functions fooled by expander random walks.

Authors: David Eppstein, Michael T. Goodrich, Vinesh Sridhar

Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line L?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, dynamic 2D convex hulls, and Delaunay triangulations for noisy primitives in optimal time with high probability.

Authors: Catalin E. Brita, Jacobus G. M. van der Linden, Emir Demirović

Computing an optimal classification tree that provably maximizes training performance within a given size limit, is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three. Therefore, most methods rely on a coarse binarization of continuous features to maintain scalability. We propose a novel algorithm that optimizes trees directly on the continuous feature data using dynamic programming with branch-and-bound. We develop new pruning techniques that eliminate many sub-optimal splits in the search when similar to previously computed splits and we provide an efficient subroutine for computing optimal depth-two trees. Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedy heuristics.

Authors: Shangdi Yu, Laxman Dhulipala, Jakub Łącki, Nikos Parotsidis

We consider the problem of maintaining a hierarchical agglomerative clustering (HAC) in the dynamic setting, when the input is subject to point insertions and deletions. We introduce DynHAC - the first dynamic HAC algorithm for the popular average-linkage version of the problem which can maintain a 1+\epsilon approximate solution. Our approach leverages recent structural results on (1+\epsilon)-approximate HAC to carefully identify the part of the clustering dendrogram that needs to be updated in order to produce a solution that is consistent with what a full recomputation from scratch would have output. We evaluate DynHAC on a number of real-world graphs. We show that DynHAC can handle each update up to 423x faster than what it would take to recompute the clustering from scratch. At the same time it achieves up to 0.21 higher NMI score than the state-of-the-art dynamic hierarchical clustering algorithms, which do not provably approximate HAC.

Back in the nineties, I was told computers would end the world. Not because they would become superintelligent like in the movies, but because programmers had been frugal/lazy and written years with only two digits. You know how we write dates with only the last two digits of the year (01/14/25)? Well, computers were programmed this way too. That meant that when we moved from year 99 to year 00, havoc would break loose because differences in years would give invalid negative numbers. Newborns would be classified as centenarians, banks would lose all records of their holdings, planes would fall from the sky, nuclear missiles would launch themselves…

To prevent this pending disaster, IT departments around the world united to patch code bases. People received hefty bonuses if they could read and write the COBOL that instructed our ancient mainframes. Hundreds of billions of dollars were invested to patch this annoying problem that years should be represented by four digits, not two.1

When the clock struck midnight on December 31, 1999, the Judgment Day predicted by Prince did not arrive. Some things definitely broke, and the wikipedia has a fun list of some of the systems that crashed. For instance, some ticket dispensers on public transit stopped working. But it was not the end of the world as we knew it.

Why did the doomsday predictions not pan out? This is a fascinating question of causal inference. It could be that the concerted efforts of IT workers programmed our way out of the apocalypse. It could be that the predicted consequences of data overflows were overblown, and most of the Y2K bugs were relatively minor threats that could be fixed upon failure. How could we know the difference? Historians spend their time assembling strong evidentiary bases to impute why things that happened happened. But how do we assemble evidence to argue about the cause of something that didn’t happen?

One technique might be to look to “synthetic controls,” places that faced similar circumstances but took different actions. As I read retrospectives on Y2K, I was surprised to learn that some countries decided to do nothing! Not only did Italy and Russia do nothing, but the US State Department issued an advisory not to visit these countries because of potential Y2K catastrophes. Of course, nothing catastrophic happened in either country.

Now, this isn’t evidence that the prevention in the US wasn’t important! These countries are not perfect comparisons. However, it does suggest that those who raised maximal Y2K panic were way off. And the reporting of the time tended to amplify the doomsayers and downplay any reasonable prognoses. I mean, this book is real:

Yet plenty of people at the time tried to quell the alarm about the Y2K panic.

Computer science professor Ross Anderson was initially so afraid that in 1996 he bought a cabin in the woods to ride out the millennium. He had calmed down considerably by 1999. After assessing and fixing the bugs at Cambridge University, he came away with a sanguine prediction in December 1999:

“The surprising discovery is that although some systems have been fixed or replaced, none of the bugs found so far would have had a serious impact on our business operations even if they had been ignored until January 2000.

“So the UK government anxiety about the millennium bug compliance of small-to-medium sized enterprises appears misplaced. The average small business owner, who is doing absolutely nothing about the bug, appears to be acting quite rationally. This does not mean that the millennium bug is harmless.

“There are still risks to the economy and to public safety, but in the UK at least they appear to be minor.”

Friend-of-the-blog John Quiggin, who has been blogging since before blogs were a thing, also bet that the Y2K bug was overhyped. You can read his prescient predictions from September 1999 here. Notably, John noted that by 1999, about half of the catastrophic failures should have already happened! This information guided his prediction:

“We can use the Gartner Group's analysis to conclude that date-related problems in the year 2000 will be about twice as severe as those in 1999. Since twice zero is still zero, it looks as if it is time to start running down those emergency stocks of baked beans.”

Finally, as a last piece of Y2K minimizing evidence, let’s be honest with ourselves about programming computers. We all know that for every bug we patch, we create two more bugs. The idea that our global effort fixed all bugs and didn’t introduce new glitches is unreasonable. In fact, it wasn’t the case. Buggy Y2K patches took out several US spy satellites for several days: “It was the only serious military consequence of the year 2000 rollover, for which the Pentagon prepared at a cost of $3.6 billion.” Considering that the massive bug patching didn’t create more failures adds credence to the position that the Y2K bug was not world-ending.

I’ve said it a couple of times already, and I’ll say it one more time to fend off grumpy commenters: Don’t take this presentation of evidence as an argument that Y2K wasn’t a real issue. I’m not taking sides here. I’m instead interested in how to best assemble historical evidence to assess why catastrophe didn’t occur in the year 2000. How can we think about retrospective evidence of non-catastrophes? On the 25th anniversary of the end of the world as we know it, John Quiggin wrote a retrospective arguing that we’ll never know. Or, as John puts it, the Y2K experience was a “Rashomon phenomenon. Many realities are simultaneously true:

“For programmers in large organisations, the experience of Y2k remediation was that of a huge effort that fixed plenty of bugs was 100 % effective. For small businesses and schools, another thing to worry about about, but too hard to solve, leading to “fix on failure” when problems emerged. For Pollyannas like me who correctly predicted few critical problems anywhere, vindication, but no credit. For most people, another panic and false alarm.”

All of these are simultaneously true. This is the crux of “the preparedness paradox.” In prevention, whether it be preventing natural disasters or individual illness, your hard work can simultaneously pay off and not have been worth it. It can be simultaneously true that you overreacted, but a reaction was essential. And it can be true that not all prevention for the sake of prevention is good. When regulation impacts people’s lives, “preparedness” can be a huge ask. We can’t govern by moral panic, yet we need guardrails against potential disasters. How we balance these makes governance daunting. Especially because citizens can believe completely contradictory things about the state of affairs and still all be correct.

Subscribe now

By Ben Recht

May 12-14, 2025 Hnanice, Czechia https://radioelektronika.cz The conference is expected to attract a large number of researchers, scientists, industry experts, and students who are interested in the latest developments in electronics, signal processing, applications, information technology, microwave engineering, and related fields.

By shacharlovett

Authors: Luís Cunha, Jack Kuipers, Thiago Lopes

The mutational heterogeneity of tumours can be described with a tree representing the evolutionary history of the tumour. With noisy sequencing data there may be uncertainty in the inferred tree structure, while we may also wish to study patterns in the evolution of cancers in different patients. In such situations, understanding tree similarities is a key challenge, and therefore we present an approach to determine distances between trees. Considering the bounded height of trees, we determine the distances associated with the swap operations over strings. While in general, by solving the {\sc Maximum Common Almost $v$-tree} problem between two trees, we describe an efficient approach to determine the minimum number of operations to transform one tree into another. The inherent noise in current statistical methods for constructing mutation evolution trees of cancer cells presents a significant challenge: handling such collections of trees to determine a consensus tree that accurately represents the set and evaluating the extent of their variability or dispersion. Given a set of mutation trees and the notion of distance, there are at least two natural ways to define the ``target'' tree, such as a min-sum (\emph{median tree}) or a min-max (\emph{closest tree}) of a set of trees. Thus, considering a set of trees as input and dealing with the {\sc median} and {\sc closest} problems, we prove that both problems are \NP-complete, even with only three input trees. In addition, we develop algorithms to obtain upper bounds on the median and closest solutions, which are analysed by the experiments presented on generated and on real databases. We show a fast way to find consensus trees with better results than any tree in the input set while still preserving all internal structure.

Authors: Kyle Burke, Craig Tennenhouse

We demonstrate that Col is PSPACE-complete on triangular grid graphs via a reduction from Bounded Two-Player Constraint Logic. This is the most structured graph family that Col is known to be computationally hard for.

Authors: Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Wei Wang, Jiahao Zhang

Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data, leveraging the message-passing mechanism that iteratively propagates node embeddings through graph structures. While GNNs have achieved significant empirical success, their theoretical limitations remain an active area of research. Existing studies primarily focus on characterizing GNN expressiveness through Weisfeiler-Lehman (WL) graph isomorphism tests. In this paper, we take a fundamentally different approach by exploring the computational limitations of GNNs through the lens of circuit complexity. Specifically, we analyze the circuit complexity of common GNN architectures and prove that under constraints of constant-depth layers, linear or sublinear embedding sizes, and polynomial precision, GNNs cannot solve key problems such as graph connectivity and graph isomorphism unless $\mathsf{TC}^0 = \mathsf{NC}^1$. These results reveal the intrinsic expressivity limitations of GNNs behind their empirical success and introduce a novel framework for analyzing GNN expressiveness that can be extended to a broader range of GNN models and graph decision problems.

Authors: Brice Huang, Mark Sellke

It is a folklore belief in the theory of spin glasses and disordered systems that out-of-equilibrium dynamics fail to find stable local optima exhibiting e.g. local strict convexity on physical time-scales. In the context of the Sherrington--Kirkpatrick spin glass, Behrens-Arpino-Kivva-Zdeborov\'a and Minzer-Sah-Sawhney have recently conjectured that this obstruction may be inherent to all efficient algorithms, despite the existence of exponentially many such optima throughout the landscape. We prove this search problem exhibits strong low degree hardness for polynomial algorithms of degree $D\leq o(N)$: any such algorithm has probability $o(1)$ to output a stable local optimum. To the best of our knowledge, this is the first result to prove that even constant-degree polynomials have probability $o(1)$ to solve a random search problem without planted structure. To prove this, we develop a general-purpose enhancement of the ensemble overlap gap property, and as a byproduct improve previous results on spin glass optimization, maximum independent set, random $k$-SAT, and the Ising perceptron to strong low degree hardness. Finally for spherical spin glasses with no external field, we prove that Langevin dynamics does not find stable local optima within dimension-free time.

Authors: Arthur Bawin, André Garon, Jean-François Remacle

Anisotropic mesh adaptation with Riemannian metrics has proven effective for generating straight-sided meshes with anisotropy induced by the geometry of interest and/or the resolved physics. Within the continuous mesh framework, anisotropic meshes are thought of as discrete counterparts to Riemannian metrics. Ideal, or unit, simplicial meshes consist only of simplices whose edges exhibit unit or quasi-unit length with respect to a given Riemannian metric. Recently, mesh adaptation with high-order (i.e., curved) elements has grown in popularity in the meshing community, as the additional flexibility of high-order elements can further reduce the approximation error. However, a complete and competitive methodology for anisotropic and high-order mesh adaptation is not yet available. The goal of this paper is to address a key aspect of metric-based high-order mesh adaptation, namely, the adequacy between a Riemannian metric and high-order simplices. This is done by extending the notions of unit simplices and unit meshes, central to the continuous mesh framework, to high-order elements. The existing definitions of a unit simplex are reviewed, then a broader definition involving Riemannian isometries is introduced to handle curved and high-order simplices. Similarly, the notion of quasi-unitness is extended to curved simplices to tackle the practical generation of high-order meshes. Proofs of concept for unit and (quasi-)isometric meshes are presented in two dimensions.

Authors: Mónika Csikós, Alexandre Louvet, Nabil Mustafa

Simplicial partitions are a fundamental structure in computational geometry, as they form the basis of optimal data structures for range searching and several related problems. Current algorithms are built on very specific spatial partitioning tools tailored for certain geometric cases. This severely limits their applicability to general set systems. In this work, we propose a simple greedy heuristic for constructing simplicial partitions of any set system. We present a thorough empirical evaluation of its behavior on a variety of geometric and non-geometric set systems, showing that it performs well on most instances. Implementation of these algorithms is available on Github.

Authors: Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn

We consider coresets for $k$-clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the $k$-median objective $\sum_{p}\min_{c\in C}dist(p,C)$. Given a point set $P$, a coreset $\Omega$ is a small weighted subset that approximates the cost of $P$ for all candidate solutions $C$ up to a $(1\pm\varepsilon )$ multiplicative factor. In this paper, we give a sharp VC-dimension based analysis for coreset construction. As a consequence, we obtain improved $k$-median coreset bounds for the following metrics: Coresets of size $\tilde{O}\left(k\varepsilon^{-2}\right)$ for shortest path metrics in planar graphs, improving over the bounds $\tilde{O}\left(k\varepsilon^{-6}\right)$ by [Cohen-Addad, Saulpic, Schwiegelshohn, STOC'21] and $\tilde{O}\left(k^2\varepsilon^{-4}\right)$ by [Braverman, Jiang, Krauthgamer, Wu, SODA'21]. Coresets of size $\tilde{O}\left(kd\ell\varepsilon^{-2}\log m\right)$ for clustering $d$-dimensional polygonal curves of length at most $m$ with curves of length at most $\ell$ with respect to Frechet metrics, improving over the bounds $\tilde{O}\left(k^3d\ell\varepsilon^{-3}\log m\right)$ by [Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, and Wu, FOCS'22] and $\tilde{O}\left(k^2d\ell\varepsilon^{-2}\log m \log |P|\right)$ by [Conradi, Kolbe, Psarros, Rohde, SoCG'24].

Authors: Daniel Anderson, Guy E. Blelloch, Siddhartha Jayanti

In this paper, we give theoretically and practically efficient implementations of Big Atomics, i.e., $k$-word linearizable registers that support the load, store, and compare-and-swap (CAS) operations. While modern hardware supports $k = 1$ and sometimes $k = 2$ (e.g., double-width compare-and-swap in x86), our implementations support arbitrary $k$. Big Atomics are useful in many applications, including atomic manipulation of tuples, version lists, and implementing load-linked/store-conditional (LL/SC). We design fast, lock-free implementations of big atomics based on a novel fast-path-slow-path approach we develop. We then use them to develop an efficient concurrent hash table, as evidence of their utility. We experimentally validate the approach by comparing a variety of implementations of big atomics under a variety of workloads (thread counts, load/store ratios, contention, oversubscription, and number of atomics). The experiments compare two of our lock-free variants with C++ std::atomic, a lock-based version, a version using sequence locks, and an indirect version. The results show that our approach is close to the fastest under all conditions and far outperforms others under oversubscription. We also compare our big atomics based concurrent hash table to a variety of other state-of-the-art hash tables that support arbitrary length keys and values, including implementations from Intel's TBB, Facebook's Folly, libcuckoo, and a recent release from Boost. The results show that our approach of using big atomics in the design of hash tables is a promising direction.

Authors: Marius Dumitran

This thesis investigates three biologically inspired operations: prefix-suffix duplication, bounded prefix-suffix duplication, and prefix-suffix-square completion. Duplication, a common genetic mutation, involves repeating DNA sequences and is modeled here as formal operations on words. The prefix-suffix duplication generates non-context-free languages, even from simple initial words. To better reflect biological processes, we propose a bounded variant that limits duplication length, resolving unsolved problems and aligning with biochemical realities. We also introduce the prefix-suffix-square completion operation, which generates squares at sequence ends. This operation enables the generation of infinite words such as Fibonacci, Period-doubling, and Thue-Morse, which contain squares but avoid higher exponent repetitions, highlighting unique structural properties. In contrast, prefix-suffix duplication cannot generate certain infinite words, such as Thue-Morse, but can produce cube-free words. Additionally, we address the detection of gapped repeats and palindromes-structures important in DNA and RNA analysis. These involve repeating or reversed factors flanking a central gap. Previous studies imposed constraints on gap length or arm-gap relationships; we extend this by solving the problem in three novel settings. This work advances theoretical insights into biologically inspired operations and their computational applications in genetic modeling.

Authors: Mohsen Koohi Esfahani, Hans Vandierendonck

This paper investigates the shared-memory Graph Transposition (GT) problem, a fundamental graph algorithm that is widely used in graph analytics and scientific computing. Previous GT algorithms have significant memory requirements that are proportional to the number of vertices and threads which obstructs their use on large graphs. Moreover, atomic memory operations have become comparably fast on recent CPU architectures, which creates new opportunities for improving the performance of concurrent atomic accesses in GT. We design PoTra, a GT algorithm which leverages graph structure and processor and memory architecture to optimize locality and performance. PoTra limits the size of additional data structures close to CPU cache sizes and utilizes the skewed degree distribution of graph datasets to optimize locality and performance. We present the performance model of PoTra to explain the connection between cache and memory response times and graph locality. Our evaluation of PoTra on three CPU architectures and 20 real-world and synthetic graph datasets with up to 128 billion edges demonstrates that PoTra achieves up to 8.7 times speedup compared to previous works and if there is a performance loss it remains limited to 15.7%, on average.

Authors: Ruizhong Qiu, Jun-Gi Jang, Xiao Lin, Lihui Liu, Hanghang Tong

Tucker decomposition has been widely used in a variety of applications to obtain latent factors of tensor data. In these applications, a common need is to compute Tucker decomposition for a given time range. Furthermore, real-world tensor time series are typically evolving in the time dimension. Such needs call for a data structure that can efficiently and accurately support range queries of Tucker decomposition and stream updates. Unfortunately, existing methods do not support either range queries or stream updates. This challenging problem has remained open for years prior to our work. To solve this challenging problem, we propose TUCKET, a data structure that can efficiently and accurately handle both range queries and stream updates. Our key idea is to design a new data structure that we call a stream segment tree by generalizing the segment tree, a data structure that was originally invented for computational geometry. For a range query of length $L$, our TUCKET can find $O(\log L)$ nodes (called the hit set) from the tree and efficiently stitch their preprocessed decompositions to answer the range query. We also propose an algorithm to optimally prune the hit set via an approximation of subtensor decomposition. For the $T$-th stream update, our TUCKET modifies only amortized $O(1)$ nodes and only $O(\log T)$ nodes in the worst case. Extensive evaluation demonstrates that our TUCKET consistently achieves the highest efficiency and accuracy across four large-scale datasets. Our TUCKET achieves at least 3 times lower latency and at least 1.4 times smaller reconstruction error than Zoom-Tucker on all datasets.

Authors: Dekel Tsur

In the 3-Hitting Set problem, the input is a hypergraph $G$ such that the size of every hyperedge of $G$ is at most 3, and an integers $k$, and the goal is to decide whether there is a set $S$ of at most $k$ vertices such that every hyperedge of $G$ contains at least one vertex from $S$. In this paper we give an $O^*(2.0409^k)$-time algorithm for 3-Hitting Set.

Authors: Jerry Chee, Arturs Backurs, Rainie Heck, Li Zhang, Janardhan Kulkarni, Thomas Rothvoss, Sivakanth Gopi

Quantizing the weights of a neural network has two steps: (1) Finding a good low bit-complexity representation for weights (which we call the quantization grid) and (2) Rounding the original weights to values in the quantization grid. In this paper, we study the problem of rounding optimally given any quantization grid. The simplest and most commonly used way to round is Round-to-Nearest (RTN). By rounding in a data-dependent way instead, one can improve the quality of the quantized model significantly. We study the rounding problem from the lens of \emph{discrepancy theory}, which studies how well we can round a continuous solution to a discrete solution without affecting solution quality too much. We prove that given $m=\mathrm{poly}(1/\epsilon)$ samples from the data distribution, we can round all but $O(m)$ model weights such that the expected approximation error of the quantized model on the true data distribution is $\le \epsilon$ as long as the space of gradients of the original model is approximately low rank (which we empirically validate). Our proof, which is algorithmic, inspired a simple and practical rounding algorithm called \emph{DiscQuant}. In our experiments, we demonstrate that DiscQuant significantly improves over the prior state-of-the-art rounding method called GPTQ and the baseline RTN over a range of benchmarks on Phi3mini-3.8B and Llama3.1-8B. For example, rounding Phi3mini-3.8B to a fixed quantization grid with 3.25 bits per parameter using DiscQuant gets 64\% accuracy on the GSM8k dataset, whereas GPTQ achieves 54\% and RTN achieves 31\% (the original model achieves 84\%). We make our code available at https://github.com/jerry-chee/DiscQuant.

We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalizations of structured low-degree $F_2$-polynomials that we did not have correlation bounds for before. In particular: 1. We construct a PRG for width-2 $poly(n)$-length branching programs which read $d$ bits at a time with seed length $2^{O(\sqrt{\log n})}\cdot d^2\log^2(1/\epsilon)$. This comes quadratically close to optimal dependence in $d$ and $\log(1/\epsilon)$. Improving the dependence on $n$ would imply nontrivial PRGs for $\log n$-degree $F_2$-polynomials. The previous PRG by Bogdanov, Dvir, Verbin, and Yehudayoff had an exponentially worse dependence on $d$ with seed length of $O(d\log n + d2^d\log(1/\epsilon))$. 2. We provide correlation bounds and PRGs against size-$n^{\Omega(\log n)}$ AC0 circuits with either $n^{.99}$ SYM gates (computing an arbitrary symmetric function) or $n^{.49}$ THR gates (computing an arbitrary linear threshold function). Previous work of Servedio and Tan only handled $n^{.49}$ SYM gates or $n^{.24}$ THR gates, and previous work of Lovett and Srinivasan only handled polysize circuits. 3. We give exponentially small correlation bounds against degree-$n^{O(1)}$ $F_2$-polynomials set-multilinear over some partition of the input into $n^{.99}$ parts (noting that at $n$ parts, we recover all low-degree polynomials). This generalizes correlation bounds against degree-$(d-1)$ polynomials which are set-multilinear over a fixed partition into $d$ blocks, which were established by Bhrushundi, Harsha, Hatami, Kopparty and Kumar. The common technique behind all of these results is to fortify a hard function with the right type of extractor to obtain stronger correlation bounds. Although this technique has been used in previous work, it relies on the model shrinking to a very small class under random restrictions. Our results show such fortification can be done even for classes that do not enjoy such behavior.

Authors: Ioanna Mitropoulou, Amir Vaxman, Olga Diamanti, Benjamin Dillenburger

We present a method to fabricate double shell structures printed in trans-versal directions using multi-axis fused-deposition-modeling (FDM) robot-ic 3D printing. Shell structures, characterized by lightweight, thin walls, fast buildup, and minimal material usage, find diverse applications in pro-totyping and architecture for uses such as fa\c{c}ade panels, molds for concrete casting, or full-scale pavilions. We leverage an underlying representation of transversal strip networks generated using existing methods and propose a methodology for converting them into printable partitions. Each partition is printed separately and assembled into a double-shell structure. We out-line the specifications and workflow that make the printing of each piece and the subsequent assembly process feasible. The versatility and robust-ness of our method are demonstrated with both digital and fabricated re-sults on surfaces of different scales and geometric complexity.