Last Update

OPML feed of all feeds.

Subscribe to the Atom feed, RSS feed to stay up to date.

Thank you to arXiv for use of its open access interoperability.

Note: the date of arXiv entries announced right after publication holidays might incorrectly show up as the date of the publication holiday itself. This is due to our ad hoc method of inferring announcement dates, which are not returned by the arXiv API.

Powered by Pluto.

Source on GitHub.

Maintained by Nima Anari, Arnab Bhattacharyya, Gautam Kamath.

Theory of Computing Report

Friday, August 08

Minimal Model Reasoning in Description Logics: Don't Try This at Home!

from arXiv: Computational Complexity

Authors: Federica Di Stefano, Quentin Manière, Magdalena Ortiz, Mantas Šimkus

Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates, letting the remaining predicates vary or be fixed, as proposed in circumscription, has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. We address this problem in popular DLs and obtain surprisingly negative results: concept satisfiability in minimal models is undecidable already for $\mathcal{EL}$. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite$_{\text{core}}$, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite$_{\text{horn}}$.

Authors: Federica Di Stefano, Quentin Manière, Magdalena Ortiz, Mantas Šimkus

Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates, letting the remaining predicates vary or be fixed, as proposed in circumscription, has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. We address this problem in popular DLs and obtain surprisingly negative results: concept satisfiability in minimal models is undecidable already for $\mathcal{EL}$. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite$_{\text{core}}$, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite$_{\text{horn}}$.

NP-Hardness and ETH-Based Inapproximability of Communication Complexity via Relaxed Interlacing

from arXiv: Data Structures and Algorithms

Authors: Serge Gaspers, Zixu He, Simon Mackenzie

We prove that computing the deterministic communication complexity D(f) of a Boolean function is NP-hard, even when protocols are limited to a constant number of alternations, resolving a question first posed by Yao (1979). Our reduction builds and expands on a suite of structural "interlacing" lemmas introduced by Mackenzie and Saffidine (arXiv:2505.12345); these lemmas can be reused as black boxes in future lower-bound constructions. The instances produced by our reduction admit optimal protocols that use only constant alternations, so NP-hardness holds under stronger restrictions than those considered in concurrent and independent work by Hirahara, Ilango, and Loff (arXiv:2507.06789), whose proof requires unbounded alternations. Because the gadgets in our construction are self-similar, they can be recursively embedded. We sketch how this yields, under the Exponential-Time Hypothesis, an additive inapproximability gap that grows without bound, and we outline a route toward NP-hardness of approximating D(f) within a fixed constant additive error. Full details of the ETH-based inapproximability results will appear in a future version. Beyond settling the complexity of deterministic communication complexity itself, the modular framework we develop opens the door to a wider class of reductions and, we believe, will prove useful in tackling other long-standing questions in communication complexity.

Authors: Serge Gaspers, Zixu He, Simon Mackenzie

We prove that computing the deterministic communication complexity D(f) of a Boolean function is NP-hard, even when protocols are limited to a constant number of alternations, resolving a question first posed by Yao (1979). Our reduction builds and expands on a suite of structural "interlacing" lemmas introduced by Mackenzie and Saffidine (arXiv:2505.12345); these lemmas can be reused as black boxes in future lower-bound constructions. The instances produced by our reduction admit optimal protocols that use only constant alternations, so NP-hardness holds under stronger restrictions than those considered in concurrent and independent work by Hirahara, Ilango, and Loff (arXiv:2507.06789), whose proof requires unbounded alternations. Because the gadgets in our construction are self-similar, they can be recursively embedded. We sketch how this yields, under the Exponential-Time Hypothesis, an additive inapproximability gap that grows without bound, and we outline a route toward NP-hardness of approximating D(f) within a fixed constant additive error. Full details of the ETH-based inapproximability results will appear in a future version. Beyond settling the complexity of deterministic communication complexity itself, the modular framework we develop opens the door to a wider class of reductions and, we believe, will prove useful in tackling other long-standing questions in communication complexity.

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem

from arXiv: Data Structures and Algorithms

Authors: Jingyang Zhao, Mingyu Xiao

The Capacitated Arc Routing Problem (CARP), introduced by Golden and Wong in 1981, is an important arc routing problem in Operations Research, which generalizes the famous Capacitated Vehicle Routing Problem (CVRP). When every customer has a unit demand, the best known approximation ratio for CARP, given by Jansen in 1993, remains $\frac{5}{2}-\frac{1.5}{k}$, where $k$ denotes the vehicle capacity. Based on recent progress in approximating CVRP, we improve this result by proposing a $(\frac{5}{2}-\Theta(\frac{1}{\sqrt{k}}))$-approximation algorithm, which to the best of our knowledge constitutes the first improvement over Jansen's bound.

Authors: Jingyang Zhao, Mingyu Xiao

The Capacitated Arc Routing Problem (CARP), introduced by Golden and Wong in 1981, is an important arc routing problem in Operations Research, which generalizes the famous Capacitated Vehicle Routing Problem (CVRP). When every customer has a unit demand, the best known approximation ratio for CARP, given by Jansen in 1993, remains $\frac{5}{2}-\frac{1.5}{k}$, where $k$ denotes the vehicle capacity. Based on recent progress in approximating CVRP, we improve this result by proposing a $(\frac{5}{2}-\Theta(\frac{1}{\sqrt{k}}))$-approximation algorithm, which to the best of our knowledge constitutes the first improvement over Jansen's bound.

Parameterized complexity of isometric path partition: treewidth and diameter

from arXiv: Data Structures and Algorithms

Authors: Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale

We investigate the parameterized complexity of the Isometric Path Partition problem when parameterized by the treewidth ($\mathrm{tw}$) of the input graph, arguably one of the most widely studied parameters. Courcelle's theorem shows that graph problems that are expressible as MSO formulas of constant size admit FPT algorithms parameterized by the treewidth of the input graph. This encompasses many natural graph problems. However, many metric-based graph problems, where the solution is defined using some metric-based property of the graph (often the distance) are not expressible as MSO formulas of constant size. These types of problems, Isometric Path Partition being one of them, require individual attention and often draw the boundary for the success story of parameterization by treewidth. In this paper, we prove that Isometric Path Partition is $W[1]$-hard when parameterized by treewidth (in fact, even pathwidth), answering the question by Dumas et al. [SIDMA, 2024], Fernau et al. [CIAC, 2023], and confirming the aforementioned tendency. We complement this hardness result by designing a tailored dynamic programming algorithm running in $n^{O(\mathrm{tw})}$ time. This dynamic programming approach also results in an algorithm running in time $\textrm{diam}^{O(\mathrm{tw}^2)} \cdot n^{O(1)}$, where $\textrm{diam}$ is the diameter of the graph. Note that the dependency on treewidth is unusually high, as most problems admit algorithms running in time $2^{O(\mathrm{tw})}\cdot n^{O(1)}$ or $2^{O(\mathrm{tw} \log (\mathrm{tw}))}\cdot n^{O(1)}$. However, we rule out the possibility of a significantly faster algorithm by proving that Isometric Path Partition does not admit an algorithm running in time $\textrm{diam}^{o(\mathrm{tw}^2/(\log^3(\mathrm{tw})))} \cdot n^{O(1)}$, unless the Randomized-ETH fails.

Authors: Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale

We investigate the parameterized complexity of the Isometric Path Partition problem when parameterized by the treewidth ($\mathrm{tw}$) of the input graph, arguably one of the most widely studied parameters. Courcelle's theorem shows that graph problems that are expressible as MSO formulas of constant size admit FPT algorithms parameterized by the treewidth of the input graph. This encompasses many natural graph problems. However, many metric-based graph problems, where the solution is defined using some metric-based property of the graph (often the distance) are not expressible as MSO formulas of constant size. These types of problems, Isometric Path Partition being one of them, require individual attention and often draw the boundary for the success story of parameterization by treewidth. In this paper, we prove that Isometric Path Partition is $W[1]$-hard when parameterized by treewidth (in fact, even pathwidth), answering the question by Dumas et al. [SIDMA, 2024], Fernau et al. [CIAC, 2023], and confirming the aforementioned tendency. We complement this hardness result by designing a tailored dynamic programming algorithm running in $n^{O(\mathrm{tw})}$ time. This dynamic programming approach also results in an algorithm running in time $\textrm{diam}^{O(\mathrm{tw}^2)} \cdot n^{O(1)}$, where $\textrm{diam}$ is the diameter of the graph. Note that the dependency on treewidth is unusually high, as most problems admit algorithms running in time $2^{O(\mathrm{tw})}\cdot n^{O(1)}$ or $2^{O(\mathrm{tw} \log (\mathrm{tw}))}\cdot n^{O(1)}$. However, we rule out the possibility of a significantly faster algorithm by proving that Isometric Path Partition does not admit an algorithm running in time $\textrm{diam}^{o(\mathrm{tw}^2/(\log^3(\mathrm{tw})))} \cdot n^{O(1)}$, unless the Randomized-ETH fails.

Online Sparsification of Bipartite-Like Clusters in Graphs

from arXiv: Data Structures and Algorithms

Authors: Joyentanuj Das, Suranjan De, He Sun

Graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most graph clustering algorithms is to find a vertex set of low conductance, a sequence of recent studies highlights the importance of the inter-connection between vertex sets when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online sparsification algorithms that find such clusters in both undirected graphs and directed ones. We conduct experimental studies on both synthetic and real-world datasets, and show that our algorithms significantly speedup the running time of existing clustering algorithms while preserving their effectiveness.

Authors: Joyentanuj Das, Suranjan De, He Sun

Graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most graph clustering algorithms is to find a vertex set of low conductance, a sequence of recent studies highlights the importance of the inter-connection between vertex sets when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online sparsification algorithms that find such clusters in both undirected graphs and directed ones. We conduct experimental studies on both synthetic and real-world datasets, and show that our algorithms significantly speedup the running time of existing clustering algorithms while preserving their effectiveness.

Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size

from arXiv: Data Structures and Algorithms

Authors: Fangjian Shen, Yicheng Zheng, Wushao Wen, Hankz Hankui Zhuo

In this paper, we present fixed-parameter tractability algorithms for both the undirected and directed versions of the Spanning Tree Isomorphism Problem, parameterized by the size $k$ of a redundant set. A redundant set is a collection of edges whose removal transforms the graph into a spanning tree. For the undirected version, our algorithm achieves a time complexity of $O(n^2 \log n \cdot 2^{k \log k})$. For the directed version, we propose a more efficient algorithm with a time complexity of $O(n^2 \cdot 2^{4k-3})$, where $n$ is the number of vertices.

Authors: Fangjian Shen, Yicheng Zheng, Wushao Wen, Hankz Hankui Zhuo

In this paper, we present fixed-parameter tractability algorithms for both the undirected and directed versions of the Spanning Tree Isomorphism Problem, parameterized by the size $k$ of a redundant set. A redundant set is a collection of edges whose removal transforms the graph into a spanning tree. For the undirected version, our algorithm achieves a time complexity of $O(n^2 \log n \cdot 2^{k \log k})$. For the directed version, we propose a more efficient algorithm with a time complexity of $O(n^2 \cdot 2^{4k-3})$, where $n$ is the number of vertices.

Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space

from arXiv: Data Structures and Algorithms

Authors: Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild

We describe a simple variant of Hierholzer's algorithm that finds an Eulerian cycle in a (multi)graph with $n$ vertices and $m$ edges using $\mathrm{O}(n \lg m)$ bits of working memory. This substantially improves the working space compared to standard implementations of Hierholzer's algorithm, which use $\mathrm{O}(m \lg n)$ bits of space. Our algorithm runs in linear time, like the classical versions, but avoids an $\mathrm{O}(m)$-size stack of vertices or storing information for each edge. To our knowledge, this is the first linear-time algorithm to achieve this space bound, and the method is very easy to implement. The correctness argument, by contrast, is surprisingly subtle; we give a detailed formal proof. The space savings are particularly relevant for dense graphs or multigraphs with large edge multiplicities.

Authors: Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild

We describe a simple variant of Hierholzer's algorithm that finds an Eulerian cycle in a (multi)graph with $n$ vertices and $m$ edges using $\mathrm{O}(n \lg m)$ bits of working memory. This substantially improves the working space compared to standard implementations of Hierholzer's algorithm, which use $\mathrm{O}(m \lg n)$ bits of space. Our algorithm runs in linear time, like the classical versions, but avoids an $\mathrm{O}(m)$-size stack of vertices or storing information for each edge. To our knowledge, this is the first linear-time algorithm to achieve this space bound, and the method is very easy to implement. The correctness argument, by contrast, is surprisingly subtle; we give a detailed formal proof. The space savings are particularly relevant for dense graphs or multigraphs with large edge multiplicities.

Text Indexing and Pattern Matching with Ephemeral Edits

from arXiv: Data Structures and Algorithms

Authors: Solon P. Pissis

A sequence $e_0,e_1,\ldots$ of edit operations in a string $T$ is called ephemeral if operation $e_i$ constructing string $T^i$, for all $i=2k$ with $k\in\mathbb{N}$, is reverted by operation $e_{i+1}$ that reconstructs $T$. Such a sequence arises when processing a stream of independent edits or testing hypothetical edits. We introduce text indexing with ephemeral substring edits, a new version of text indexing. Our goal is to design a data structure over a given text that supports subsequent pattern matching queries with ephemeral substring insertions, deletions, or substitutions in the text; we require insertions and substitutions to be of constant length. In particular, we preprocess a text $T=T[0\mathinner{.\,.} n)$ over an integer alphabet $\Sigma=[0,\sigma)$ with $\sigma=n^{\mathcal{O}(1)}$ in $\mathcal{O}(n)$ time. Then, we can preprocess any arbitrary pattern $P=P[0\mathinner{.\,.} m)$ given online in $\mathcal{O}(m\log\log m)$ time and $\mathcal{O}(m)$ space and allow any ephemeral sequence of edit operations in $T$. Before reverting the $i$th operation, we report all Occ occurrences of $P$ in $T^i$ in $\mathcal{O}(\log\log n + \text{Occ})$ time. We also introduce pattern matching with ephemeral edits. In particular, we preprocess two strings $T$ and $P$, each of length at most $n$, over an integer alphabet $\Sigma=[0,\sigma)$ with $\sigma=n^{\mathcal{O}(1)}$ in $\mathcal{O}(n)$ time. Then, we allow any ephemeral sequence of edit operations in $T$. Before reverting the $i$th operation, we report all Occ occurrences of $P$ in $T^i$ in the optimal $\mathcal{O}(\text{Occ})$ time. Along our way to this result, we also give an optimal solution for pattern matching with ephemeral block deletions.

Authors: Solon P. Pissis

A sequence $e_0,e_1,\ldots$ of edit operations in a string $T$ is called ephemeral if operation $e_i$ constructing string $T^i$, for all $i=2k$ with $k\in\mathbb{N}$, is reverted by operation $e_{i+1}$ that reconstructs $T$. Such a sequence arises when processing a stream of independent edits or testing hypothetical edits. We introduce text indexing with ephemeral substring edits, a new version of text indexing. Our goal is to design a data structure over a given text that supports subsequent pattern matching queries with ephemeral substring insertions, deletions, or substitutions in the text; we require insertions and substitutions to be of constant length. In particular, we preprocess a text $T=T[0\mathinner{.\,.} n)$ over an integer alphabet $\Sigma=[0,\sigma)$ with $\sigma=n^{\mathcal{O}(1)}$ in $\mathcal{O}(n)$ time. Then, we can preprocess any arbitrary pattern $P=P[0\mathinner{.\,.} m)$ given online in $\mathcal{O}(m\log\log m)$ time and $\mathcal{O}(m)$ space and allow any ephemeral sequence of edit operations in $T$. Before reverting the $i$th operation, we report all Occ occurrences of $P$ in $T^i$ in $\mathcal{O}(\log\log n + \text{Occ})$ time. We also introduce pattern matching with ephemeral edits. In particular, we preprocess two strings $T$ and $P$, each of length at most $n$, over an integer alphabet $\Sigma=[0,\sigma)$ with $\sigma=n^{\mathcal{O}(1)}$ in $\mathcal{O}(n)$ time. Then, we allow any ephemeral sequence of edit operations in $T$. Before reverting the $i$th operation, we report all Occ occurrences of $P$ in $T^i$ in the optimal $\mathcal{O}(\text{Occ})$ time. Along our way to this result, we also give an optimal solution for pattern matching with ephemeral block deletions.

Necessity of Block Designs for Optimal Locally Private Distribution Estimation

from arXiv: Data Structures and Algorithms

Authors: Abigail Gentle

Local differential privacy represents the gold standard for preserving the privacy of data before it leaves the device, and distribution estimation under this model has been well studied. Recently, protocols built upon balanced incomplete block designs were shown to achieve optimal error for this problem. However, it remained unknown whether other constructions could also be optimal. We resolve this question by proving that any protocol achieving optimal error must correspond to some balanced incomplete block design. This result, combined with prior work, completely characterises the set of optimal protocols for this problem. As a consequence, the protocols that achieve optimal error and optimal communication are only those based on symmetrical balanced incomplete block designs.

Authors: Abigail Gentle

Local differential privacy represents the gold standard for preserving the privacy of data before it leaves the device, and distribution estimation under this model has been well studied. Recently, protocols built upon balanced incomplete block designs were shown to achieve optimal error for this problem. However, it remained unknown whether other constructions could also be optimal. We resolve this question by proving that any protocol achieving optimal error must correspond to some balanced incomplete block design. This result, combined with prior work, completely characterises the set of optimal protocols for this problem. As a consequence, the protocols that achieve optimal error and optimal communication are only those based on symmetrical balanced incomplete block designs.

Minimum-Weight Parity Factor Decoder for Quantum Error Correction

from arXiv: Data Structures and Algorithms

Authors: Yue Wu, Binghong Li, Kathleen Chang, Shruti Puri, Lin Zhong

Fast and accurate quantum error correction (QEC) decoding is crucial for scalable fault-tolerant quantum computation. Most-Likely-Error (MLE) decoding, while being near-optimal, is intractable on general quantum Low-Density Parity-Check (qLDPC) codes and typically relies on approximation and heuristics. We propose HyperBlossom, a unified framework that formulates MLE decoding as a Minimum-Weight Parity Factor (MWPF) problem and generalizes the blossom algorithm to hypergraphs via a similar primal-dual linear programming model with certifiable proximity bounds. HyperBlossom unifies all the existing graph-based decoders like (Hypergraph) Union-Find decoders and Minimum-Weight Perfect Matching (MWPM) decoder, thus bridging the gap between heuristic and certifying decoders. We implement HyperBlossom in software, namely Hyperion. Hyperion achieves a 4.8x lower logical error rate compared to the MWPM decoder on the distance-11 surface code and 1.6x lower logical error rate compared to a fine-tuned BPOSD decoder on the $[[90, 8, 10]]$ bivariate bicycle code under code-capacity noise. It also achieves an almost-linear average runtime scaling on both the surface code and the color code, with numerical results up to sufficiently large code distances of 99 and 31 for code-capacity noise and circuit-level noise, respectively.

Authors: Yue Wu, Binghong Li, Kathleen Chang, Shruti Puri, Lin Zhong

Fast and accurate quantum error correction (QEC) decoding is crucial for scalable fault-tolerant quantum computation. Most-Likely-Error (MLE) decoding, while being near-optimal, is intractable on general quantum Low-Density Parity-Check (qLDPC) codes and typically relies on approximation and heuristics. We propose HyperBlossom, a unified framework that formulates MLE decoding as a Minimum-Weight Parity Factor (MWPF) problem and generalizes the blossom algorithm to hypergraphs via a similar primal-dual linear programming model with certifiable proximity bounds. HyperBlossom unifies all the existing graph-based decoders like (Hypergraph) Union-Find decoders and Minimum-Weight Perfect Matching (MWPM) decoder, thus bridging the gap between heuristic and certifying decoders. We implement HyperBlossom in software, namely Hyperion. Hyperion achieves a 4.8x lower logical error rate compared to the MWPM decoder on the distance-11 surface code and 1.6x lower logical error rate compared to a fine-tuned BPOSD decoder on the $[[90, 8, 10]]$ bivariate bicycle code under code-capacity noise. It also achieves an almost-linear average runtime scaling on both the surface code and the color code, with numerical results up to sufficiently large code distances of 99 and 31 for code-capacity noise and circuit-level noise, respectively.

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths

from arXiv: Data Structures and Algorithms

Authors: Sunny Atalig, Marek Chrobak

In this note we examine the recent paper "Breaking the Bellman-Ford Shortest-Path Bound" by Amr Elmasry, where he presents an algorithm for the single-source shortest path problem and claims that its running time complexity is $\tilde{O}(m\sqrt{n})$, where $n$ is the number of vertices and $m$ is the number of edges. We show that his analysis is incorrect, by providing an example of a weighted graph on which the running time of his algorithm is $\Omega(mn)$.

Authors: Sunny Atalig, Marek Chrobak

In this note we examine the recent paper "Breaking the Bellman-Ford Shortest-Path Bound" by Amr Elmasry, where he presents an algorithm for the single-source shortest path problem and claims that its running time complexity is $\tilde{O}(m\sqrt{n})$, where $n$ is the number of vertices and $m$ is the number of edges. We show that his analysis is incorrect, by providing an example of a weighted graph on which the running time of his algorithm is $\Omega(mn)$.

Thursday, August 07

AI and ...

from Computational Complexity

AI and Vacation

I'm back from my German vacation. This was my first AI vacation, by which I mean how I used AI to navigate a foreign country. Taking a picture of a hand-written menu board, not just to translate the dishes, but to get a description of each. Visiting a palace with a German-speaking tour guide and translating in real time. Even the more mundane taking pictures of buildings to learn about them.

On the TV I saw something about Künstliche Intelligenz, and Chatty told me it was German for Artificial Intelligence. The Germans use KI instead of AI partly because AI can be confused with Ei (egg). At least that's what AI tells me, so it must be true.

AI and Math

At the beginning of my vacation, Google announced that they achieved gold medal status in the International Mathematical Olympiad. An impressive achievement though Terry Tao makes a good point that comparing an AI system to a time-constrained high-school students is not an apples-to-apples comparison.

I already find talking to AI about math topics quite useful, though it's like talking to an early PhD student. Sometimes they just say things that aren't correct, but usually they are. The reasoning models are particularly good at finding holes in P v NP proofs. For example here's the conclusion of ChatGPT o3-pro's review of the paper from Eric's guest post.

The paper is a reminder that lower‑bound proofs live or die on the exact breadth of the algorithmic model they exclude—too narrow and the result is unsurprising, too broad and the proof tends to break. At present this work sits in the first category.

What I want to see is AI come up with a solution to an open math problem, a true new insight beyond just some optimized search. I'm not looking for P ≠ NP, just some result that would be publishable in a respectable conference or journal, even just a new completeness result. We haven't really seen that yet, but I suspect we will soon and then we can figure out where math goes from there.

AI and Bill

In his presidents question and solution, Bill states that AI had failed to find the right answer to his problem. Back in June, I saw Bill's draft post and tried AI to solve it.

AI initially failed the test but for a good reason. Bill's initial draft post had Ford and Dole in Group Two because they received LLBs instead of JDs. In the past the LLB was the professional law degree. Yale didn't change to JD until 1971. Ford got his LLB from Yale in 1941.

When I removed Ford and Dole, ChatGPT o3-pro correctly gave the reason for the partition, though it did take over 13 minutes.

Every name in Group One spent time in a law school—most completed a J.D. or LL.B., and the two exceptions (Al Gore and, in some accounts, Lloyd Bentsen) still enrolled in law studies.

  • examples – Walter Mondale (University of Minnesota Law) en.wikipedia.org,
    JD Vance (Yale Law) en.wikipedia.org,
    Al Gore (attended Vanderbilt Law) en.wikipedia.org.

No one in Group Two ever attended a law school; their highest formal education is in fields such as engineering (Jimmy Carter), economics (George H. W. Bush), business (Donald Trump), political science (Paul Ryan), or acting (Ronald Reagan) en.wikipedia.orgen.wikipedia.org.

So the distinguishing property is legal education: every Group One figure went to law school, while none in Group Two did.

Another commentor got a similar result for ChatGPT o4-mini-high. I just tried it on Gemini 2.5-Pro and it also gave the correct response, this time in seconds.

On the other hand, E tried several base models and none of them succeeded. The lesson: You want to solve a tricky problem, pony up the $20/month and use a reasoning model.

By Lance Fortnow

AI and Vacation

I'm back from my German vacation. This was my first AI vacation, by which I mean how I used AI to navigate a foreign country. Taking a picture of a hand-written menu board, not just to translate the dishes, but to get a description of each. Visiting a palace with a German-speaking tour guide and translating in real time. Even the more mundane taking pictures of buildings to learn about them.

On the TV I saw something about Künstliche Intelligenz, and Chatty told me it was German for Artificial Intelligence. The Germans use KI instead of AI partly because AI can be confused with Ei (egg). At least that's what AI tells me, so it must be true.

AI and Math

At the beginning of my vacation, Google announced that they achieved gold medal status in the International Mathematical Olympiad. An impressive achievement though Terry Tao makes a good point that comparing an AI system to a time-constrained high-school students is not an apples-to-apples comparison.

I already find talking to AI about math topics quite useful, though it's like talking to an early PhD student. Sometimes they just say things that aren't correct, but usually they are. The reasoning models are particularly good at finding holes in P v NP proofs. For example here's the conclusion of ChatGPT o3-pro's review of the paper from Eric's guest post.

The paper is a reminder that lower‑bound proofs live or die on the exact breadth of the algorithmic model they exclude—too narrow and the result is unsurprising, too broad and the proof tends to break. At present this work sits in the first category.

What I want to see is AI come up with a solution to an open math problem, a true new insight beyond just some optimized search. I'm not looking for P ≠ NP, just some result that would be publishable in a respectable conference or journal, even just a new completeness result. We haven't really seen that yet, but I suspect we will soon and then we can figure out where math goes from there.

AI and Bill

In his presidents question and solution, Bill states that AI had failed to find the right answer to his problem. Back in June, I saw Bill's draft post and tried AI to solve it.

AI initially failed the test but for a good reason. Bill's initial draft post had Ford and Dole in Group Two because they received LLBs instead of JDs. In the past the LLB was the professional law degree. Yale didn't change to JD until 1971. Ford got his LLB from Yale in 1941.

When I removed Ford and Dole, ChatGPT o3-pro correctly gave the reason for the partition, though it did take over 13 minutes.

Every name in Group One spent time in a law school—most completed a J.D. or LL.B., and the two exceptions (Al Gore and, in some accounts, Lloyd Bentsen) still enrolled in law studies.

No one in Group Two ever attended a law school; their highest formal education is in fields such as engineering (Jimmy Carter), economics (George H. W. Bush), business (Donald Trump), political science (Paul Ryan), or acting (Ronald Reagan) en.wikipedia.orgen.wikipedia.org.

So the distinguishing property is legal education: every Group One figure went to law school, while none in Group Two did.

Another commentor got a similar result for ChatGPT o4-mini-high. I just tried it on Gemini 2.5-Pro and it also gave the correct response, this time in seconds.

On the other hand, E tried several base models and none of them succeeded. The lesson: You want to solve a tricky problem, pony up the $20/month and use a reasoning model.

By Lance Fortnow

What is Intelligence? From Reflection to Suffering

from Nisheeth Vishnoi

When intelligence turns inward, it creates the structure in which suffering can arise When Light Meets Mind In 1930, Berlin, two men sat across from each other. I’ve read the transcript more times than I can count. Not because it resolved anything, but because it kept echoing through my life. You had Albert Einstein: the […]

When intelligence turns inward, it creates the structure in which suffering can arise

When Light Meets Mind

In 1930, Berlin, two men sat across from each other. I’ve read the transcript more times than I can count. Not because it resolved anything, but because it kept echoing through my life.

You had Albert Einstein: the rationalist, the physicist. The man who redefined time, and connected matter and energy, gravity and spacetime. He saw the universe as vast, governed by elegant equations: something to be uncovered, mapped, and trusted.

And then Rabindranath Tagore: the poet, the mystic, the one who saw the inner world. But more than that, he believed that consciousness was not an afterthought in the cosmos. It was central. He wrote songs that became anthems, plays that folded myth into philosophy. His essays held reason and reverence in the same hand.

Where Einstein searched for equations and invariants, Tagore searched for meaning. He accepted science; he insisted that without awareness, it was incomplete. That the world, however beautiful, is only illuminated through the light of mind.

They spoke quietly, these two Nobel laureates, gently trying to name what is real.

Einstein put it plainly: “I believe in the external world, independent of the perceiving subject.”

Tagore’s response was just as clear: “The world is a human world; its reality is relative to our consciousness.”

On the surface, it sounded like a classic philosophical disagreement. But it felt like something more. As if two orientations, objective structure and lived experience, had paused long enough to listen, without declaring a winner.

I used to read that conversation purely as a question of truth: Is there a world independent of us, or is the world, at its core, ours?

But over time, it stopped feeling abstract. It began to weigh on me, in quiet ways I couldn’t always name.

There were losses, some that shook me more than I expected. And then the birth of my children cracked open a terrain I had not known was missing. Both experiences, in their own way, made me question how I had come to know the world, and what kind of knowledge mattered.

The structure I had spent years building, through science and mathematics, was solid. It gave me clarity. It gave me recognition. But it stopped short of certain truths I could now feel pressing in from the edges. Truths not about the world, but about the self that was trying to understand it.

And I began to notice something unsettling: the same intelligence that helped me understand the world could also make me feel lost within it. Not in the usual scientific way, where each answer opens new questions. That rhythm was familiar, even comforting. This was something different. A quieter unease. As if my way of knowing: analytical, recursive, and precise, had become part of the very trap.

I began to see a pattern: the mind’s ability to turn inward, to reflect on itself, could both elevate and entangle it. That reflection could open not just insight, but ache.

Tagore’s words, “The world is a human world”, started to echo differently. Not just as a metaphysical claim, but as a lived one. As a statement about what happens when consciousness turns in on itself. When intelligence doesn’t just observe the world, but begins to simulate its role within it. To model. To track. To reflect. And so I found myself asking: If intelligence brings light to the world, what happens when that light bends inward? What does it illuminate? And what does it burn?

This essay follows that question: tracing how recursive self-modeling, across biology, culture, and computation, opens the door not only to creativity and empathy, but to suffering. Along the way, I turn to contemplative traditions and computational framing to propose a deeper account: that suffering emerges when valuation becomes identity, when the mind tries to optimize a moving target that it has mistaken for itself.

Read the full essay by subscribing (for free) to The Intelligence Loop.

By nisheethvishnoi

Quantum circuit complexity and unsupervised machine learning of topological order

from arXiv: Computational Complexity

Authors: Yanming Che, Clemens Gneiting, Xiaoguang Wang, Franco Nori

Inspired by the close relationship between Kolmogorov complexity and unsupervised machine learning, we explore quantum circuit complexity, an important concept in quantum computation and quantum information science, as a pivot to understand and to build interpretable and efficient unsupervised machine learning for topological order in quantum many-body systems. To span a bridge from conceptual power to practical applicability, we present two theorems that connect Nielsen's quantum circuit complexity for the quantum path planning between two arbitrary quantum many-body states with fidelity change and entanglement generation, respectively. Leveraging these connections, fidelity-based and entanglement-based similarity measures or kernels, which are more practical for implementation, are formulated. Using the two proposed kernels, numerical experiments targeting the unsupervised clustering of quantum phases of the bond-alternating XXZ spin chain, the ground state of Kitaev's toric code and random product states, are conducted, demonstrating their superior performance. Relations with classical shadow tomography and shadow kernel learning are also discussed, where the latter can be naturally derived and understood from our approach. Our results establish connections between key concepts and tools of quantum circuit computation, quantum complexity, and machine learning of topological quantum order.

Authors: Yanming Che, Clemens Gneiting, Xiaoguang Wang, Franco Nori

Inspired by the close relationship between Kolmogorov complexity and unsupervised machine learning, we explore quantum circuit complexity, an important concept in quantum computation and quantum information science, as a pivot to understand and to build interpretable and efficient unsupervised machine learning for topological order in quantum many-body systems. To span a bridge from conceptual power to practical applicability, we present two theorems that connect Nielsen's quantum circuit complexity for the quantum path planning between two arbitrary quantum many-body states with fidelity change and entanglement generation, respectively. Leveraging these connections, fidelity-based and entanglement-based similarity measures or kernels, which are more practical for implementation, are formulated. Using the two proposed kernels, numerical experiments targeting the unsupervised clustering of quantum phases of the bond-alternating XXZ spin chain, the ground state of Kitaev's toric code and random product states, are conducted, demonstrating their superior performance. Relations with classical shadow tomography and shadow kernel learning are also discussed, where the latter can be naturally derived and understood from our approach. Our results establish connections between key concepts and tools of quantum circuit computation, quantum complexity, and machine learning of topological quantum order.

Square packing with $O(x^{0.6})$ wasted area

from arXiv: Computational Geometry

Authors: Hong Duc Bui

We show a new construction for square packing, and prove that it is more efficient than previous results.

Authors: Hong Duc Bui

We show a new construction for square packing, and prove that it is more efficient than previous results.

On existence of a compatible triangulation with the double circle order type

from arXiv: Computational Geometry

Authors: Hong Duc Bui

We show that the "double circle" order type and some of its generalizations have a compatible triangulation with any other order types with the same number of points and number of edges on convex hull, thus proving another special case of the conjecture in Aichholzer (2003).

Authors: Hong Duc Bui

We show that the "double circle" order type and some of its generalizations have a compatible triangulation with any other order types with the same number of points and number of edges on convex hull, thus proving another special case of the conjecture in Aichholzer (2003).

Polynomial-time sampling despite disorder chaos

from arXiv: Data Structures and Algorithms

Authors: Eric Ma, Tselil Schramm

A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out "stable" sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph $\boldsymbol{G} \sim G(n,1/2)$: (1) the hardcore model (at fugacity $\lambda = 1$) on $\boldsymbol{G}$ exhibits disorder chaos, and (2) Glauber dynamics run for $O(n)$ time can approximately sample from the hardcore model on $\boldsymbol{G}$ (in Wasserstein distance).

Authors: Eric Ma, Tselil Schramm

A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out "stable" sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph $\boldsymbol{G} \sim G(n,1/2)$: (1) the hardcore model (at fugacity $\lambda = 1$) on $\boldsymbol{G}$ exhibits disorder chaos, and (2) Glauber dynamics run for $O(n)$ time can approximately sample from the hardcore model on $\boldsymbol{G}$ (in Wasserstein distance).

A 60-Addition, Rank-23 Scheme for Exact 3x3 Matrix Multiplication

from arXiv: Data Structures and Algorithms

Authors: Joshua Stapleton

We reduce the additive cost of general (non-commutative) 3x3 matrix multiplication from the previous records of 61 (Schwartz-Vaknin, 2023) and 62 (Martensson-Wagner, 2025) to 60 without a change of basis. To our knowledge, this represents a new state-of-the-art.

Authors: Joshua Stapleton

We reduce the additive cost of general (non-commutative) 3x3 matrix multiplication from the previous records of 61 (Schwartz-Vaknin, 2023) and 62 (Martensson-Wagner, 2025) to 60 without a change of basis. To our knowledge, this represents a new state-of-the-art.

Approximation Algorithms for Scheduling Crowdsourcing Tasks in Mobile Social Networks

from arXiv: Data Structures and Algorithms

Authors: Chi-Yeh Chen

This paper addresses the scheduling problem in mobile social networks. We begin by proving that the approximation ratio analysis presented in the paper by Zhang \textit{et al.} (IEEE Transactions on Mobile Computing, 2025) is incorrect, and we provide the correct analysis results. Furthermore, when the required service time for a task exceeds the total contact time between the requester and the crowd worker, we demonstrate that the approximation ratio of the Largest-Ratio-First task scheduling algorithm can reach $2 - \frac{1}{m}$. Next, we introduce a randomized approximation algorithm to minimize mobile social networks' total weighted completion time. This algorithm achieves an expected approximation ratio of $1.5 + \epsilon$ for $\epsilon>0$. Finally, we present a deterministic approximation algorithm that minimizes mobile social networks' total weighted completion time. This deterministic algorithm achieves an approximation ratio of $\max\left\{2.5,1+\epsilon\right\}$ for $\epsilon>0$. Additionally, when the task's required service time or the total contact time between the requester and the crowd worker is sufficiently large, this algorithm can reach an approximation ratio of $1.5+\epsilon$ for $\epsilon>0$.

Authors: Chi-Yeh Chen

This paper addresses the scheduling problem in mobile social networks. We begin by proving that the approximation ratio analysis presented in the paper by Zhang \textit{et al.} (IEEE Transactions on Mobile Computing, 2025) is incorrect, and we provide the correct analysis results. Furthermore, when the required service time for a task exceeds the total contact time between the requester and the crowd worker, we demonstrate that the approximation ratio of the Largest-Ratio-First task scheduling algorithm can reach $2 - \frac{1}{m}$. Next, we introduce a randomized approximation algorithm to minimize mobile social networks' total weighted completion time. This algorithm achieves an expected approximation ratio of $1.5 + \epsilon$ for $\epsilon>0$. Finally, we present a deterministic approximation algorithm that minimizes mobile social networks' total weighted completion time. This deterministic algorithm achieves an approximation ratio of $\max\left\{2.5,1+\epsilon\right\}$ for $\epsilon>0$. Additionally, when the task's required service time or the total contact time between the requester and the crowd worker is sufficiently large, this algorithm can reach an approximation ratio of $1.5+\epsilon$ for $\epsilon>0$.

Exact Matching in Matrix Multiplication Time

from arXiv: Data Structures and Algorithms

Authors: Ryotaro Sato, Yutaro Yamaguchi

Initiated by Mulmuley, Vazirani, and Vazirani (1987), many algebraic algorithms have been developed for matching and related problems. In this paper, we review basic facts and discuss possible improvements with the aid of fast computation of the characteristic polynomial of a matrix. In particular, we show that the so-called exact matching problem can be solved with high probability in asymptotically the same time order as matrix multiplication. We also discuss its extension to the linear matroid parity problem.

Authors: Ryotaro Sato, Yutaro Yamaguchi

Initiated by Mulmuley, Vazirani, and Vazirani (1987), many algebraic algorithms have been developed for matching and related problems. In this paper, we review basic facts and discuss possible improvements with the aid of fast computation of the characteristic polynomial of a matrix. In particular, we show that the so-called exact matching problem can be solved with high probability in asymptotically the same time order as matrix multiplication. We also discuss its extension to the linear matroid parity problem.

Exactly simulating stochastic chemical reaction networks in sub-constant time per reaction

from arXiv: Data Structures and Algorithms

Authors: Joshua Petrack, David Doty

The model of chemical reaction networks is among the oldest and most widely studied and used in natural science. The model describes reactions among abstract chemical species, for instance $A + B \to C$, which indicates that if a molecule of type $A$ interacts with a molecule of type $B$ (the reactants), they may stick together to form a molecule of type $C$ (the product). The standard algorithm for simulating (discrete, stochastic) chemical reaction networks is the Gillespie algorithm [JPC 1977], which stochastically simulates one reaction at a time, so to simulate $\ell$ consecutive reactions, it requires total running time $\Omega(\ell)$. We give the first chemical reaction network stochastic simulation algorithm that can simulate $\ell$ reactions, provably preserving the exact stochastic dynamics (sampling from precisely the same distribution as the Gillespie algorithm), yet using time provably sublinear in $\ell$. Under reasonable assumptions, our algorithm can simulate $\ell$ reactions among $n$ total molecules in time $O(\ell/\sqrt n)$ when $\ell \ge n^{5/4}$, and in time $O(\ell/n^{2/5})$ when $n \le \ell \le n^{5/4}$. Our work adapts an algorithm of Berenbrink, Hammer, Kaaser, Meyer, Penschuck, and Tran [ESA 2020] for simulating the distributed computing model known as population protocols, extending it (in a very nontrivial way) to the more general chemical reaction network setting. We provide an implementation of our algorithm as a Python package, with the core logic implemented in Rust, with remarkably fast performance in practice.

Authors: Joshua Petrack, David Doty

The model of chemical reaction networks is among the oldest and most widely studied and used in natural science. The model describes reactions among abstract chemical species, for instance $A + B \to C$, which indicates that if a molecule of type $A$ interacts with a molecule of type $B$ (the reactants), they may stick together to form a molecule of type $C$ (the product). The standard algorithm for simulating (discrete, stochastic) chemical reaction networks is the Gillespie algorithm [JPC 1977], which stochastically simulates one reaction at a time, so to simulate $\ell$ consecutive reactions, it requires total running time $\Omega(\ell)$. We give the first chemical reaction network stochastic simulation algorithm that can simulate $\ell$ reactions, provably preserving the exact stochastic dynamics (sampling from precisely the same distribution as the Gillespie algorithm), yet using time provably sublinear in $\ell$. Under reasonable assumptions, our algorithm can simulate $\ell$ reactions among $n$ total molecules in time $O(\ell/\sqrt n)$ when $\ell \ge n^{5/4}$, and in time $O(\ell/n^{2/5})$ when $n \le \ell \le n^{5/4}$. Our work adapts an algorithm of Berenbrink, Hammer, Kaaser, Meyer, Penschuck, and Tran [ESA 2020] for simulating the distributed computing model known as population protocols, extending it (in a very nontrivial way) to the more general chemical reaction network setting. We provide an implementation of our algorithm as a Python package, with the core logic implemented in Rust, with remarkably fast performance in practice.

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk

from arXiv: Data Structures and Algorithms

Authors: Nikhil Bansal, Haotian Jiang

The Beck-Fiala Conjecture [Discrete Appl. Math, 1981] asserts that any set system of $n$ elements with degree $k$ has combinatorial discrepancy $O(\sqrt{k})$. A substantial generalization is the Koml\'os Conjecture, which states that any $m \times n$ matrix with unit length columns has discrepancy $O(1)$. In this work, we resolve the Beck-Fiala Conjecture for $k \geq \log^2 n$. We also give an $\widetilde{O}(\sqrt{k} + \sqrt{\log n})$ bound for $k \leq \log^2 n$, where $\widetilde{O}(\cdot)$ hides $\mathsf{poly}(\log \log n)$ factors. These bounds improve upon the $O(\sqrt{k \log n})$ bound due to Banaszczyk [Random Struct. Algor., 1998]. For the Komlos problem, we give an $\widetilde{O}(\log^{1/4} n)$ bound, improving upon the previous $O(\sqrt{\log n})$ bound [Random Struct. Algor., 1998]. All of our results also admit efficient polynomial-time algorithms. To obtain these results, we consider a new notion of affine spectral-independence in designing random walks. In particular, our algorithms obtain the desired colorings via a discrete Brownian motion, guided by a semidefinite program (SDP). Besides standard constraints used in prior works, we add some extra affine spectral-independence constraints, which effectively decouple the evolution of discrepancy across different rows, and allow us to better control how many rows accumulate large discrepancy at any point during the process. This technique of ``decoupling via affine spectral-independence'' is quite general and may be of independent interest.

Authors: Nikhil Bansal, Haotian Jiang

The Beck-Fiala Conjecture [Discrete Appl. Math, 1981] asserts that any set system of $n$ elements with degree $k$ has combinatorial discrepancy $O(\sqrt{k})$. A substantial generalization is the Koml\'os Conjecture, which states that any $m \times n$ matrix with unit length columns has discrepancy $O(1)$. In this work, we resolve the Beck-Fiala Conjecture for $k \geq \log^2 n$. We also give an $\widetilde{O}(\sqrt{k} + \sqrt{\log n})$ bound for $k \leq \log^2 n$, where $\widetilde{O}(\cdot)$ hides $\mathsf{poly}(\log \log n)$ factors. These bounds improve upon the $O(\sqrt{k \log n})$ bound due to Banaszczyk [Random Struct. Algor., 1998]. For the Komlos problem, we give an $\widetilde{O}(\log^{1/4} n)$ bound, improving upon the previous $O(\sqrt{\log n})$ bound [Random Struct. Algor., 1998]. All of our results also admit efficient polynomial-time algorithms. To obtain these results, we consider a new notion of affine spectral-independence in designing random walks. In particular, our algorithms obtain the desired colorings via a discrete Brownian motion, guided by a semidefinite program (SDP). Besides standard constraints used in prior works, we add some extra affine spectral-independence constraints, which effectively decouple the evolution of discrepancy across different rows, and allow us to better control how many rows accumulate large discrepancy at any point during the process. This technique of ``decoupling via affine spectral-independence'' is quite general and may be of independent interest.

Counting Distinct Square Substrings in Sublinear Time

from arXiv: Data Structures and Algorithms

Authors: Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba

We show that the number of distinct squares in a packed string of length $n$ over an alphabet of size $\sigma$ can be computed in $O(n/\log_\sigma n)$ time in the word-RAM model. This paper is the first to introduce a sublinear-time algorithm for counting squares in the packed setting. The packed representation of a string of length $n$ over an alphabet of size $\sigma$ is given as a sequence of $O(n/\log_\sigma n)$ machine words in the word-RAM model (a machine word consists of $\omega \ge \log_2 n$ bits). Previously, it was known how to count distinct squares in $O(n)$ time [Gusfield and Stoye, JCSS 2004], even for a string over an integer alphabet [Crochemore et al., TCS 2014; Bannai et al., CPM 2017; Charalampopoulos et al., SPIRE 2020]. We use the techniques for extracting squares from runs described by Crochemore et al. [TCS 2014]. However, the packed model requires novel approaches. We need an $O(n/\log_\sigma n)$-sized representation of all long-period runs (runs with period $\Omega(\log_\sigma n)$) which allows for a sublinear-time counting of the -- potentially linearly-many -- implied squares. The long-period runs with a string period that is periodic itself (called layer runs) are an obstacle, since their number can be $\Omega(n)$. The number of all other long-period runs is $O(n/\log_\sigma n)$ and we can construct an implicit representation of all long-period runs in $O(n/\log_\sigma n)$ time by leveraging the insights of Amir et al. [ESA 2019]. We count squares in layer runs by exploiting combinatorial properties of pyramidally-shaped groups of layer runs. Another difficulty lies in computing the locations of Lyndon roots of runs in packed strings, which is needed for grouping runs that may generate equal squares. To overcome this difficulty, we introduce sparse-Lyndon roots which are based on string synchronizers [Kempa and Kociumaka, STOC 2019].

Authors: Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba

We show that the number of distinct squares in a packed string of length $n$ over an alphabet of size $\sigma$ can be computed in $O(n/\log_\sigma n)$ time in the word-RAM model. This paper is the first to introduce a sublinear-time algorithm for counting squares in the packed setting. The packed representation of a string of length $n$ over an alphabet of size $\sigma$ is given as a sequence of $O(n/\log_\sigma n)$ machine words in the word-RAM model (a machine word consists of $\omega \ge \log_2 n$ bits). Previously, it was known how to count distinct squares in $O(n)$ time [Gusfield and Stoye, JCSS 2004], even for a string over an integer alphabet [Crochemore et al., TCS 2014; Bannai et al., CPM 2017; Charalampopoulos et al., SPIRE 2020]. We use the techniques for extracting squares from runs described by Crochemore et al. [TCS 2014]. However, the packed model requires novel approaches. We need an $O(n/\log_\sigma n)$-sized representation of all long-period runs (runs with period $\Omega(\log_\sigma n)$) which allows for a sublinear-time counting of the -- potentially linearly-many -- implied squares. The long-period runs with a string period that is periodic itself (called layer runs) are an obstacle, since their number can be $\Omega(n)$. The number of all other long-period runs is $O(n/\log_\sigma n)$ and we can construct an implicit representation of all long-period runs in $O(n/\log_\sigma n)$ time by leveraging the insights of Amir et al. [ESA 2019]. We count squares in layer runs by exploiting combinatorial properties of pyramidally-shaped groups of layer runs. Another difficulty lies in computing the locations of Lyndon roots of runs in packed strings, which is needed for grouping runs that may generate equal squares. To overcome this difficulty, we introduce sparse-Lyndon roots which are based on string synchronizers [Kempa and Kociumaka, STOC 2019].

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space

from arXiv: Data Structures and Algorithms

Authors: Thejas Radhika Sajith

Given a multiset $A = \{a_1, \dots, a_n\}$ of positive integers and a target integer $t$, the Subset Sum problem asks if there is a subset of $A$ that sums to $t$. Bellman's [1957] classical dynamic programming algorithm runs in $O(nt)$ time and $O(t)$ space. Since then, there have been multiple improvements in both time and space complexity. Notably, Bringmann [SODA 2017] uses a two-step color-coding technique to obtain a randomized algorithm that runs in $\tilde{O}(n+t)$ time and $\tilde{O}(t)$ space. On the other hand, there are polynomial space algorithms -- for example, Jin, Vyas and Williams [SODA 2021] build upon the algorithm given by Bringmann, using a clever algebraic trick first seen in Kane's Logspace algorithm, to obtain an $\tilde{O}(nt)$ time and $\tilde{O}(\log(nt))$ space algorithm. A natural question, asked by Jin et al. is if there is an $\tilde{O}(n+t)$ time algorithm running in poly$(n, \log t)$ space. Another natural question is whether it is possible to construct a deterministic polynomial space algorithm with time complexity comparable to that of Bellman's. In this paper, we answer both questions affirmatively. We build on the framework given by Jin et al., using a multipoint evaluation-based approach to speed up a bottleneck step in their algorithm. We construct a deterministic algorithm that runs in $\tilde{O}(nt)$ time and $\tilde{O}(n \log^2 t)$ space and a randomized algorithm that runs in $\tilde{O}(n+t)$ time and $\tilde{O}(n^2 + n \log^2 t)$ space.

Authors: Thejas Radhika Sajith

Given a multiset $A = \{a_1, \dots, a_n\}$ of positive integers and a target integer $t$, the Subset Sum problem asks if there is a subset of $A$ that sums to $t$. Bellman's [1957] classical dynamic programming algorithm runs in $O(nt)$ time and $O(t)$ space. Since then, there have been multiple improvements in both time and space complexity. Notably, Bringmann [SODA 2017] uses a two-step color-coding technique to obtain a randomized algorithm that runs in $\tilde{O}(n+t)$ time and $\tilde{O}(t)$ space. On the other hand, there are polynomial space algorithms -- for example, Jin, Vyas and Williams [SODA 2021] build upon the algorithm given by Bringmann, using a clever algebraic trick first seen in Kane's Logspace algorithm, to obtain an $\tilde{O}(nt)$ time and $\tilde{O}(\log(nt))$ space algorithm. A natural question, asked by Jin et al. is if there is an $\tilde{O}(n+t)$ time algorithm running in poly$(n, \log t)$ space. Another natural question is whether it is possible to construct a deterministic polynomial space algorithm with time complexity comparable to that of Bellman's. In this paper, we answer both questions affirmatively. We build on the framework given by Jin et al., using a multipoint evaluation-based approach to speed up a bottleneck step in their algorithm. We construct a deterministic algorithm that runs in $\tilde{O}(nt)$ time and $\tilde{O}(n \log^2 t)$ space and a randomized algorithm that runs in $\tilde{O}(n+t)$ time and $\tilde{O}(n^2 + n \log^2 t)$ space.

Wednesday, August 06

FOCS 2025: Students and Postdocs Travel Support

from CS Theory Events

December 14-17, 2025 Sydney, Australia focs.computer.org/2025/travel-support/ Submission deadline: September 19, 2025 Travel awards are intended for students and postdoctoral fellows. It will include a registration fee waiver, and, based on funding availability, accommodation for the duration of the conference. Members of underrepresented groups are particularly encouraged to apply for support.* * A portion of the … Continue reading FOCS 2025: Students and Postdocs Travel Support

By shacharlovett

December 14-17, 2025 Sydney, Australia https://focs.computer.org/2025/travel-support/ Submission deadline: September 19, 2025 Travel awards are intended for students and postdoctoral fellows. It will include a registration fee waiver, and, based on funding availability, accommodation for the duration of the conference. Members of underrepresented groups are particularly encouraged to apply for support.* * A portion of the … Continue reading FOCS 2025: Students and Postdocs Travel Support

By shacharlovett

FOCS 2025: Call for Workshops

from CS Theory Events

December 14-17, 2025 Sydney, Australia focs.computer.org/2025/call-for-workshops/ Submission deadline: September 5, 2025 The FOCS 2025 workshops provide an informal forum for researchers to discuss important research questions, directions, and challenges in the field. Workshops often serve the vital purpose of introducing researchers to new areas and agendas. We also encourage workshops focusing on connections between theoretical … Continue reading FOCS 2025: Call for Workshops

By shacharlovett

December 14-17, 2025 Sydney, Australia https://focs.computer.org/2025/call-for-workshops/ Submission deadline: September 5, 2025 The FOCS 2025 workshops provide an informal forum for researchers to discuss important research questions, directions, and challenges in the field. Workshops often serve the vital purpose of introducing researchers to new areas and agendas. We also encourage workshops focusing on connections between theoretical … Continue reading FOCS 2025: Call for Workshops

By shacharlovett

2-round BFT in Simplex style for n=5f-1

from Decentralized Thoughts

In our previous post, we described a 2-round partially synchronous BFT protocol for $n = 5f+1$. In this follow-up post, we push the bound to $n = 5f-1$, achieving optimal 2-round commit in the Simplex style. We then extend the result to $n=3f+2p-1$ for $0<p\leq f$ that obtains liveness for...

In our previous post, we described a 2-round partially synchronous BFT protocol for $n = 5f+1$. In this follow-up post, we push the bound to $n = 5f-1$, achieving optimal 2-round commit in the Simplex style. We then extend the result to $n=3f+2p-1$ for $0<p\leq f$ that obtains liveness for...

Thermodynamic Signature of Logical Depth in Quantum Circuits

from arXiv: Computational Complexity

Authors: Issam Ibnouhsein

We demonstrate that the internal logical structure of a quantum circuit can leave a distinct thermodynamic signature under progressive decoherence. By comparing deep, conditionally branching circuits with shallow, uniform counterparts-while controlling for overall halting probability and physical resources-we show that branching architectures induce greater entropy flow into the environment. This effect is captured by a logical depth factor $L_d$, which quantifies entropy accumulation during environmental interactions. We validate our framework through detailed analysis of two 4-branch quantum circuits, demonstrating greater entropy production with $L_d \approx 1.615$ for conditional versus uniform architectures. An ancilla-based experimental protocol using controlled-phase gates provides a concrete pathway for detecting these thermodynamic signatures on current quantum platforms. Our results establish logical depth as a physically measurable quantity with implications for circuit design, compilation strategies, and verification protocols.

Authors: Issam Ibnouhsein

We demonstrate that the internal logical structure of a quantum circuit can leave a distinct thermodynamic signature under progressive decoherence. By comparing deep, conditionally branching circuits with shallow, uniform counterparts-while controlling for overall halting probability and physical resources-we show that branching architectures induce greater entropy flow into the environment. This effect is captured by a logical depth factor $L_d$, which quantifies entropy accumulation during environmental interactions. We validate our framework through detailed analysis of two 4-branch quantum circuits, demonstrating greater entropy production with $L_d \approx 1.615$ for conditional versus uniform architectures. An ancilla-based experimental protocol using controlled-phase gates provides a concrete pathway for detecting these thermodynamic signatures on current quantum platforms. Our results establish logical depth as a physically measurable quantity with implications for circuit design, compilation strategies, and verification protocols.

When is String Reconstruction using de Bruijn Graphs Hard?

from arXiv: Data Structures and Algorithms

Authors: Ben Bals, Sebastiaan van Krieken, Solon P. Pissis, Leen Stougie, Hilde Verbeek

The reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly. This reduction employs the notion of de Bruijn graph $G=(V,E)$ of order $k$ over an alphabet $\Sigma$. A single Eulerian trail in $G$ represents a candidate genome reconstruction. Bernardini et al. have also introduced the complementary idea in data privacy [ALENEX 2020] based on $z$-anonymity. The pressing question is: How hard is it to reconstruct a best string from a de Bruijn graph given a function that models domain knowledge? Such a function maps every length-$k$ string to an interval of positions where it may occur in the reconstructed string. By the above reduction to de Bruijn graphs, the latter function translates into a function $c$ mapping every edge to an interval where it may occur in an Eulerian trail. This gives rise to the following basic problem on graphs: Given an instance $(G,c)$, can we efficiently compute an Eulerian trail respecting $c$? Hannenhalli et al.~[CABIOS 1996] formalized this problem and showed that it is NP-complete. We focus on parametrization aiming to capture the quality of our domain knowledge in the complexity. Ben-Dor et al. developed an algorithm to solve the problem on de Bruijn graphs in $O(m \cdot w^{1.5} 4^{w})$ time, where $m=|E|$ and $w$ is the maximum interval length over all edges. Bumpus and Meeks [Algorithmica 2023] rediscovered the same algorithm on temporal graphs, highlighting the relevance of this problem in other contexts. We give combinatorial insights that lead to exponential-time improvements over the state-of-the-art. For the important class of de Bruijn graphs, we develop an algorithm parametrized by $w (\log w+1) /(k-1)$. Our improved algorithm shows that it is enough when the range of positions is small relative to $k$.

Authors: Ben Bals, Sebastiaan van Krieken, Solon P. Pissis, Leen Stougie, Hilde Verbeek

The reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly. This reduction employs the notion of de Bruijn graph $G=(V,E)$ of order $k$ over an alphabet $\Sigma$. A single Eulerian trail in $G$ represents a candidate genome reconstruction. Bernardini et al. have also introduced the complementary idea in data privacy [ALENEX 2020] based on $z$-anonymity. The pressing question is: How hard is it to reconstruct a best string from a de Bruijn graph given a function that models domain knowledge? Such a function maps every length-$k$ string to an interval of positions where it may occur in the reconstructed string. By the above reduction to de Bruijn graphs, the latter function translates into a function $c$ mapping every edge to an interval where it may occur in an Eulerian trail. This gives rise to the following basic problem on graphs: Given an instance $(G,c)$, can we efficiently compute an Eulerian trail respecting $c$? Hannenhalli et al.~[CABIOS 1996] formalized this problem and showed that it is NP-complete. We focus on parametrization aiming to capture the quality of our domain knowledge in the complexity. Ben-Dor et al. developed an algorithm to solve the problem on de Bruijn graphs in $O(m \cdot w^{1.5} 4^{w})$ time, where $m=|E|$ and $w$ is the maximum interval length over all edges. Bumpus and Meeks [Algorithmica 2023] rediscovered the same algorithm on temporal graphs, highlighting the relevance of this problem in other contexts. We give combinatorial insights that lead to exponential-time improvements over the state-of-the-art. For the important class of de Bruijn graphs, we develop an algorithm parametrized by $w (\log w+1) /(k-1)$. Our improved algorithm shows that it is enough when the range of positions is small relative to $k$.

Coloring 3-Colorable Graphs with Low Threshold Rank

from arXiv: Data Structures and Algorithms

Authors: Jun-Ting Hsieh

We present a new algorithm for finding large independent sets in $3$-colorable graphs with small $1$-sided threshold rank. Specifically, given an $n$-vertex $3$-colorable graph whose uniform random walk matrix has at most $r$ eigenvalues larger than $\varepsilon$, our algorithm finds a proper $3$-coloring on at least $(\frac{1}{2}-O(\varepsilon))n$ vertices in time $n^{O(r/\varepsilon^2)}$. This extends and improves upon the result of Bafna, Hsieh, and Kothari on $1$-sided expanders. Furthermore, an independent work by Buhai, Hua, Steurer, and V\'ari-Kakas shows that it is UG-hard to properly $3$-color more than $(\frac{1}{2}+\varepsilon)n$ vertices, thus establishing the tightness of our result. Our proof is short and simple, relying on the observation that for any distribution over proper $3$-colorings, the correlation across an edge must be large if the marginals of the endpoints are not concentrated on any single color. Notably, this property fails for $4$-colorings, which is consistent with the hardness result of [BHK25] for $4$-colorable $1$-sided expanders.

Authors: Jun-Ting Hsieh

We present a new algorithm for finding large independent sets in $3$-colorable graphs with small $1$-sided threshold rank. Specifically, given an $n$-vertex $3$-colorable graph whose uniform random walk matrix has at most $r$ eigenvalues larger than $\varepsilon$, our algorithm finds a proper $3$-coloring on at least $(\frac{1}{2}-O(\varepsilon))n$ vertices in time $n^{O(r/\varepsilon^2)}$. This extends and improves upon the result of Bafna, Hsieh, and Kothari on $1$-sided expanders. Furthermore, an independent work by Buhai, Hua, Steurer, and V\'ari-Kakas shows that it is UG-hard to properly $3$-color more than $(\frac{1}{2}+\varepsilon)n$ vertices, thus establishing the tightness of our result. Our proof is short and simple, relying on the observation that for any distribution over proper $3$-colorings, the correlation across an edge must be large if the marginals of the endpoints are not concentrated on any single color. Notably, this property fails for $4$-colorings, which is consistent with the hardness result of [BHK25] for $4$-colorable $1$-sided expanders.

Finding Colorings in One-Sided Expanders

from arXiv: Data Structures and Algorithms

Authors: Rares-Darius Buhai, Yiding Hua, David Steurer, Andor Vári-Kakas

We establish new algorithmic guarantees with matching hardness results for coloring and independent set problems in one-sided expanders and related classes of graphs. For example, given a $3$-colorable regular one-sided expander, we compute in polynomial time either an independent set of relative size at least $1/2-o(1)$ or a proper $3$-coloring for all but an $o(1)$ fraction of the vertices, where $o(1)$ stands for a function that tends to $0$ with the second largest eigenvalue of the normalized adjacency matrix. This result improves on recent seminal work of Bafna, Hsieh, and Kothari (STOC 2025) developing an algorithm that efficiently finds independent sets of relative size at least $0.01$ in such graphs. We also obtain an efficient $1.6667$-factor approximation algorithm for VERTEX COVER in sufficiently strong regular one-sided expanders, improving over a previous $(2-\epsilon)$-factor approximation in such graphs for an unspecified constant $\epsilon>0$. We propose a new stratification of $k$-COLORING in terms of $k$-by-$k$ matrices akin to predicate sets for constraint satisfaction problems. We prove that whenever this matrix has repeated rows, the corresponding coloring problem is NP-hard for one-sided expanders under the Unique Games Conjecture. On the other hand, if this matrix has no repeated rows, our algorithms can solve the corresponding coloring problem on one-sided expanders in polynomial time. As starting point for our algorithmic results, we show a property of graph spectra that, to the best of our knowledge, has not been observed before: The number of negative eigenvalues smaller than $-\tau$ is at most $O(1/\tau^{2})$ times the number of eigenvalues larger than $\tau^{2}/2$. While this result allows us to bound the number of eigenvalues bounded away from $0$ in one-sided spectral expanders, this property alone is insufficient for our algorithmic results.

Authors: Rares-Darius Buhai, Yiding Hua, David Steurer, Andor Vári-Kakas

We establish new algorithmic guarantees with matching hardness results for coloring and independent set problems in one-sided expanders and related classes of graphs. For example, given a $3$-colorable regular one-sided expander, we compute in polynomial time either an independent set of relative size at least $1/2-o(1)$ or a proper $3$-coloring for all but an $o(1)$ fraction of the vertices, where $o(1)$ stands for a function that tends to $0$ with the second largest eigenvalue of the normalized adjacency matrix. This result improves on recent seminal work of Bafna, Hsieh, and Kothari (STOC 2025) developing an algorithm that efficiently finds independent sets of relative size at least $0.01$ in such graphs. We also obtain an efficient $1.6667$-factor approximation algorithm for VERTEX COVER in sufficiently strong regular one-sided expanders, improving over a previous $(2-\epsilon)$-factor approximation in such graphs for an unspecified constant $\epsilon>0$. We propose a new stratification of $k$-COLORING in terms of $k$-by-$k$ matrices akin to predicate sets for constraint satisfaction problems. We prove that whenever this matrix has repeated rows, the corresponding coloring problem is NP-hard for one-sided expanders under the Unique Games Conjecture. On the other hand, if this matrix has no repeated rows, our algorithms can solve the corresponding coloring problem on one-sided expanders in polynomial time. As starting point for our algorithmic results, we show a property of graph spectra that, to the best of our knowledge, has not been observed before: The number of negative eigenvalues smaller than $-\tau$ is at most $O(1/\tau^{2})$ times the number of eigenvalues larger than $\tau^{2}/2$. While this result allows us to bound the number of eigenvalues bounded away from $0$ in one-sided spectral expanders, this property alone is insufficient for our algorithmic results.

Tuesday, August 05

TR25-116 | Supercritical Tradeoff Between Size and Depth for Resolution over Parities | Dmitry Itsykson, Alexander Knop

from ECCC Papers

Alekseev and Itsykson (STOC 2025) proved the existence of an unsatisfiable CNF formula such that any resolution over parities (Res($\oplus$)) refutation must either have exponential size (in the formula size) or superlinear depth (in the number of variables). In this paper, we extend this result by constructing a formula with the same hardness properties, but which additionally admits a resolution refutation of quasi-polynomial size. This establishes a supercritical tradeoff between size and depth for resolution over parities. The proof builds on the framework of Alekseev and Itsykson and relies on a lifting argument applied to the supercritical tradeoff between width and depth in resolution, proposed by Buss and Thapen (IPL 2026).

Alekseev and Itsykson (STOC 2025) proved the existence of an unsatisfiable CNF formula such that any resolution over parities (Res($\oplus$)) refutation must either have exponential size (in the formula size) or superlinear depth (in the number of variables). In this paper, we extend this result by constructing a formula with the same hardness properties, but which additionally admits a resolution refutation of quasi-polynomial size. This establishes a supercritical tradeoff between size and depth for resolution over parities. The proof builds on the framework of Alekseev and Itsykson and relies on a lifting argument applied to the supercritical tradeoff between width and depth in resolution, proposed by Buss and Thapen (IPL 2026).

Full professorship (W3) at Saarland University (apply by September 18, 2025)

from CCI: jobs

We seek candidates with a strong research record in theoretical computer science, with a focus on algorithms, computational complexity, algorithmic game theory, algorithms engineering or related areas. There are numerous opportunities for collaborative research with other institutes on campus, in particular with the algorithms and complexity group of the Max-Planck Institute. Website: www.uni-saarland.de/fileadmin/upload/verwaltung/stellen/Wissenschaftler/W2672_Professorship__W3__in_Algorithms_and_Complexity.pdf Email: mblaeser@cs.uni-saarland.de

We seek candidates with a strong research record in theoretical computer science, with a focus on algorithms, computational complexity, algorithmic game theory, algorithms engineering or related areas. There are numerous opportunities for collaborative research with other institutes on campus, in particular with the algorithms and complexity group of the Max-Planck Institute.

Website: https://www.uni-saarland.de/fileadmin/upload/verwaltung/stellen/Wissenschaftler/W2672_Professorship__W3__in_Algorithms_and_Complexity.pdf
Email: mblaeser@cs.uni-saarland.de

By shacharlovett

ChatGPT and the Meaning of Life: Guest Post by Harvey Lederman

from Scott Aaronson

Scott Aaronson’s Brief Foreword: Harvey Lederman is a distinguished analytic philosopher who moved from Princeton to UT Austin a few years ago. Since his arrival, he’s become one of my best friends among the UT professoriate. He’s my favorite kind of philosopher, the kind who sees scientists as partners in discovering the truth, and also […]

Scott Aaronson’s Brief Foreword:

Harvey Lederman is a distinguished analytic philosopher who moved from Princeton to UT Austin a few years ago. Since his arrival, he’s become one of my best friends among the UT professoriate. He’s my favorite kind of philosopher, the kind who sees scientists as partners in discovering the truth, and also has a great sense of humor. He and I are both involved in UT’s new AI and Human Objectives Initiative (AHOI), which is supported by Open Philanthropy.

The other day, Harvey emailed me an eloquent meditation he wrote on what will be the meaning of life if AI doesn’t kill us all, but “merely” does everything we do better than we do it. While the question is of course now extremely familiar to me, Harvey’s erudition—bringing to bear everything from speculative fiction to the history of polar exploration—somehow brought the stakes home for me in a new way.

Harvey mentioned that he’d sent his essay to major magazines but hadn’t had success. So I said, why not a Shtetl-Optimized guest post? Harvey replied—what might be the highest praise this blog has ever received—well, that would be even better than the national magazine, as it would reach more relevant people.

And so without further ado, I present to you…


ChatGPT and the Meaning of Life, by Harvey Lederman

For the last two and a half years, since the release of ChatGPT, I’ve been suffering from fits of dread. It’s not every minute, or even every day, but maybe once a week, I’m hit by it—slackjawed, staring into the middle distance—frozen by the prospect that someday, maybe pretty soon, everyone will lose their job.

At first, I thought these slackjawed fits were just a phase, a passing thing. I’m a philosophy professor; staring into the middle distance isn’t exactly an unknown disease among my kind. But as the years have begun to pass, and the fits have not, I’ve begun to wonder if there’s something deeper to my dread. Does the coming automation of work foretell, as my fits seem to say, an irreparable loss of value in human life?

The titans of artificial intelligence tell us that there’s nothing to fear. Dario Amodei, CEO of Anthropic, the maker of Claude, suggests that: “historical hunter-gatherer societies might have imagined that life is meaningless without hunting,” and “that our well-fed technological society is devoid of purpose.” But of course, we don’t see our lives that way. Sam Altman, the CEO of OpenAI, sounds so similar, the text could have been written by ChatGPT. Even if the jobs of the future will look as “fake” to us as ours do to “a subsistence farmer”, Altman has “no doubt they will feel incredibly important and satisfying to the people doing them.”

Alongside these optimists, there are plenty of pessimists who, like me, are filled with dread. Pope Leo XIV has decried the threats AI poses to “human dignity, labor and justice”. Bill Gates has written about his fear, that “if we solved big problems like hunger and disease, and the world kept getting more peaceful: What purpose would humans have then?” And Douglas Hofstadter, the computer scientist and author of Gödel, Escher, Bach, has spoken eloquently of his terror and depression at “an oncoming tsunami that is going to catch all of humanity off guard.”

Who should we believe? The optimists with their bright visions of a world without work, or the pessimists who fear the end of a key source of meaning in human life?


I was brought up, maybe like you, to value hard work and achievement. In our house, scientists were heroes, and discoveries grand prizes of life. I was a diligent, obedient kid, and eagerly imbibed what I was taught. I came to feel that one way a person’s life could go well was to make a discovery, to figure something out.

I had the sense already then that geographical discovery was played out. I loved the heroes of the great Polar Age, but I saw them—especially Roald Amundsen and Robert Falcon Scott—as the last of their kind. In December 1911, Amundsen reached the South Pole using skis and dogsleds. Scott reached it a month later, in January 1912, after ditching the motorized sleds he’d hoped would help, and man-hauling the rest of the way. As the black dot of Amundsen’s flag came into view on the ice, Scott was devastated to reach this “awful place”, “without the reward of priority”. He would never make it back.

Scott’s motors failed him, but they spelled the end of the great Polar Age. Even Amundsen took to motors on his return: in 1924, he made a failed attempt for the North Pole in a plane, and, in 1926, he successfully flew over it, in a dirigible. Already by then, the skis and dogsleds of the decade before were outdated heroics of a bygone world.

We may be living now in a similar twilight age for human exploration in the realm of ideas. Akshay Venkatesh, whose discoveries earned him the 2018 Fields Medal, mathematics’ highest honor, has written that, the “mechanization of our cognitive processes will alter our understanding of what mathematics is”. Terry Tao, a 2006 Fields Medalist, expects that in just two years AI will be a copilot for working mathematicians. He envisions a future where thousands of theorems are proven all at once by mechanized minds.

Now, I don’t know any more than the next person where our current technology is headed, or how fast. The core of my dread isn’t based on the idea that human redundancy will come in two years rather than twenty, or, for that matter, two hundred. It’s a more abstract dread, if that’s a thing, dread about what it would mean for human values, or anyway my values, if automation “succeeds”: if all mathematics—and, indeed all work—is done by motor, not by human hands and brains.

A world like that wouldn’t be good news for my childhood dreams. Venkatesh and Tao, like Amundsen and Scott, live meaningful lives, lives of purpose. But worthwhile discoveries like theirs are a scarce resource. A territory, once seen, can’t be seen first again. If mechanized minds consume all the empty space on the intellectual map, lives dedicated to discovery won’t be lives that humans can lead.

The right kind of pessimist sees here an important argument for dread. If discovery is valuable in its own right, the loss of discovery could be an irreparable loss for humankind.

A part of me would like this to be true. But over these last strange years, I’ve come to think it’s not. What matters, I now think, isn’t being the first to figure something out, but the consequences of the discovery: the joy the discoverer gets, the understanding itself, or the real life problem their knowledge solves. Alexander Fleming discovered penicillin, and through that work saved thousands, perhaps millions of lives. But if it were to emerge, in the annals of an outlandish future, that an alien discovered penicillin thousands of years before Fleming did, we wouldn’t think that Fleming’s life was worse, just because he wasn’t first. He eliminated great suffering from human life; the alien discoverer, if they’re out there, did not. So, I’ve come to see, it’s not discoveries themselves that matter. It’s what they bring about.


But the advance of automation would mean the end of much more than human discovery. It could mean the end of all necessary work. Already in 1920, the Czech playwright Karel Capek asked what a world like that would mean for the values in human life. In the first act of R.U.R.—the play which introduced the modern use of the word “robot”—Capek has Henry Domin, the manager of Rossum’s Universal Robots (the R.U.R. of the title), offer his corporation’s utopian pitch. “In ten years”, he says, their robots will “produce so much corn, so much cloth, so much everything” that “There will be no poverty.” “Everybody will be free from worry and liberated from the degradation of labor.” The company’s engineer, Alquist, isn’t convinced. Alquist (who, incidentally, ten years later, will be the only human living, when the robots have killed the rest) retorts that “There was something good in service and something great in humility”, “some kind of virtue in toil and weariness”.

Service—work that meets others’ significant needs and wants— is, unlike discovery, clearly good in and of itself. However we work— as nurses, doctors, teachers, therapists, ministers, lawyers, bankers, or, really, anything at all—working to meet others’ needs makes our own lives go well. But, as Capek saw, all such work could disappear. In a “post-instrumental” world, where people are comparatively useless and the bots meet all our important needs, there would be no needed work for us to do, no suffering to eliminate, no diseases to cure. Could the end of such work be a better reason for dread?

The hardline pessimists say that it is. They say that the end all needed work would not only be a loss of some value to humanity, as everyone should agree. For them it would be a loss to humanity on balance, an overall loss, that couldn’t be compensated in another way.

I feel a lot of pull to this pessimistic thought. But once again, I’ve come to think it’s wrong. For one thing, pessimists often overlook just how bad most work actually is. In May 2021, Luo Huazhang, a 31 year-old ex-factory worker in Sichuan wrote a viral post, entitled “Lying Flat is Justice”. Luo had searched at length for a job that, unlike his factory job, would allow him time for himself, but he couldn’t find one. So he quit, biked to Tibet and back, and commenced his lifestyle of lying flat, doing what he pleased, reading philosophy, contemplating the world. The idea struck a chord with overworked young Chinese, who, it emerged, did not find “something great” in their “humility”. The movement inspired memes, selfies flat on one’s back, and even an anthem.

That same year, as the Great Resignation in the United States took off, the subreddit r/antiwork played to similar discontent. Started in 2013, under the motto “Unemployment for all, not only the rich!”, the forum went viral in 2021, starting with a screenshot of a quitting worker’s texts to his supervisor (“No thanks. Have a good life”), and culminating in labor-actions, first supporting striking workers at Kelloggs by spamming their job application site, and then attempting to support a similar strike at McDonald’s. It wasn’t just young Chinese who hated their jobs.

In Automation and Utopia: Human Flourishing in a World without Work, the Irish lawyer and philosopher John Danaher imagines an antiwork techno-utopia, with plenty of room for lying flat. As Danaher puts it: “Work is bad for most people most of the time.”“We should do what we can to hasten the obsolescence of humans in the arena of work.”

The young Karl Marx would have seen both Domin’s and Danaher’s utopias as a catastrophe for human life. In his notebooks from 1844, Marx describes an ornate and almost epic process, where, by meeting the needs of others through production, we come to recognize the other in ourselves, and through that recognition, come at last to self-consciousness, the full actualization of our human nature. The end of needed work, for the Marx of these notes, would be the impossibility of fully realizing our nature, the end, in a way, of humanity itself.

But such pessimistic lamentations have come to seem to me no more than misplaced machismo. Sure, Marx’s and my culture, the ethos of our post-industrial professional class, might make us regret a world without work. But we shouldn’t confuse the way two philosophers were brought up with the fundamental values of human life. What stranger narcissism could there be than bemoaning the end of others’ suffering, disease, and need, just because it deprives you of the chance to be a hero?


The first summer after the release of ChatGPT—the first summer of my fits of dread—I stayed with my in-laws in Val Camonica, a valley in the Italian alps. The houses in their village, Sellero, are empty and getting emptier; the people on the streets are old and getting older. The kids that are left—my wife’s elementary school class had, even then, a full complement of four—often leave for better lives. But my in-laws are connected to this place, to the houses and streets where they grew up. They see the changes too, of course. On the mountains above, the Adamello, Italy’s largest glacier, is retreating faster every year. But while the shows on Netflix change, the same mushrooms appear in the summer, and the same chestnuts are collected in the fall.

Walking in the mountains of Val Camonica that summer, I tried to find parallels for my sense of impending loss. I thought about William Shanks, a British mathematician who calculated π to 707 digits by hand in 1873 (he made a mistake at 527; almost 200 digits were wrong). He later spent years of his life, literally years, on a table of the reciprocals of the primes up to one-hundred and ten thousand, calculating in the morning by hand, and checking it over in the afternoon. That was his life’s work. Just sixty years after his death, though, already in the 1940s, the table on which his precious mornings were spent, the few mornings he had on this earth, could be made by a machine in a day.

I feel sad thinking about Shanks, but I don’t feel grief for the loss of calculation by hand. The invention of the typewriter, and the death of handwritten notes seemed closer to the loss I imagined we might feel. Handwriting was once a part of your style, a part of who you were. With its decline some artistry, a deep and personal form of expression, may be lost. When the bots help with everything we write, couldn’t we too lose our style and voice?

But more than anything I thought of what I saw around me: the slow death of the dialects of Val Camonica and the culture they express. Chestnuts were at one time so important for nutrition here, that in the village of Paspardo, a street lined with chestnut trees is called “bread street” (“Via del Pane”). The hyper-local dialects of the valley, outgrowths sometimes of a single family’s inside jokes, have words for all the phases of the chestnut. There’s a porridge made from chestnut flour that, in Sellero goes by ‘skelt’, but is ‘pult’ in Paspardo, a cousin of ‘migole’ in Malonno, just a few villages away. Boiled, chestnuts are tetighe; dried on a grat, biline or bascocc, which, seasoned and boiled become broalade. The dialects don’t just record what people eat and ate; they recall how they lived, what they saw, and where they went. Behind Sellero, every hundred-yard stretch of the walk up to the cabins where the cows were taken to graze in summer, has its own name. Aiva Codaola. Quarsanac. Coran. Spi. Ruc.

But the young people don’t speak the dialect anymore. They go up to the cabins by car, too fast to name the places along the way. They can’t remember a time when the cows were taken up to graze. Some even buy chestnuts in the store.

Grief, you don’t need me to tell you, is a complicated beast. You can grieve for something even when you know that, on balance, it’s good that it’s gone. The death of these dialects, of the stories told on summer nights in the mountains with the cows, is a loss reasonably grieved. But you don’t hear the kids wishing more people would be forced to stay or speak this funny-sounding tongue. You don’t even hear the old folks wishing they could go back fifty years—in those days it wasn’t so easy to be sure of a meal. For many, it’s better this way, not the best it could be, but still better, even as they grieve what they stand to lose and what they’ve already lost.

The grief I feel, imagining a world without needed work, seems closest to this kind of loss. A future without work could be much better than ours, overall. But, living in that world, or watching as our old ways passed away, we might still reasonably grieve the loss of the work that once was part of who we were.


In the last chapter of Edith Wharton’s Age of Innocence, Newland Archer contemplates a world that has changed dramatically since, thirty years earlier, before these new fangled telephones and five-day trans-Atlantic ships, he renounced the love of his life. Awaiting a meeting that his free-minded son Dallas has organized with Ellen Olenska, the woman Newland once loved, he wonders whether his son, and this whole new age, can really love the way he did and does. How could their hearts beat like his, when they’re always so sure of getting what they want?

There have always been things to grieve about getting old. But modern technology has given us new ways of coming to be out of date. A generation born in 1910 did their laundry in Sellero’s public fountains. They watched their grandkids grow up with washing machines at home. As kids, my in-laws worked with their families to dry the hay by hand. They now know, abstractly, that it can all be done by machine. Alongside newfound health and ease, these changes brought, as well, a mix of bitterness and grief: grief for the loss of gossip at the fountains or picnics while bringing in the hay; and also bitterness, because the kids these days just have no idea how easy they have it now.

As I look forward to the glories that, if the world doesn’t end, my grandkids might enjoy, I too feel prospective bitterness and prospective grief. There’s grief, in advance, for what we now have that they’ll have lost: the formal manners of my grandparents they’ll never know, the cars they’ll never learn to drive, and the glaciers that will be long gone before they’re born. But I also feel bitter about what we’ve been through that they won’t have to endure: small things like folding the laundry, standing in security lines or taking out the trash, but big ones too—the diseases which will take our loved ones that they’ll know how to cure.

All this is a normal part of getting old in the modern world. But the changes we see could be much faster and grander in scale. Amodei of Anthropic speculates that a century of technological change could be compressed into the next decade, or less. Perhaps it’s just hype, but—what if it’s not? It’s one thing for a person to adjust, over a full life, to the washing machine, the dishwasher, the air-conditioner, one by one. It’s another, in five years, to experience the progress of a century. Will I see a day when childbirth is a thing of the past? What about sleep? Will our ‘descendants’ have bodies at all?

And this round of automation could also lead to unemployment unlike any our grandparents saw. Worse, those of us working now might be especially vulnerable to this loss. Our culture, or anyway mine—professional America of the early 21st century—has apotheosized work, turning it into a central part of who we are. Where others have a sense of place—their particular mountains and trees—we’ve come to locate ourselves with professional attainment, with particular degrees and jobs. For us, ‘workists’ that so many of us have become, technological displacement wouldn’t just be the loss of our jobs. It would be the loss of a central way we have of making sense of our lives.

None of this will be a problem for the new generation, for our kids. They’ll know how to live in a world that could be—if things go well—far better overall. But I don’t know if I’d be able to adapt. Intellectual argument, however strong, is weak against the habits of years. I fear they’d look at me, stuck in my old ways, with the same uncomprehending look that Dallas Archer gives his dad, when Newland announces that he won’t go see Ellen Olenska, the love of his life, after all. “Say”, as Newland tries to explain to his dumbfounded son, “that I’m old fashioned, that’s enough.”


And yet, the core of my dread is not about aging out of work before my time. I feel closest to Douglas Hofstadter, the author of Gödel, Escher, Bach. His dread, like mine, isn’t only about the loss of work today, or the possibility that we’ll be killed off by the bots. He fears that even a gentle superintelligence will be “as incomprehensible to us as we are to cockroaches.”

Today, I feel part of our grand human projects—the advancement of knowledge, the creation of art, the effort to make the world a better place. I’m not in any way a star player on the team. My own work is off in a little backwater of human thought. And I can’t understand all the details of the big moves by the real stars. But even so, I understand enough of our collective work to feel, in some small way, part of our joint effort. All that will change. If I were to be transported to the brilliant future of the bots, I wouldn’t understand them or their work enough to feel part of the grand projects of their day. Their work would have become, to me, as alien as ours is to a roach.


But I’m still persuaded that the hardline pessimists are wrong. Work is far from the most important value in our lives. A post-instrumental world could be full of much more important goods— from rich love of family and friends, to new undreamt of works of art—which would more than compensate the loss of value from the loss of our work.

Of course, even the values that do persist may be transformed in almost unrecognizable ways. In Deep Utopia: Life and Meaning in a Solved World, the futurist and philosopher Nick Bostrom imagines how things might look. In one of the most memorable sections of the book—right up there with an epistolary novella about the exploits of Pignolius the pig (no joke!)—Bostrom says that even child-rearing may be something that we, if we love our children, would come to forego. In a truly post-instrumental world, a robot intelligence could do better for your child, not only in teaching the child to read, but also in showing unbreakable patience and care. If you’ll snap at your kid, when the robot would not, it would only be selfishness for you to get in the way.

It’s a hard question whether Bostrom is right. At least some of the work of care isn’t like eliminating suffering or ending mortal disease. The needs or wants are small-scale stuff, and the value we get from helping each other might well outweigh the fact that we’d do it worse than a robot could.

But even supposing Bostrom is right about his version of things, and we wouldn’t express our love by changing diapers, we could still love each other. And together with our loved ones and friends, we’d have great wonders to enjoy. Wharton has Newland Archer wonder at five-day transatlantic ships. But what about five day journeys to Mars? These days, it’s a big deal if you see the view from Everest with your own eyes. But Olympus Mons on Mars is more than twice as tall.

And it’s not just geographical tourism that could have a far expanded range. There’d be new journeys of the spirit as well. No humans would be among the great writers or sculptors of the day, but the fabulous works of art a superintelligence could make could help to fill our lives. Really, for almost any aesthetic value you now enjoy—sentimental or austere, minute or magnificent, meaningful or jocular—the bots would do it much better than we have ever done.

Humans could still have meaningful projects, too. In 1976, about a decade before any of Altman, Amodei or even I were born, the Canadian philosopher Bernhard Suits argued that “voluntary attempts to overcome unnecessary obstacles” could give people a sense of purpose in a post-instrumental world. Suits calls these “games”, but the name is misleading; I prefer “artificial projects”. The projects include things we would call games like chess, checkers and bridge, but also things we wouldn’t think of as games at all, like Amundsen’s and Scott’s exploits to the Pole. Whatever we call them, Suits—who’s followed here explicitly by Danaher, the antiwork utopian and, implicitly, by Altman and Amodei—is surely right: even as things are now, we get a lot of value from projects we choose, whether or not they meet a need. We learn to play a piece on the piano, train to run a marathon, or even fly to Antartica to “ski the last degree” to the Pole. Why couldn’t projects like these become the backbone of purpose in our lives?

And we could have one real purpose, beyond the artificial ones, as well. There is at least one job that no machine can take away: the work of self-fashioning, the task of becoming and being ourselves. There’s an aesthetic accomplishment in creating your character, an artistry of choice and chance in making yourself who you are. This personal style includes not just wardrobe or tattoos, not just your choice of silverware or car, but your whole way of being, your brand of patience, modesty, humor, rage, hobbies and tastes. Creating this work of art could give some of us something more to live for.


Would a world like that leave any space for human intellectual achievement, the stuff of my childhood dreams? The Buddhist Pali Canon says that “All conditioned things are impermanent—when one sees this with wisdom, one turns away from suffering.” Apparently, in this text, the intellectual achievement of understanding gives us a path out of suffering. To arrive at this goal, you don’t have to be the first to plant your flag on what you’ve understood; you just have to get there.

A secular version of this idea might hold, more simply, that some knowledge or understanding is good in itself. Maybe understanding the mechanics of penicillin matters mainly because of what it enabled Fleming and others to do. But understanding truths about the nature of our existence, or even mathematics, could be different. That sort of understanding plausibly is good in its own right, even if someone or something has gotten there first.

Venkatesh the Fields Medalist seems to suggest something like this for the future of math. Perhaps we’ll change our understanding of the discipline, so that it’s not about getting the answers, but instead about human understanding, the artistry of it perhaps, or the miracle of the special kind of certainty that proof provides.

Philosophy, my subject, might seem an even more promising place for this idea. For some, philosophy is a “way of life”. The aim isn’t necessarily an answer, but constant self-examination for its own sake. If that’s the point, then in the new world of lying flat, there could be a lot of philosophy to do.

I don’t myself accept this way of seeing things. For me, philosophy aims at the truth as much as physics does. But I of course agree that there are some truths that it’s good for us to understand, whether or not we get there first. And there could be other parts of philosophy that survive for us, as well. We need to weigh the arguments for ourselves, and make up our own minds, even if the work of finding new arguments comes to belong to a machine.

I’m willing to believe, and even hope that future people will pursue knowledge and understanding in this way. But I don’t find, here, much consolation for my personal grief. I was trained to produce knowledge, not merely to acquire it. In the hours when I’m not teaching or preparing to teach, my job is to discover the truth. The values I imbibed—and I told you I was an obedient kid—held that the prize goes for priority.

Thinking of this world where all we learn is what the bots have discovered first, I feel sympathy with Lee Sedol, the champion Go player who retired after his defeat by Google’s AlphaZero in 2016. For him, losing to AI “in a sense, meant my entire world was collapsing”. “Even if I become the number one, there is an entity that cannot be defeated.” Right or wrong, I would feel the same about my work, in a world with an automated philosophical champ.

But Sedol and I are likely just out of date models, with values that a future culture will rightly revise. It’s been more than twenty years since Garry Kasparov lost to IBM’s Deep Blue, but chess has never been more popular. And this doesn’t seem some new-fangled twist of the internet age. I know of no human who quit the high-jump after the invention of mechanical flight. The Greeks sprinted in their Olympics, though they had, long before, domesticated the horse. Maybe we too will come to value the sport of understanding with our own brains.


Frankenstein, Mary Shelley’s 1818 classic of the creations-kill-creator genre, begins with an expedition to the North Pole. Robert Walton hopes to put himself in the annals of science and claim the Pole for England, when he comes upon Victor Frankenstein, floating in the Arctic Sea. It’s only once Frankenstein warms up, that we get into the story everyone knows. Victor hopes he can persuade Walton to turn around, by describing how his own quest for knowledge and glory went south.

Frankenstein doesn’t offer Walton an alternative way of life, a guide for living without grand goals. And I doubt Walton would have been any more personally consoled by the glories of a post-instrumental future than I am. I ended up a philosopher, but I was raised by parents who, maybe like yours, hoped for doctors or lawyers. They saw our purpose in answering real needs, in, as they’d say, contributing to society. Lives devoted to families and friends, fantastic art and games could fill a wondrous future, a world far better than it has ever been. But those aren’t lives that Walton or I, or our parents for that matter, would know how to be proud of. It’s just not the way we were brought up.

For the moment, of course, we’re not exactly short on things to do. The world is full of grisly suffering, sickness, starvation, violence, and need. Frankenstein is often remembered with the moral that thirst for knowledge brings ruination, that scientific curiosity killed the cat. But Victor Frankenstein makes a lot of mistakes other than making his monster. His revulsion at his creation persistently prevents him, almost inexplicably, from feeling the love or just plain empathy that any father should. On top of all we have to do to help each other, we have a lot of work to do, in engineering as much as empathy, if we hope to avoid Frankenstein’s fate.

But even with these tasks before us, my fits of dread are here to stay. I know that the post-instrumental world could be a much better place. But its coming means the death of my culture, the end of my way of life. My fear and grief about this loss won’t disappear because of some choice consolatory words. But I know how to relish the twilight too. I feel lucky to live in a time where people have something to do, and the exploits around me seem more poignant, and more beautiful, in the dusk. We may be some of the last to enjoy this brief spell, before all exploration, all discovery, is done by fully automated sleds.

By Scott

Forrelation is Extremally Hard

from arXiv: Computational Complexity

Authors: Uma Girish, Rocco Servedio

The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to $n$-bit Boolean functions $f$ and $g$, the goal is to estimate the Forrelation function $\mathrm{forr}(f,g)$, which measures the correlation between $g$ and the Fourier transform of $f$. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely $(f,g)$ with $\mathrm{forr}(f,g)=1$ and $\mathrm{forr}(f,g)=-1$. We show that this problem can be solved with one quantum query and success probability one, yet requires $\tilde{\Omega}\left(2^{n/4}\right)$ classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs $f,g$ are computable by small classical circuits and show classical hardness under cryptographic assumptions.

Authors: Uma Girish, Rocco Servedio

The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to $n$-bit Boolean functions $f$ and $g$, the goal is to estimate the Forrelation function $\mathrm{forr}(f,g)$, which measures the correlation between $g$ and the Fourier transform of $f$. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely $(f,g)$ with $\mathrm{forr}(f,g)=1$ and $\mathrm{forr}(f,g)=-1$. We show that this problem can be solved with one quantum query and success probability one, yet requires $\tilde{\Omega}\left(2^{n/4}\right)$ classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs $f,g$ are computable by small classical circuits and show classical hardness under cryptographic assumptions.

Proof of Hiding Conjecture in Gaussian Boson Sampling

from arXiv: Computational Complexity

Authors: Laura Shou, Sarah H. Miller, Victor Galitski

Gaussian boson sampling (GBS) is a promising protocol for demonstrating quantum computational advantage. One of the key steps for proving classical hardness of GBS is the so-called ``hiding conjecture'', which asserts that one can ``hide'' a complex Gaussian matrix as a submatrix of the outer product of Haar unitary submatrices in total variation distance. In this paper, we prove the hiding conjecture for input states with the maximal number of squeezed states, which is a setup that has recently been realized experimentally [Madsen et al., Nature 606, 75 (2022)]. In this setting, the hiding conjecture states that a $o(\sqrt{M})\times o(\sqrt{M})$ submatrix of an $M\times M$ circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex Gaussian matrix in total variation distance as $M\to\infty$. This is the first rigorous proof of the hiding property for GBS in the experimentally relevant regime, and puts the argument for hardness of classically simulating GBS with a maximal number of squeezed states on a comparable level to that of the conventional boson sampling of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)].

Authors: Laura Shou, Sarah H. Miller, Victor Galitski

Gaussian boson sampling (GBS) is a promising protocol for demonstrating quantum computational advantage. One of the key steps for proving classical hardness of GBS is the so-called ``hiding conjecture'', which asserts that one can ``hide'' a complex Gaussian matrix as a submatrix of the outer product of Haar unitary submatrices in total variation distance. In this paper, we prove the hiding conjecture for input states with the maximal number of squeezed states, which is a setup that has recently been realized experimentally [Madsen et al., Nature 606, 75 (2022)]. In this setting, the hiding conjecture states that a $o(\sqrt{M})\times o(\sqrt{M})$ submatrix of an $M\times M$ circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex Gaussian matrix in total variation distance as $M\to\infty$. This is the first rigorous proof of the hiding property for GBS in the experimentally relevant regime, and puts the argument for hardness of classically simulating GBS with a maximal number of squeezed states on a comparable level to that of the conventional boson sampling of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)].

Categorizing Merge Tree Edit Distances by Stability using Minimal Vertex Perturbation

from arXiv: Computational Geometry

Authors: Florian Wetzels, Christoph Garth

This paper introduces a novel stability measure for edit distances between merge trees of piecewise linear scalar fields. We apply the new measure to various metrics introduced recently in the field of scalar field comparison in scientific visualization. While previous stability measures are unable to capture the fine-grained hierarchy of the considered distances, we obtain a classification of stability that fits the efficiency of current implementations and quality of practical results. Our results induce several open questions regarding the lacking theoretical analysis of such practical distances.

Authors: Florian Wetzels, Christoph Garth

This paper introduces a novel stability measure for edit distances between merge trees of piecewise linear scalar fields. We apply the new measure to various metrics introduced recently in the field of scalar field comparison in scientific visualization. While previous stability measures are unable to capture the fine-grained hierarchy of the considered distances, we obtain a classification of stability that fits the efficiency of current implementations and quality of practical results. Our results induce several open questions regarding the lacking theoretical analysis of such practical distances.

Topolow: Force-Directed Euclidean Embedding of Dissimilarity Data with Robustness Against Non-Metricity and Sparsity

from arXiv: Computational Geometry

Authors: Omid Arhami, Pejman Rohani

The problem of embedding a set of objects into a low-dimensional Euclidean space based on a matrix of pairwise dissimilarities is fundamental in data analysis, machine learning, and statistics. However, the assumptions of many standard analytical methods are violated when the input dissimilarities fail to satisfy metric or Euclidean axioms. We present the mathematical and statistical foundations of Topolow, a physics-inspired, gradient-free optimization framework for such embedding problems. Topolow is conceptually related to force-directed graph drawing algorithms but is fundamentally distinguished by its goal of quantitative metric reconstruction. It models objects as particles in a physical system, and its novel optimization scheme proceeds through sequential, stochastic pairwise interactions, which circumvents the need to compute a global gradient and provides robustness against convergence to local optima, especially for sparse data. Topolow maximizes the likelihood under a Laplace error model, robust to outliers and heterogeneous errors, and properly handles censored data. Crucially, Topolow does not require the input dissimilarities to be metric, making it a robust solution for embedding non-metric measurements into a valid Euclidean space, thereby enabling the use of standard analytical tools. We demonstrate the superior performance of Topolow compared to standard Multidimensional Scaling (MDS) methods in reconstructing the geometry of sparse and non-Euclidean data. This paper formalizes the algorithm, first introduced as Topolow in the context of antigenic mapping in (Arhami and Rohani, 2025) (open access), with emphasis on its metric embedding and mathematical properties for a broader audience. The general-purpose function Euclidify is available in the R package topolow.

Authors: Omid Arhami, Pejman Rohani

The problem of embedding a set of objects into a low-dimensional Euclidean space based on a matrix of pairwise dissimilarities is fundamental in data analysis, machine learning, and statistics. However, the assumptions of many standard analytical methods are violated when the input dissimilarities fail to satisfy metric or Euclidean axioms. We present the mathematical and statistical foundations of Topolow, a physics-inspired, gradient-free optimization framework for such embedding problems. Topolow is conceptually related to force-directed graph drawing algorithms but is fundamentally distinguished by its goal of quantitative metric reconstruction. It models objects as particles in a physical system, and its novel optimization scheme proceeds through sequential, stochastic pairwise interactions, which circumvents the need to compute a global gradient and provides robustness against convergence to local optima, especially for sparse data. Topolow maximizes the likelihood under a Laplace error model, robust to outliers and heterogeneous errors, and properly handles censored data. Crucially, Topolow does not require the input dissimilarities to be metric, making it a robust solution for embedding non-metric measurements into a valid Euclidean space, thereby enabling the use of standard analytical tools. We demonstrate the superior performance of Topolow compared to standard Multidimensional Scaling (MDS) methods in reconstructing the geometry of sparse and non-Euclidean data. This paper formalizes the algorithm, first introduced as Topolow in the context of antigenic mapping in (Arhami and Rohani, 2025) (open access), with emphasis on its metric embedding and mathematical properties for a broader audience. The general-purpose function Euclidify is available in the R package topolow.

Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking

from arXiv: Data Structures and Algorithms

Authors: Shlomi Dolev

Consider graphs of n nodes, and use a Bloom filter of length 2 log3 n bits. An edge between nodes i and j, with i < j, turns on a certain bit of the Bloom filter according to a hash function on i and j. Pick a set of log n nodes and turn on all the bits of the Bloom filter required for these log n nodes to form a clique. As a result, the Bloom filter implies the existence of certain other edges, those edges (x, y), with x < y, such that all the bits selected by applying the hash functions to x and y happen to have been turned on due to hashing the clique edges into the Bloom filter. Constructing the graph consisting of the clique-selected edges and those edges mapped to the turned-on bits of the Bloom filter can be performed in polynomial time in n. Choosing a large enough polylogarithmic in n Bloom filter yields that the graph has only one clique of size log n, the planted clique. When the hash function is black-boxed, finding that clique is intractable and, therefore, inverting the function that maps log n nodes to a graph is not (likely to be) possible in polynomial time.

Authors: Shlomi Dolev

Consider graphs of n nodes, and use a Bloom filter of length 2 log3 n bits. An edge between nodes i and j, with i < j, turns on a certain bit of the Bloom filter according to a hash function on i and j. Pick a set of log n nodes and turn on all the bits of the Bloom filter required for these log n nodes to form a clique. As a result, the Bloom filter implies the existence of certain other edges, those edges (x, y), with x < y, such that all the bits selected by applying the hash functions to x and y happen to have been turned on due to hashing the clique edges into the Bloom filter. Constructing the graph consisting of the clique-selected edges and those edges mapped to the turned-on bits of the Bloom filter can be performed in polynomial time in n. Choosing a large enough polylogarithmic in n Bloom filter yields that the graph has only one clique of size log n, the planted clique. When the hash function is black-boxed, finding that clique is intractable and, therefore, inverting the function that maps log n nodes to a graph is not (likely to be) possible in polynomial time.

Efficient Direct-Access Ranked Retrieval

from arXiv: Data Structures and Algorithms

Authors: Mohsen Dehghankar, Raghav Mittal, Suraj Shetiya, Abolfazl Asudeh, Gautam Das

We study the problem of Direct-Access Ranked Retrieval (DAR) for interactive data tooling, where evolving data exploration practices, combined with large-scale and high-dimensional datasets, create new challenges. DAR concerns the problem of enabling efficient access to arbitrary rank positions according to a ranking function, without enumerating all preceding tuples. To address this need, we formalize the DAR problem and propose a theoretically efficient algorithm based on geometric arrangements, achieving logarithmic query time. However, this method suffers from exponential space complexity in high dimensions. Therefore, we develop a second class of algorithms based on $\varepsilon$-sampling, which consume a linear space. Since exactly locating the tuple at a specific rank is challenging due to its connection to the range counting problem, we introduce a relaxed variant called Conformal Set Ranked Retrieval (CSR), which returns a small subset guaranteed to contain the target tuple. To solve the CSR problem efficiently, we define an intermediate problem, Stripe Range Retrieval (SRR), and design a hierarchical sampling data structure tailored for narrow-range queries. Our method achieves practical scalability in both data size and dimensionality. We prove near-optimal bounds on the efficiency of our algorithms and validate their performance through extensive experiments on real and synthetic datasets, demonstrating scalability to millions of tuples and hundreds of dimensions.

Authors: Mohsen Dehghankar, Raghav Mittal, Suraj Shetiya, Abolfazl Asudeh, Gautam Das

We study the problem of Direct-Access Ranked Retrieval (DAR) for interactive data tooling, where evolving data exploration practices, combined with large-scale and high-dimensional datasets, create new challenges. DAR concerns the problem of enabling efficient access to arbitrary rank positions according to a ranking function, without enumerating all preceding tuples. To address this need, we formalize the DAR problem and propose a theoretically efficient algorithm based on geometric arrangements, achieving logarithmic query time. However, this method suffers from exponential space complexity in high dimensions. Therefore, we develop a second class of algorithms based on $\varepsilon$-sampling, which consume a linear space. Since exactly locating the tuple at a specific rank is challenging due to its connection to the range counting problem, we introduce a relaxed variant called Conformal Set Ranked Retrieval (CSR), which returns a small subset guaranteed to contain the target tuple. To solve the CSR problem efficiently, we define an intermediate problem, Stripe Range Retrieval (SRR), and design a hierarchical sampling data structure tailored for narrow-range queries. Our method achieves practical scalability in both data size and dimensionality. We prove near-optimal bounds on the efficiency of our algorithms and validate their performance through extensive experiments on real and synthetic datasets, demonstrating scalability to millions of tuples and hundreds of dimensions.

Instance-Optimal Uniformity Testing and Tracking

from arXiv: Data Structures and Algorithms

Authors: Guy Blanc, Clément L. Canonne, Erik Waingarten

In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the uniform distribution, or, alternatively, if its total variation distance from uniform exceeds some input distance parameter. This question has received a significant amount of interest and its complexity is, by now, fully settled. Yet, we argue that it fails to capture many scenarios of interest, and that its very definition as a gap problem in terms of a prespecified distance may lead to suboptimal performance. To address these shortcomings, we introduce the problem of uniformity tracking, whereby an algorithm is required to detect deviations from uniformity (however they may manifest themselves) using as few samples as possible, and be competitive against an optimal algorithm knowing the distribution profile in hindsight. Our main contribution is a $\operatorname{polylog}(\operatorname{opt})$-competitive uniformity tracking algorithm. We obtain this result by leveraging new structural results on Poisson mixtures, which we believe to be of independent interest.

Authors: Guy Blanc, Clément L. Canonne, Erik Waingarten

In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the uniform distribution, or, alternatively, if its total variation distance from uniform exceeds some input distance parameter. This question has received a significant amount of interest and its complexity is, by now, fully settled. Yet, we argue that it fails to capture many scenarios of interest, and that its very definition as a gap problem in terms of a prespecified distance may lead to suboptimal performance. To address these shortcomings, we introduce the problem of uniformity tracking, whereby an algorithm is required to detect deviations from uniformity (however they may manifest themselves) using as few samples as possible, and be competitive against an optimal algorithm knowing the distribution profile in hindsight. Our main contribution is a $\operatorname{polylog}(\operatorname{opt})$-competitive uniformity tracking algorithm. We obtain this result by leveraging new structural results on Poisson mixtures, which we believe to be of independent interest.

Facility Location and $k$-Median with Fair Outliers

from arXiv: Data Structures and Algorithms

Authors: Rajni Dabas, Samir Khuller, Emilie Rivkin

Classical clustering problems such as \emph{Facility Location} and \emph{$k$-Median} aim to efficiently serve a set of clients from a subset of facilities -- minimizing the total cost of facility openings and client assignments in Facility Location, and minimizing assignment (service) cost under a facility count constraint in $k$-Median. These problems are highly sensitive to outliers, and therefore researchers have studied variants that allow excluding a small number of clients as outliers to reduce cost. However, in many real-world settings, clients belong to different demographic or functional groups, and unconstrained outlier removal can disproportionately exclude certain groups, raising fairness concerns. We study \emph{Facility Location with Fair Outliers}, where each group is allowed a specified number of outliers, and the objective is to minimize total cost while respecting group-wise fairness constraints. We present a bicriteria approximation with a $O(1/\epsilon)$ approximation factor and $(1+ 2\epsilon)$ factor violation in outliers per group. For \emph{$k$-Median with Fair Outliers}, we design a bicriteria approximation with a $4(1+\omega/\epsilon)$ approximation factor and $(\omega + \epsilon)$ violation in outliers per group improving on prior work by avoiding dependence on $k$ in outlier violations. We also prove that the problems are W[1]-hard parameterized by $\omega$, assuming the Exponential Time Hypothesis. We complement our algorithmic contributions with a detailed empirical analysis, demonstrating that fairness can be achieved with negligible increase in cost and that the integrality gap of the standard LP is small in practice.

Authors: Rajni Dabas, Samir Khuller, Emilie Rivkin

Classical clustering problems such as \emph{Facility Location} and \emph{$k$-Median} aim to efficiently serve a set of clients from a subset of facilities -- minimizing the total cost of facility openings and client assignments in Facility Location, and minimizing assignment (service) cost under a facility count constraint in $k$-Median. These problems are highly sensitive to outliers, and therefore researchers have studied variants that allow excluding a small number of clients as outliers to reduce cost. However, in many real-world settings, clients belong to different demographic or functional groups, and unconstrained outlier removal can disproportionately exclude certain groups, raising fairness concerns. We study \emph{Facility Location with Fair Outliers}, where each group is allowed a specified number of outliers, and the objective is to minimize total cost while respecting group-wise fairness constraints. We present a bicriteria approximation with a $O(1/\epsilon)$ approximation factor and $(1+ 2\epsilon)$ factor violation in outliers per group. For \emph{$k$-Median with Fair Outliers}, we design a bicriteria approximation with a $4(1+\omega/\epsilon)$ approximation factor and $(\omega + \epsilon)$ violation in outliers per group improving on prior work by avoiding dependence on $k$ in outlier violations. We also prove that the problems are W[1]-hard parameterized by $\omega$, assuming the Exponential Time Hypothesis. We complement our algorithmic contributions with a detailed empirical analysis, demonstrating that fairness can be achieved with negligible increase in cost and that the integrality gap of the standard LP is small in practice.

A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm

from arXiv: Data Structures and Algorithms

Authors: Stefan Kuhlmann, Robert Weismantel

One important question in the theory of lattices is to detect a shortest vector: given a norm and a lattice, what is the smallest norm attained by a non-zero vector contained in the lattice? We focus on the infinity norm and work with lattices of the form $A\mathbb{Z}^n$, where $A$ has integer entries and is of full column rank. Finding a shortest vector is NP-hard. We show that this task is fixed parameter tractable in the parameter $\Delta$, the largest absolute value of the determinant of a full rank submatrix of $A$. The algorithm is based on a structural result that can be interpreted as a threshold phenomenon: whenever the dimension $n$ exceeds a certain value determined only by $\Delta$, then a shortest lattice vector attains an infinity norm value of one. This threshold phenomenon has several applications. In particular, it reveals that integer optimal solutions lie on faces of the given polyhedron whose dimensions are bounded only in terms of $\Delta$.

Authors: Stefan Kuhlmann, Robert Weismantel

One important question in the theory of lattices is to detect a shortest vector: given a norm and a lattice, what is the smallest norm attained by a non-zero vector contained in the lattice? We focus on the infinity norm and work with lattices of the form $A\mathbb{Z}^n$, where $A$ has integer entries and is of full column rank. Finding a shortest vector is NP-hard. We show that this task is fixed parameter tractable in the parameter $\Delta$, the largest absolute value of the determinant of a full rank submatrix of $A$. The algorithm is based on a structural result that can be interpreted as a threshold phenomenon: whenever the dimension $n$ exceeds a certain value determined only by $\Delta$, then a shortest lattice vector attains an infinity norm value of one. This threshold phenomenon has several applications. In particular, it reveals that integer optimal solutions lie on faces of the given polyhedron whose dimensions are bounded only in terms of $\Delta$.

Testing Quasiperiodicity

from arXiv: Data Structures and Algorithms

Authors: Christine Awofeso, Ben Bals, Oded Lachish, Solon P. Pissis

A cover (or quasiperiod) of a string $S$ is a shorter string $C$ such that every position of $S$ is contained in some occurrence of $C$ as a substring. The notion of covers was introduced by Apostolico and Ehrenfeucht over 30 years ago [Theor. Comput. Sci. 1993] and it has received significant attention from the combinatorial pattern matching community. In this note, we show how to efficiently test whether $S$ admits a cover. Our tester can also be translated into a streaming algorithm.

Authors: Christine Awofeso, Ben Bals, Oded Lachish, Solon P. Pissis

A cover (or quasiperiod) of a string $S$ is a shorter string $C$ such that every position of $S$ is contained in some occurrence of $C$ as a substring. The notion of covers was introduced by Apostolico and Ehrenfeucht over 30 years ago [Theor. Comput. Sci. 1993] and it has received significant attention from the combinatorial pattern matching community. In this note, we show how to efficiently test whether $S$ admits a cover. Our tester can also be translated into a streaming algorithm.

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

from arXiv: Data Structures and Algorithms

Authors: Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, Leqi Zhu

Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k$-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of $n$ due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. As an application, we solve a number of important graph problems with better bounds than previous work. We apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including $k$-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge DP algorithm for $k$-core decomposition with $O(\epsilon^{-1}\log n)$ additive error and no multiplicative error in $O(n)$ rounds. We also give a new $(2+\eta)$-factor multiplicative, $O(\epsilon^{-1}\log n)$ additive error algorithm in $O(\log^2 n)$ rounds for any constant $\eta > 0$. Both of these results are asymptotically tight against our new lower bound of $\Omega(\log n)$ for any constant-factor approximation algorithm for $k$-core decomposition. Our new algorithms for $k$-core also directly lead to new algorithms for densest subgraph and low out-degree ordering. Our novel private defective coloring algorithms uses number of colors proportional to the arboricity of the graph.

Authors: Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, Leqi Zhu

Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k$-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of $n$ due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. As an application, we solve a number of important graph problems with better bounds than previous work. We apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including $k$-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge DP algorithm for $k$-core decomposition with $O(\epsilon^{-1}\log n)$ additive error and no multiplicative error in $O(n)$ rounds. We also give a new $(2+\eta)$-factor multiplicative, $O(\epsilon^{-1}\log n)$ additive error algorithm in $O(\log^2 n)$ rounds for any constant $\eta > 0$. Both of these results are asymptotically tight against our new lower bound of $\Omega(\log n)$ for any constant-factor approximation algorithm for $k$-core decomposition. Our new algorithms for $k$-core also directly lead to new algorithms for densest subgraph and low out-degree ordering. Our novel private defective coloring algorithms uses number of colors proportional to the arboricity of the graph.

Robust Detection of Planted Subgraphs in Semi-Random Models

from arXiv: Data Structures and Algorithms

Authors: Dor Elimelech, Wasim Huleihel

Detection of planted subgraphs in Erd\"os-R\'enyi random graphs has been extensively studied, leading to a rich body of results characterizing both statistical and computational thresholds. However, most prior work assumes a purely random generative model, making the resulting algorithms potentially fragile in the face of real-world perturbations. In this work, we initiate the study of semi-random models for the planted subgraph detection problem, wherein an adversary is allowed to remove edges outside the planted subgraph before the graph is revealed to the statistician. Crucially, the statistician remains unaware of which edges have been removed, introducing fundamental challenges to the inference task. We establish fundamental statistical limits for detection under this semi-random model, revealing a sharp dichotomy. Specifically, for planted subgraphs with strongly sub-logarithmic maximum density detection becomes information-theoretically impossible in the presence of an adversary, despite being possible in the classical random model. In stark contrast, for subgraphs with super-logarithmic density, the statistical limits remain essentially unchanged; we prove that the optimal (albeit computationally intractable) likelihood ratio test remains robust. Beyond these statistical boundaries, we design a new computationally efficient and robust detection algorithm, and provide rigorous statistical guarantees for its performance. Our results establish the first robust framework for planted subgraph detection and open new directions in the study of semi-random models, computational-statistical trade-offs, and robustness in graph inference problems.

Authors: Dor Elimelech, Wasim Huleihel

Detection of planted subgraphs in Erd\"os-R\'enyi random graphs has been extensively studied, leading to a rich body of results characterizing both statistical and computational thresholds. However, most prior work assumes a purely random generative model, making the resulting algorithms potentially fragile in the face of real-world perturbations. In this work, we initiate the study of semi-random models for the planted subgraph detection problem, wherein an adversary is allowed to remove edges outside the planted subgraph before the graph is revealed to the statistician. Crucially, the statistician remains unaware of which edges have been removed, introducing fundamental challenges to the inference task. We establish fundamental statistical limits for detection under this semi-random model, revealing a sharp dichotomy. Specifically, for planted subgraphs with strongly sub-logarithmic maximum density detection becomes information-theoretically impossible in the presence of an adversary, despite being possible in the classical random model. In stark contrast, for subgraphs with super-logarithmic density, the statistical limits remain essentially unchanged; we prove that the optimal (albeit computationally intractable) likelihood ratio test remains robust. Beyond these statistical boundaries, we design a new computationally efficient and robust detection algorithm, and provide rigorous statistical guarantees for its performance. Our results establish the first robust framework for planted subgraph detection and open new directions in the study of semi-random models, computational-statistical trade-offs, and robustness in graph inference problems.

An Improved Bound for the Beck-Fiala Conjecture

from arXiv: Data Structures and Algorithms

Authors: Nikhil Bansal, Haotian Jiang

In 1981, Beck and Fiala [Discrete Appl. Math, 1981] conjectured that given a set system $A \in \{0,1\}^{m \times n}$ with degree at most $k$ (i.e., each column of $A$ has at most $k$ non-zeros), its combinatorial discrepancy $\mathsf{disc}(A) := \min_{x \in \{\pm 1\}^n} \|Ax\|_\infty$ is at most $O(\sqrt{k})$. Previously, the best-known bounds for this conjecture were either $O(k)$, first established by Beck and Fiala [Discrete Appl. Math, 1981], or $O(\sqrt{k \log n})$, first proved by Banaszczyk [Random Struct. Algor., 1998]. We give an algorithmic proof of an improved bound of $O(\sqrt{k \log\log n})$ whenever $k \geq \log^5 n$, thus matching the Beck-Fiala conjecture up to $O(\sqrt{\log \log n})$ for almost the full regime of $k$.

Authors: Nikhil Bansal, Haotian Jiang

In 1981, Beck and Fiala [Discrete Appl. Math, 1981] conjectured that given a set system $A \in \{0,1\}^{m \times n}$ with degree at most $k$ (i.e., each column of $A$ has at most $k$ non-zeros), its combinatorial discrepancy $\mathsf{disc}(A) := \min_{x \in \{\pm 1\}^n} \|Ax\|_\infty$ is at most $O(\sqrt{k})$. Previously, the best-known bounds for this conjecture were either $O(k)$, first established by Beck and Fiala [Discrete Appl. Math, 1981], or $O(\sqrt{k \log n})$, first proved by Banaszczyk [Random Struct. Algor., 1998]. We give an algorithmic proof of an improved bound of $O(\sqrt{k \log\log n})$ whenever $k \geq \log^5 n$, thus matching the Beck-Fiala conjecture up to $O(\sqrt{\log \log n})$ for almost the full regime of $k$.

Fast Gaussian process inference by exact Matérn kernel decomposition

from arXiv: Data Structures and Algorithms

Authors: Nicolas Langrené, Xavier Warin, Pierre Gruet

To speed up Gaussian process inference, a number of fast kernel matrix-vector multiplication (MVM) approximation algorithms have been proposed over the years. In this paper, we establish an exact fast kernel MVM algorithm based on exact kernel decomposition into weighted empirical cumulative distribution functions, compatible with a class of kernels which includes multivariate Mat\'ern kernels with half-integer smoothness parameter. This algorithm uses a divide-and-conquer approach, during which sorting outputs are stored in a data structure. We also propose a new algorithm to take into account some linear fixed effects predictor function. Our numerical experiments confirm that our algorithm is very effective for low-dimensional Gaussian process inference problems with hundreds of thousands of data points. An implementation of our algorithm is available at gitlab.com/warin/fastgaussiankernelregression.git.

Authors: Nicolas Langrené, Xavier Warin, Pierre Gruet

To speed up Gaussian process inference, a number of fast kernel matrix-vector multiplication (MVM) approximation algorithms have been proposed over the years. In this paper, we establish an exact fast kernel MVM algorithm based on exact kernel decomposition into weighted empirical cumulative distribution functions, compatible with a class of kernels which includes multivariate Mat\'ern kernels with half-integer smoothness parameter. This algorithm uses a divide-and-conquer approach, during which sorting outputs are stored in a data structure. We also propose a new algorithm to take into account some linear fixed effects predictor function. Our numerical experiments confirm that our algorithm is very effective for low-dimensional Gaussian process inference problems with hundreds of thousands of data points. An implementation of our algorithm is available at https://gitlab.com/warin/fastgaussiankernelregression.git.

Faster Distributed $Δ$-Coloring via a Reduction to MIS

from arXiv: Data Structures and Algorithms

Authors: Yann Bourreau, Sebastian Brandt, Alexandre Nolin

Recent improvements on the deterministic complexities of fundamental graph problems in the LOCAL model of distributed computing have yielded state-of-the-art upper bounds of $\tilde{O}(\log^{5/3} n)$ rounds for maximal independent set (MIS) and $(\Delta + 1)$-coloring [Ghaffari, Grunau, FOCS'24] and $\tilde{O}(\log^{19/9} n)$ rounds for the more restrictive $\Delta$-coloring problem [Ghaffari, Kuhn, FOCS'21; Ghaffari, Grunau, FOCS'24; Bourreau, Brandt, Nolin, STOC'25]. In our work, we show that $\Delta$-coloring can be solved deterministically in $\tilde{O}(\log^{5/3} n)$ rounds as well, matching the currently best bound for $(\Delta + 1)$-coloring. We achieve our result by developing a reduction from $\Delta$-coloring to MIS that guarantees that the (asymptotic) complexity of $\Delta$-coloring is at most the complexity of MIS, unless MIS can be solved in sublogarithmic time, in which case, due to the $\Omega(\log n)$-round $\Delta$-coloring lower bound from [BFHKLRSU, STOC'16], our reduction implies a tight complexity of $\Theta(\log n)$ for $\Delta$-coloring. In particular, any improvement on the complexity of the MIS problem will yield the same improvement for the complexity of $\Delta$-coloring (up to the true complexity of $\Delta$-coloring). Our reduction yields improvements for $\Delta$-coloring in the randomized LOCAL model and when complexities are parameterized by both $n$ and $\Delta$. We obtain a randomized complexity bound of $\tilde{O}(\log^{5/3} \log n)$ rounds (improving over the state of the art of $\tilde{O}(\log^{8/3} \log n)$ rounds) on general graphs and tight complexities of $\Theta(\log n)$ and $\Theta(\log \log n)$ for the deterministic, resp.\ randomized, complexity on bounded-degree graphs. In the special case of graphs of constant clique number (which for instance include bipartite graphs), we also give a reduction to the $(\Delta+1)$-coloring problem.

Authors: Yann Bourreau, Sebastian Brandt, Alexandre Nolin

Recent improvements on the deterministic complexities of fundamental graph problems in the LOCAL model of distributed computing have yielded state-of-the-art upper bounds of $\tilde{O}(\log^{5/3} n)$ rounds for maximal independent set (MIS) and $(\Delta + 1)$-coloring [Ghaffari, Grunau, FOCS'24] and $\tilde{O}(\log^{19/9} n)$ rounds for the more restrictive $\Delta$-coloring problem [Ghaffari, Kuhn, FOCS'21; Ghaffari, Grunau, FOCS'24; Bourreau, Brandt, Nolin, STOC'25]. In our work, we show that $\Delta$-coloring can be solved deterministically in $\tilde{O}(\log^{5/3} n)$ rounds as well, matching the currently best bound for $(\Delta + 1)$-coloring. We achieve our result by developing a reduction from $\Delta$-coloring to MIS that guarantees that the (asymptotic) complexity of $\Delta$-coloring is at most the complexity of MIS, unless MIS can be solved in sublogarithmic time, in which case, due to the $\Omega(\log n)$-round $\Delta$-coloring lower bound from [BFHKLRSU, STOC'16], our reduction implies a tight complexity of $\Theta(\log n)$ for $\Delta$-coloring. In particular, any improvement on the complexity of the MIS problem will yield the same improvement for the complexity of $\Delta$-coloring (up to the true complexity of $\Delta$-coloring). Our reduction yields improvements for $\Delta$-coloring in the randomized LOCAL model and when complexities are parameterized by both $n$ and $\Delta$. We obtain a randomized complexity bound of $\tilde{O}(\log^{5/3} \log n)$ rounds (improving over the state of the art of $\tilde{O}(\log^{8/3} \log n)$ rounds) on general graphs and tight complexities of $\Theta(\log n)$ and $\Theta(\log \log n)$ for the deterministic, resp.\ randomized, complexity on bounded-degree graphs. In the special case of graphs of constant clique number (which for instance include bipartite graphs), we also give a reduction to the $(\Delta+1)$-coloring problem.

Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation

from arXiv: Data Structures and Algorithms

Authors: Oded Schwartz, Eyal Zwecher

Matrix multiplication is a fundamental kernel in high performance computing. Many algorithms for fast matrix multiplication can only be applied to enormous matrices ($n>10^{100}$) and thus cannot be used in practice. Of all algorithms applicable to feasible input, Pan's $O(n^{2.773372})$ algorithm (1982) is asymptotically the fastest. We obtain an $O(n^{2.773203})$ algorithm applicable to the same input sizes as Pan's algorithm. This algorithm is the fastest matrix multiplication algorithm with base case smaller than $1000$. Further, our method obtains the best asymptotic complexity for many small base cases, starting at $n_0=28$. We also obtain better exponents for larger base cases. To construct our algorithm, we use the trilinear aggregation method. We find parts of the algorithms that are equivalent to matrix multiplication with smaller base case, and use the de Groote equivalence to replace these parts in a way that allows further optimization of our algorithms. Finally, we improve the additive complexity of our algorithms by finding a sparse decomposition and reducing the leading coefficient. These mark a fundamental step towards outperforming existing fast matrix multiplication algorithms in practice.

Authors: Oded Schwartz, Eyal Zwecher

Matrix multiplication is a fundamental kernel in high performance computing. Many algorithms for fast matrix multiplication can only be applied to enormous matrices ($n>10^{100}$) and thus cannot be used in practice. Of all algorithms applicable to feasible input, Pan's $O(n^{2.773372})$ algorithm (1982) is asymptotically the fastest. We obtain an $O(n^{2.773203})$ algorithm applicable to the same input sizes as Pan's algorithm. This algorithm is the fastest matrix multiplication algorithm with base case smaller than $1000$. Further, our method obtains the best asymptotic complexity for many small base cases, starting at $n_0=28$. We also obtain better exponents for larger base cases. To construct our algorithm, we use the trilinear aggregation method. We find parts of the algorithms that are equivalent to matrix multiplication with smaller base case, and use the de Groote equivalence to replace these parts in a way that allows further optimization of our algorithms. Finally, we improve the additive complexity of our algorithms by finding a sparse decomposition and reducing the leading coefficient. These mark a fundamental step towards outperforming existing fast matrix multiplication algorithms in practice.