Theory of Computing Report

The Faculty of Computer Science and Engineering of Innopolis University invites high-caliber Full Professors

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Authors: Michaela Borzechowski, Simon Weber

A unique sink orientation (USO) is an orientation of the $n$-dimensional hypercube graph such that every non-empty face contains a unique sink. Schurr showed that given any $n$-dimensional USO and any dimension $i$, the set of edges $E_i$ in that dimension can be decomposed into equivalence classes (so-called phases), such that flipping the orientation of a subset $S$ of $E_i$ yields another USO if and only if $S$ is a union of a set of these phases. In this paper we prove various results on the structure of phases. Using these results, we show that all phases can be computed in $O(3^n)$ time, significantly improving upon the previously known $O(4^n)$ trivial algorithm. Furthermore, we show that given a boolean circuit of size $poly(n)$ succinctly encoding an $n$-dimensional (acyclic) USO, it is PSPACE-complete to determine whether two given edges are in the same phase. The problem is thus equally difficult as determining whether the hypercube orientation encoded by a given circuit is an acyclic USO [G\"artner and Thomas, STACS'15].

Authors: Daniel Alabi, Dimitris Kalimeris

Large-scale analysis of the distributions of the network graphs observed in naturally-occurring phenomena has revealed that the degrees of such graphs follow a power-law or lognormal distribution. Seshadhri, Pinar, and Kolda (J. ACM, 2013) proved that stochastic Kronecker graph (SKG) models cannot generate graphs with degree distribution that follows a power-law or lognormal distribution. As a result, variants of the SKG model have been proposed to generate graphs which approximately follow degree distributions, without any significant oscillations. However, all existing solutions either require significant additional parameterization or have no provable guarantees on the degree distribution.

-- In this work, we present statistical and computational identifiability notions which imply the separation of SKG models. Specifically, we prove that SKG models in different identifiability classes can be separated by the existence of isolated vertices and connected components in their corresponding generated graphs. This could explain the large (i.e., $>50\%$) fraction of isolated vertices in some popular graph generation benchmarks.

-- We present and analyze an efficient algorithm that can get rid of oscillations in the degree distribution by mixing seeds of relative prime dimensions. For an initial $2\times 1$ and $2\times 2$ seed, a crucial subroutine of this algorithm solves a degree-2 and degree-4 optimization problem in the variables of the initial seed, respectively. We generalize this approach to solving optimization problems for $m\times n$ seeds, for any $m, n\in\mathbb{N}$.

-- The use of $3\times 3$ seeds alone cannot get rid of significant oscillations. We prove that such seeds result in degree distribution that is bounded above by an exponential tail and thus cannot result in a power-law or lognormal.

Authors: Aditya Bhaskara, Sepideh Mahabadi, Ali Vakilian

Given a set of points of interest, a volumetric spanner is a subset of the points using which all the points can be expressed using "small" coefficients (measured in an appropriate norm). Formally, given a set of vectors $X = \{v_1, v_2, \dots, v_n\}$, the goal is to find $T \subseteq [n]$ such that every $v \in X$ can be expressed as $\sum_{i\in T} \alpha_i v_i$, with $\|\alpha\|$ being small. This notion, which has also been referred to as a well-conditioned basis, has found several applications, including bandit linear optimization, determinant maximization, and matrix low rank approximation. In this paper, we give almost optimal bounds on the size of volumetric spanners for all $\ell_p$ norms, and show that they can be constructed using a simple local search procedure. We then show the applications of our result to other tasks and in particular the problem of finding coresets for the Minimum Volume Enclosing Ellipsoid (MVEE) problem.

Authors: Jérémie Cabessa, Yann Strozecki

We provide a refined characterization of the super-Turing computational power of analog, evolving, and stochastic neural networks based on the Kolmogorov complexity of their real weights, evolving weights, and real probabilities, respectively. First, we retrieve an infinite hierarchy of classes of analog networks defined in terms of the Kolmogorov complexity of their underlying real weights. This hierarchy is located between the complexity classes $\mathbf{P}$ and $\mathbf{P/poly}$. Then, we generalize this result to the case of evolving networks. A similar hierarchy of Kolomogorov-based complexity classes of evolving networks is obtained. This hierarchy also lies between $\mathbf{P}$ and $\mathbf{P/poly}$. Finally, we extend these results to the case of stochastic networks employing real probabilities as source of randomness. An infinite hierarchy of stochastic networks based on the Kolmogorov complexity of their probabilities is therefore achieved. In this case, the hierarchy bridges the gap between $\mathbf{BPP}$ and $\mathbf{BPP/log^*}$. Beyond proving the existence and providing examples of such hierarchies, we describe a generic way of constructing them based on classes of functions of increasing complexity. For the sake of clarity, this study is formulated within the framework of echo state networks. Overall, this paper intends to fill the missing results and provide a unified view about the refined capabilities of analog, evolving and stochastic neural networks.

Authors: Antonis Achilleos (Reykjavik University), Dario Della Monica (University of Udine)

This volume contains the proceedings of the 14th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2023). The aim of GandALF 2023 symposium is to bring together researchers from academia and industry who are actively working in the fields of Games, Automata, Logics, and Formal Verification. The idea is to cover an ample spectrum of themes, ranging from theory to applications, and stimulate cross-fertilization.

Authors: Rusul J. Alsaedi, Joachim Gudmundsson, André van Renssen

Given a set of $n$ point robots inside a simple polygon $P$, the task is to move the robots from their starting positions to their target positions along their shortest paths, while the mutual visibility of these robots is preserved. Previous work only considered two robots. In this paper, we present an $O(mn)$ time algorithm, where $m$ is the complexity of the polygon, when all the starting positions lie on a line segment $S$, all the target positions lie on a line segment $T$, and $S$ and $T$ do not intersect. We also argue that there is no polynomial-time algorithm, whose running time depends only on $n$ and $m$, that uses a single strategy for the case where $S$ and $T$ intersect.

Authors: Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar

We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst-case and average-case input models, where the input is generated by (1) choosing an arbitrary planted assignment $x^*$, (2) choosing an arbitrary clause structure, and (3) choosing literal negations for each clause from an arbitrary distribution "shifted by $x^*$" so that $x^*$ satisfies each constraint. For an $n$ variable semirandom planted instance of a $k$-arity CSP, our algorithm runs in polynomial time and outputs an assignment that satisfies all but a $o(1)$-fraction of constraints, provided that the instance has at least $\tilde{O}(n^{k/2})$ constraints. This matches, up to $polylog(n)$ factors, the clause threshold for algorithms that solve fully random planted CSPs [FPV15], as well as algorithms that refute random and semirandom CSPs [AOW15, AGK21]. Our result shows that despite having worst-case clause structure, the randomness in the literal patterns makes semirandom planted CSPs significantly easier than worst-case, where analogous results require $O(n^k)$ constraints [AKK95, FLP16].

Perhaps surprisingly, our algorithm follows a significantly different conceptual framework when compared to the recent resolution of semirandom CSP refutation. This turns out to be inherent and, at a technical level, can be attributed to the need for relative spectral approximation of certain random matrices - reminiscent of the classical spectral sparsification - which ensures that an SDP can certify the uniqueness of the planted assignment. In contrast, in the refutation setting, it suffices to obtain a weaker guarantee of absolute upper bounds on the spectral norm of related matrices.

Authors: Yann Strozecki

This habilitation thesis is intended to be a good introduction to enumeration, the problem of listing solutions. It focuses on the different ways of measuring complexity in enumeration, with a particular emphasis on my contributions to the field.

Authors: Tatsuya Gima, Eun Jung Kim, Noleen Köhler, Nikolaos Melissinos, Manolis Vasilakis

Given a graph $G$ and an integer $b$, Bandwidth asks whether there exists a bijection $\pi$ from $V(G)$ to $\{1, \ldots, |V(G)|\}$ such that $\max_{\{u, v \} \in E(G)} | \pi(u) - \pi(v) | \leq b$. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the treedepth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number of the input graph. In this paper, we make progress towards the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number $\omega$ of the input graph, thus generalizing the previously mentioned result for vertex cover. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results generalize some of the previous results and narrow some of the complexity gaps.

Authors: Fabio Cannizzo

Many simulation applications require the generation of long sequences of pseudo-random numbers. Linear recurrences modulo 2 are commonly used as the fundamental building block for constructing pseudo-random number generators with extended periods and excellent statistical properties. These generators consist of a lengthy binary state vector that evolves iteratively through linear transformations. One widely accepted pseudo-random generator in this category is the Mersenne twister 19937 (MT19937), proposed by Matsumoto and Nishimura, which has been implemented in numerous software libraries and numerical packages. The MT19937's popularity stems from its favorable distribution properties and the simplicity and speed of its algorithm. The linear transformation responsible for evolving the binary state vector can be expressed as a concise set of elementary bit manipulations. However, this transformation does not fully utilize the potential for parallelization through SIMD instructions available on modern hardware, limiting further speed enhancements. This paper introduces a new SIMD-friendly random number generator, which maintains the same statistical properties and period as the MT19937. It combines the random streams of multiple MT19937 instances with state vectors de-phased via jump-ahead transformations, then polls each instance in a round-robin fashion. By evolving their vector states simultaneously, the new generator achieves perfect vectorization, fully leveraging on SIMD hardware capabilities. Comprehensive test results demonstrate that the throughput of the new generator scales approximately linearly with the width of the SIMD registers used. This provides significant speed improvements, especially on modern CPUs equipped with larger SIMD registers, and allows for efficient generation of random numbers for various simulation applications.

Authors: Anders Aamand, Justin Y. Chen, Allen Liu, Sandeep Silwal, Pattara Sukprasert, Ali Vakilian, Fred Zhang

Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is $\alpha$-IP stable if the average distance of every data point to its own cluster is at most $\alpha$ times the average distance to any other cluster. Unfortunately, determining if a dataset admits a $1$-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown if an $o(n)$-IP stable clustering always \emph{exists}, as the prior state of the art only guaranteed an $O(n)$-IP stable clustering. We close this gap in understanding and show that an $O(1)$-IP stable clustering always exists for general metrics, and we give an efficient algorithm which outputs such a clustering. We also introduce generalizations of IP stability beyond average distance and give efficient, near-optimal algorithms in the cases where we consider the maximum and minimum distances within and between clusters.

Authors: Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk, Meirav Zehavi

Given an undirected graph $G$ and a multiset of $k$ terminal pairs $\mathcal{X}$, the Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether $G$ has $k$ pairwise internally vertex-disjoint paths and $k$ pairwise edge-disjoint paths, respectively, connecting every terminal pair in~$\mathcal{X}$. In this paper, we study the kernelization complexity of \VDP~and~\EDP~on subclasses of chordal graphs. For \VDP, we design a $4k$ vertex kernel on split graphs and an $\mathcal{O}(k^2)$ vertex kernel on well-partitioned chordal graphs. We also show that the problem becomes polynomial-time solvable on threshold graphs. For \textsc{EDP}, we first prove that the problem is $\mathsf{NP}$-complete on complete graphs. Then, we design an $\mathcal{O}(k^{2.75})$ vertex kernel for \EDP~on split graphs, and improve it to a $7k+1$ vertex kernel on threshold graphs. Lastly, we provide an $\mathcal{O}(k^2)$ vertex kernel for \EDP~on block graphs and a $2k+1$ vertex kernel for clique paths. Our contributions improve upon several results in the literature, as well as resolve an open question by Heggernes et al.~[Theory Comput. Syst., 2015].

Authors: Akhil Bhimaraju, S. Rasoul Etesami, Lav R. Varshney

Many settings, such as medical testing of patients in hospitals or matching riders to drivers in ride-hailing platforms, require handling arrivals over time. In such applications, it is often beneficial to group the arriving orders, samples, or requests into batches and process the larger batches rather than individual arrivals. However, waiting too long to create larger batches incurs a waiting cost for past arrivals. On the other hand, processing the arrivals too soon leads to higher processing costs by missing the economies of scale of grouping larger numbers of arrivals into larger batches. Moreover, the timing of the next arrival is often unknown, meaning that fixed-size batches or fixed wait times tend to be suboptimal. In this work, we consider the problem of finding the optimal batching schedule to minimize the average wait time plus the average processing cost under both offline and online settings. In the offline problem in which all arrival times are known a priori, we show that the optimal batching schedule can be found in polynomial time by reducing it to a shortest path problem on a weighted acyclic graph. For the online problem with unknown arrival times, we develop online algorithms that are provably competitive for a broad range of processing-cost functions. We also provide a lower bound on the competitive ratio that no online algorithm can beat. Finally, we run extensive numerical experiments on simulated and real data to demonstrate the effectiveness of our proposed algorithms against the optimal offline benchmark.

Authors: Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski

We revisit the recent polynomial-time algorithm for the Max Weight Independent Set (MWIS) problem in bounded-degree graphs excluding a fixed subdivided claw $S_{t,t,t}$ as an induced subgraph [Abrishami, Dibek, Chudnovsky, Rz\k{a}\.zewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time $n^{O(\Delta^2)}$, where $n$ is the number of vertices of the instance and $\Delta$ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed subdivided claw as an induced subgraph and a fixed biclique as a subgraph.

Authors: Matthias Lanzinger, Igor Razgon

Generalised hypertree width ($ghw$) is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing $ghw$ of a hypergraph is notoriously hard. The decision version of the problem, checking whether $ghw(H) \leq k$, is paraNP-hard when parameterised by $k$. Furthermore, approximation of $ghw$ is at least as hard as approximation of Set-Cover, which is known to not admit any fpt approximation algorithms.

Research in the computation of ghw so far has focused on identifying structural restrictions to hypergraphs -- such as bounds on the size of edge intersections -- that permit XP algorithms for $ghw$. Yet, even under these restrictions that problem has so far evaded any kind of fpt algorithm. In this paper we make the first step towards fpt algorithms for $ghw$ by showing that the parameter can be approximated in fpt time for graphs of bounded edge intersection size. In concrete terms we show that there exists an fpt algorithm, parameterised by $k$ and $d$, that for input hypergraph $H$ with maximal cardinality of edge intersections $d$ and integer $k$ either outputs a tree decomposition with $ghw(H) \leq 4k(k+d+1+)(2k-1)$, or rejects, in which case it is guaranteed that $ghw(H) > k$. Thus, in the special case, of hypergraphs of bounded edge intersection, we obtain an fpt $O(k^3)$-approximation algorithm for $ghw$.

Authors: Julien Eudine, Mohammed Alser, Gagandeep Singh, Can Alkan, Onur Mutlu

Motivation: Read mapping is a computationally expensive process and a major bottleneck in genomics analyses. The performance of read mapping is mainly limited by the performance of three key computational steps: Index Querying, Seed Chaining, and Sequence Alignment. The first step is dominated by how fast and frequent it accesses the main memory (i.e., memory-bound), while the latter two steps are dominated by how fast the CPU can compute their computationally-costly dynamic programming algorithms (i.e., compute-bound). Accelerating these three steps by exploiting new algorithms and new hardware devices is essential to accelerate most genome analysis pipelines that widely use read mapping. Given the large body of work on accelerating Sequence Alignment, this work focuses on significantly improving the remaining steps. Results: We introduce GateSeeder, the first CPU-FPGA-based near-memory acceleration of both short and long read mapping. GateSeeder exploits near-memory computation capability provided by modern FPGAs that couple a reconfigurable compute fabric with high-bandwidth memory (HBM) to overcome the memory-bound and compute-bound bottlenecks. GateSeeder also introduces a new lightweight algorithm for finding the potential matching segment pairs. Using real ONT, HiFi, and Illumina sequences, we experimentally demonstrate that GateSeeder outperforms Minimap2, without performing sequence alignment, by up to 40.3x, 4.8x, and 2.3x, respectively. When performing read mapping with sequence alignment, GateSeeder outperforms Minimap2 by 1.15-4.33x (using KSW2) and by 1.97-13.63x (using WFA-GPU). Availability: https://github.com/CMU-SAFARI/GateSeeder

Authors: Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman

We consider the classic Correlation Clustering problem: Given a complete graph where edges are labelled either $+$ or $-$, the goal is to find a partition of the vertices that minimizes the number of the \pedges across parts plus the number of the \medges within parts. Recently, Cohen-Addad, Lee and Newman [CLN22] presented a 1.994-approximation algorithm for the problem using the Sherali-Adams hierarchy, hence breaking through the integrality gap of 2 for the classic linear program and improving upon the 2.06-approximation of Chawla, Makarychev, Schramm and Yaroslavtsev [CMSY15].

We significantly improve the state-of-the-art by providing a 1.73-approximation for the problem. Our approach introduces a preclustering of Correlation Clustering instances that allows us to essentially ignore the error arising from the {\em correlated rounding} used by [CLN22]. This additional power simplifies the previous algorithm and analysis. More importantly, it enables a new {\em set-based rounding} that complements the previous roundings. A combination of these two rounding algorithms yields the improved bound.

Authors: Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou

We propose an efficient $\epsilon$-differentially private algorithm, that given a simple {\em weighted} $n$-vertex, $m$-edge graph $G$ with a \emph{maximum unweighted} degree $\Delta(G) \leq n-1$, outputs a synthetic graph which approximates the spectrum with $\widetilde{O}(\min\{\Delta(G), \sqrt{n}\})$ bound on the purely additive error. To the best of our knowledge, this is the first $\epsilon$-differentially private algorithm with a non-trivial additive error for approximating the spectrum of the graph. One of the subroutines of our algorithm also precisely simulates the exponential mechanism over a non-convex set, which could be of independent interest given the recent interest in sampling from a {\em log-concave distribution} defined over a convex set. Spectral approximation also allows us to approximate all possible $(S,T)$-cuts, but it incurs an error that depends on the maximum degree, $\Delta(G)$. We further show that using our sampler, we can also output a synthetic graph that approximates the sizes of all $(S,T)$-cuts on $n$ vertices weighted graph $G$ with $m$ edges while preserving $(\epsilon,\delta)$-differential privacy and an additive error of $\widetilde{O}(\sqrt{mn}/\epsilon)$. We also give a matching lower bound (with respect to all the parameters) on the private cut approximation for weighted graphs. This removes the gap of $\sqrt{W_{\mathsf{avg}}}$ in the upper and lower bound in Eli{\'a}{\v{s}}, Kapralov, Kulkarni, and Lee (SODA 2020), where $W_{\mathsf{avg}}$ is the average edge weight.

Rational Identity Testing (RIT) is the decision problem of determining whether or not a given noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg et al., 2016; Ivanyos et al., 2018; Hamada and Hirai, 2021], and a randomized polynomial-time black-box algorithm [Derksen and Makam, 2017] via singularity testing of linear matrices over the free skew field. Designing a subexponential-time deterministic RIT algorithm in black-box is a major open problem in this area. Despite being open for several years, this question has seen very limited progress. In fact, the only known result in this direction is the construction of a quasipolynomial-size hitting set for rational formulas of only inversion height two [Arvind et al., 2022]. In this paper, we settle this problem and obtain a deterministic quasipolynomial-time RIT algorithm for the general case in the black-box setting. Our algorithm uses ideas from the theory of finite dimensional division algebras, algebraic complexity theory, and the theory of generalized formal power series.

• Equal-area right and isosceles triangles with their bases partitioning the radius of a circle and their apexes on the circle. What is the angle between them?

• Joel Hamkins’ workshop on the mathematics of infinitary games (\(\mathbb{M}\)) consists of a sequence of 90-minute Zoom talks scattered through the fall, and kicked off with a talk by Davide Leonessi on infinite draughts (checkers). Hamkins writes: “The workshop talks will be run at a high level of sophistication, aimed for the most part at serious researchers currently working in this emerging area. Mathematicians, computer scientists, infinitary game theorists, all serious researchers are welcome.”

• Simon Brendle wins the 2024 Breakthrough Prize in mathematics (\(\mathbb{M}\)) As Ian Agol writes, “he solved the Hsiang–Lawson conjecture, showing that the only embedded minimal surface in the (round) 3-sphere is the Clifford torus”.

• In a lunchtime discussion about the greedy-algorithms part of the undergraduate algorithms course that all computer science majors take, one of my colleagues pointed out that the Gale–Shapley algorithm for stable matching defines an antimatroid (\(\mathbb{M}\)). If you consider the problem on employers and applicants, with an arbitrary unmatched employer sending a job offer to an applicant in each step, then every job offer that might be sent remains available to be sent until it eventually is sent, one of the defining properties of antimatroids. (The other is that triggering an offer letter depends only on what has already happened but not on what order it has happened: an offer is sent if the next-more-preferred candidate has already been sent an offer from the same employer and another offer they like better.) It is immediate consequence that you will always get the same matching regardless of how you choose which employer to send a letter in each step. (Usually this is instead proven as a consequence of the employer-optimality of the resulting matching.)

  The same idea of having a pool of things that you can choose to do, with the ordering of choice irrelevant to the result, comes up frequently in other algorithms, and it would be easy to group other standard algorithms-course topics under the same framework (especially topological sorting). Sadly, I don’t know of any algorithms textbook that covers these topics in this way. Gale–Shapley is in the greedy chapter of Jeff Erickson’s algorithms text, but without discussion of the antimatroid property and without connection to other antimatroid problems.

• When computers write proofs, what’s the point of mathematicians (\(\mathbb{M}\), via)? Video by Quanta magazine with Andrew Granville, with accompanying article “Why mathematical proof is a social compact.

• Talk slides for my talk at Graph Drawing, “On the Biplanarity of Blowups” (\(\mathbb{M}\)). It won the best paper award for the theory track of the conference! I also presented a poster on “The Widths of Strict Outerconfluent Graphs”. For more in-depth posts on these papers see here and here respectively.

• A coin flip by any other name (\(\mathbb{M}\)), or why random cyclic quadrilaterals contain the origin with probability \(\tfrac12\).

• A tower of conjectures that rests upon a needle (\(\mathbb{M}\)). In Quanta, Jordana Cepelewicz explains how a seeming curiosity, the Kakeya needle problem on the minimum area within which a line segment can rotate, is connected to deep and fundamental questions in partial differential equations and harmonic analysis.

• A faster direct sampling algorithm for equilateral closed polygons (\(\mathbb{M}\)), by Jason Cantarella, Henrik Schumacher, and Clayton Shonkwiler, improving their previous work on sampling a certain probability distribution on these polygons. As Shonkwiler writes, a key idea is to estimate the volume of “some weird polytope”, which turns out to have the same volume as a central slab of a hypercube, proven using toric symplectic geometry.

• Optimal metric distortion for voting (\(\mathbb{M}\)). Blog post by Prasanna Ramakrishnan explaining the plurality veto voting rule of Kempe and Kızılkaya, which optimally approximates the minimum sum of voter-candidate distances in an unknown metric space.

• US states mapped as a rectangular subdivision. Getting the Four Corners correct prevents California from being in the lower left corner where one would expect it. As Dan Drake writes, “topologists make for lousy cartographers.”

• My school has posted a news story about my work at the recent Graph Drawing conference, “On the Biplanarity of Blowups” (\(\mathbb{M}\)) and its best-paper win at the conference.

• After resigning en masse from American Institute of Mathematical Sciences’ Journal of Geometric Mechanics “following a dispute with their publisher over special issues and article volume” which “would have the effect of jeopardizing scientific integrity for the sake of financial gain” the editors have launched a new journal, Geometric Mechanics, with … World Scientific (\(\mathbb{M}\)). What are they thinking? As commercial publishers go, I have nothing against World Scientific, but for new journals intended to avoid financially-motivated distortion of their scientific integrity, diamond open access is the only way to go.

• Lego Reuleaux triangle mechanisms (\(\mathbb{M}\)).

By David Eppstein

A few years ago if you asked “Can blockchains scale?” most people would give three reasons why, fundamentally, the answer is “No!” Data: every transaction needs to be replicated by every miner (validator). So increasing security by adding more validators inherently causes more replication. Having $n$ validators implies that your...

Authors: Raffaele Marino

This chapter delves into the realm of computational complexity, exploring the world of challenging combinatorial problems and their ties with statistical physics. Our exploration starts by delving deep into the foundations of combinatorial challenges, emphasizing their nature. We will traverse the class P, which comprises problems solvable in polynomial time using deterministic algorithms, contrasting it with the class NP, where finding efficient solutions remains an enigmatic endeavor, understanding the intricacies of algorithmic transitions and thresholds demarcating the boundary between tractable and intractable problems. We will discuss the implications of the P versus NP problem, representing one of the profoundest unsolved enigmas of computer science and mathematics, bearing a tantalizing reward for its resolution. Drawing parallels between combinatorics and statistical physics, we will uncover intriguing interconnections that shed light on the nature of challenging problems. Statistical physics unveils profound analogies with complexities witnessed in combinatorial landscapes. Throughout this chapter, we will discuss the interplay between computational complexity theory and statistical physics. By unveiling the mysteries surrounding challenging problems, we aim to deepen understanding of the very essence of computation and its boundaries. Through this interdisciplinary approach, we aspire to illuminate the intricate tapestry of complexity underpinning the mathematical and physical facets of hard problems.

Authors: Júlia Barberà Rodríguez, Nicolas Gama, Anand Kumar Narayanan, David Joseph

Lattice-based cryptography has emerged as one of the most prominent candidates for post-quantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest non-zero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the $K$-Densest Sub-lattice Problem ($K$-DSP): to find the densest $K$-dimensional sub-lattice of a given lattice. We formulate $K$-DSP as finding the first excited state of a Z-basis Hamiltonian, making $K$-DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and Variational Quantum Algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that $O(KN^2)$ qubits suffice for solving $K$-DSP for $N$ dimensional input lattices. We empirically demonstrate the performance of a Quantum Approximate Optimization Algorithm $K$-DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of $K$-DSP in relation to the SVP, to see if there is reason to build post-quantum cryptography on $K$-DSP. We devise a quantum algorithm that solves $K$-DSP with run-time exponent $(5KN\log{N})/2$. Therefore, for fixed $K$, $K$-DSP is no more than polynomially harder than the SVP.

Authors: Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman

While seemingly undesirable, it is not a surprising fact that there are certain problems for which quantum computers offer no computational advantage over their respective classical counterparts. Moreover, there are problems for which there is no `useful' computational advantage possible with the current quantum hardware. This situation however can be beneficial if we don't want quantum computers to solve certain problems fast - say problems relevant to post-quantum cryptography. In such a situation, we would like to have evidence that it is difficult to solve those problems on quantum computers; but what is their exact complexity?

To do so one has to prove lower bounds, but proving unconditional time lower bounds has never been easy. As a result, resorting to conditional lower bounds has been quite popular in the classical community and is gaining momentum in the quantum community. In this paper, by the use of the QSETH framework [Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT, such as parity-CNFSAT or counting-CNFSAT, and also are able to comment on the non-trivial complexity of approximate-#CNFSAT; both of these have interesting implications about the complexity of (variations of) lattice problems, strong simulation and hitting set problem, and more.

In the process, we explore the QSETH framework in greater detail than was (required and) discussed in the original paper, thus also serving as a useful guide on how to effectively use the QSETH framework.

Authors: Anurag Anshu, Nikolas P. Breuckmann, Quynh T. Nguyen

We define a map from an arbitrary quantum circuit to a local Hamiltonian whose ground state encodes the quantum computation. All previous maps relied on the Feynman-Kitaev construction, which introduces an ancillary `clock register' to track the computational steps. Our construction, on the other hand, relies on injective tensor networks with associated parent Hamiltonians, avoiding the introduction of a clock register. This comes at the cost of the ground state containing only a noisy version of the quantum computation, with independent stochastic noise. We can remedy this - making our construction robust - by using quantum fault tolerance. In addition to the stochastic noise, we show that any state with energy density exponentially small in the circuit depth encodes a noisy version of the quantum computation with adversarial noise. We also show that any `combinatorial state' with energy density polynomially small in depth encodes the quantum computation with adversarial noise. This serves as evidence that any state with energy density polynomially small in depth has a similar property. As an application, we show that contracting injective tensor networks to additive error is BQP-hard. We also discuss the implication of our construction to the quantum PCP conjecture, combining with an observation that QMA verification can be done in logarithmic depth.

Authors: Michael Kompatscher

The subpower membership problem SMP(A) of a finite algebraic structure A asks whether a given partial function from A^k to A can be interpolated by a term operation of A, or not. While this problem can be EXPTIME-complete in general, Willard asked whether it is always solvable in polynomial time if A is a Mal'tsev algebras. In particular, this includes many important structures studied in abstract algebra, such as groups, quasigroups, rings, Boolean algebras. In this paper we give an affirmative answer to Willard's question for a big class of 2-nilpotent Mal'tsev algebras. We furthermore develop tools that might be essential in answering the question for general nilpotent Mal'tsev algebras in the future.

Authors: Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou

Finding ground states of quantum many-body systems is known to be hard for both classical and quantum computers. As a result, when Nature cools a quantum system in a low-temperature thermal bath, the ground state cannot always be found efficiently. Instead, Nature finds a local minimum of the energy. In this work, we study the problem of finding local minima in quantum systems under thermal perturbations. While local minima are much easier to find than ground states, we show that finding a local minimum is computationally hard for classical computers, even when the task is to output a single-qubit observable at any local minimum. In contrast, we prove that a quantum computer can always find a local minimum efficiently using a thermal gradient descent algorithm that mimics the cooling process in Nature. To establish the classical hardness of finding local minima, we consider a family of two-dimensional Hamiltonians such that any problem solvable by polynomial-time quantum algorithms can be reduced to finding ground states of these Hamiltonians. We prove that for such Hamiltonians, all local minima are global minima. Therefore, assuming quantum computation is more powerful than classical computation, finding local minima is classically hard and quantumly easy.

Authors: Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos Parotsidis

The $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for optimizing the popular $k$-means clustering objective and is known to give an $O(\log k)$-approximation in expectation. To obtain higher quality solutions, Lattanzi and Sohler (ICML 2019) proposed augmenting $k$-means++ with $O(k \log \log k)$ local search steps obtained through the $k$-means++ sampling distribution to yield a $c$-approximation to the $k$-means clustering problem, where $c$ is a large absolute constant. Here we generalize and extend their local search algorithm by considering larger and more sophisticated local search neighborhoods hence allowing to swap multiple centers at the same time. Our algorithm achieves a $9 + \varepsilon$ approximation ratio, which is the best possible for local search. Importantly we show that our approach yields substantial practical improvements, we show significant quality improvements over the approach of Lattanzi and Sohler (ICML 2019) on several datasets.

Authors: Lucas Magee, Yusu Wang

Monotone trees - trees with a function defined on their vertices that decreases the further away from a root node one travels, are a natural model for a process that weakens the further one gets from its source. Given an aggregation of monotone trees, one may wish to reconstruct the individual monotone components. A natural representation of such an aggregation would be a graph. While many methods have been developed for extracting hidden graph structure from datasets, which makes obtaining such an aggregation possible, decomposing such graphs into the original monotone trees is algorithmically challenging.

Recently, a polynomial time algorithm has been developed to extract a minimum cardinality collection of monotone trees (M-Tree Set) from a given density tree - but no such algorithm exists for density graphs that may contain cycles. In this work, we prove that extracting such minimum M-Tree Sets of density graphs is NP-Complete. We additionally prove three additional variations of the problem - such as the minimum M-Tree Set such that the intersection between any two monotone trees is either empty or contractible (SM-Tree Set) - are also NP-Complete. We conclude by providing some approximation algorithms, highlighted by a 3-approximation algorithm for computing the minimum SM-Tree Set for density cactus graphs.

Authors: Jingbo Liu

Let $E=\mathbb{Q}\big(\sqrt{-d}\big)$ be an imaginary quadratic field for a square-free positive integer $d$, and let $\mathcal{O}$ be its ring of integers. For each positive integer $m$, let $I_m$ be the free Hermitian lattice over $\mathcal{O}$ with an orthonormal basis, let $\mathfrak{S}_d(1)$ be the set consisting of all positive definite integral unary Hermitian lattices over $\mathcal{O}$ that can be represented by some $I_m$, and let $g_d(1)$ be the least positive integer such that all Hermitian lattices in $\mathfrak{S}_d(1)$ can be uniformly represented by $I_{g_d(1)}$. The main results of this work provide an algorithm to calculate the explicit form of $\mathfrak{S}_d(1)$ and the exact value of $g_d(1)$ for every imaginary quadratic field $E$, which can be viewed as a natural extension of the Pythagoras number in the lattice setting.

Authors: Majid Daliri, Juliana Freire, Christopher Musco, Aécio Santos, Haoxiang Zhang

Recently, Bessa et al. (PODS 2023) showed that sketches based on coordinated weighted sampling theoretically and empirically outperform popular linear sketching methods like Johnson-Lindentrauss projection and CountSketch for the ubiquitous problem of inner product estimation. Despite decades of literature on such sampling methods, this observation seems to have been overlooked. We further develop the finding by presenting and analyzing two alternative sampling-based inner product sketching methods. In contrast to the computationally expensive algorithm in Bessa et al., our methods run in linear time (to compute the sketch) and perform better in practice, significantly beating linear sketching on a variety of tasks. For example, they provide state-of-the-art results for estimating the correlation between columns in unjoined tables, a problem that we show how to reduce to inner product estimation in a black-box way. While based on known sampling techniques (threshold and priority sampling) we introduce significant new theoretical analysis to prove approximation guarantees for our methods.

Authors: Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, Philip G. Warton

We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three $n \times n$ matrices $A$, $B$, and $C$ as input, to decide whether $AB = C$. A classic randomized algorithm by Freivalds (MFCS, 1979) solves MMV in $\widetilde{O}(n^2)$ time, and a longstanding challenge is to (partially) derandomize it while still running in faster than matrix multiplication time (i.e., in $o(n^{\omega})$ time).

To that end, we give two algorithms for MMV in the case where $AB - C$ is sparse. Specifically, when $AB - C$ has at most $O(n^{\delta})$ non-zero entries for a constant $0 \leq \delta < 2$, we give (1) a deterministic $O(n^{\omega - \varepsilon})$-time algorithm for constant $\varepsilon = \varepsilon(\delta) > 0$, and (2) a randomized $\widetilde{O}(n^2)$-time algorithm using $\delta/2 \cdot \log_2 n + O(1)$ random bits. The former algorithm is faster than the deterministic algorithm of K\"{u}nnemann (ESA, 2018) when $\delta \geq 1.056$, and the latter algorithm uses fewer random bits than the algorithm of Kimbrel and Sinha (IPL, 1993), which runs in the same time and uses $\log_2 n + O(1)$ random bits (in turn fewer than Freivalds's algorithm).

We additionally study the complexity of MMV. We first show that all algorithms in a natural class of deterministic linear algebraic algorithms for MMV (including ours) require $\Omega(n^{\omega})$ time. We also show a barrier to proving a super-quadratic running time lower bound for matrix multiplication (and hence MMV) under the Strong Exponential Time Hypothesis (SETH). Finally, we study relationships between natural variants and special cases of MMV (with respect to deterministic $\widetilde{O}(n^2)$-time reductions).

Authors: Yinqi Cai

We study the problem of cutting a length-$n$ string of positive real numbers into $k$ pieces so that every piece has sum at least $b$. The problem can also be phrased as transforming such a string into a new one by merging adjacent numbers. We discuss connections with other problems and present several algorithms in connection with the problem: an $O(n)$-time greedy algorithm, an $O(kn\log n)$-time dynamic programming algorithm, and an $O(n+ k \log n + 2^kk)$-time FPT algorithm for $n-k$ pieces.

Authors: Jan van den Brand, Adam Karczmarz

We present the first non-trivial fully dynamic algorithm maintaining exact single-source distances in unweighted graphs. This resolves an open problem stated by Sankowski [COCOON 2005] and van den Brand and Nanongkai [FOCS 2019]. Previous fully dynamic single-source distances data structures were all approximate, but so far, non-trivial dynamic algorithms for the exact setting could only be ruled out for polynomially weighted graphs (Abboud and Vassilevska Williams, [FOCS 2014]). The exact unweighted case remained the main case for which neither a subquadratic dynamic algorithm nor a quadratic lower bound was known.

Our dynamic algorithm works on directed graphs, is deterministic, and can report a single-source shortest paths tree in subquadratic time as well. Thus we also obtain the first deterministic fully dynamic data structure for reachability (transitive closure) with subquadratic update and query time. This answers an open problem of van den Brand, Nanongkai, and Saranurak [FOCS 2019].

Finally, using the same framework we obtain the first fully dynamic data structure maintaining all-pairs $(1+\epsilon)$-approximate distances within non-trivial sub-$n^\omega$ worst-case update time while supporting optimal-time approximate shortest path reporting at the same time. This data structure is also deterministic and therefore implies the first known non-trivial deterministic worst-case bound for recomputing the transitive closure of a digraph.

Authors: Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities. As a consequence, we obtain the first running time improvement for deterministic algorithms that compute maximum-flow in graphs with polynomial bounded capacities since the work of Goldberg-Rao [J.ACM '98].

Our algorithm builds on the framework of Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS '22] that computes an optimal flow by computing a sequence of $m^{1+o(1)}$-approximate undirected minimum-ratio cycles. We develop a deterministic dynamic graph data-structure to compute such a sequence of minimum-ratio cycles in an amortized $m^{o(1)}$ time per edge update. Our key technical contributions are deterministic analogues of the vertex sparsification and edge sparsification components of the data-structure from Chen et al. For the vertex sparsification component, we give a method to avoid the randomness in Chen et al. which involved sampling random trees to recurse on. For the edge sparsification component, we design a deterministic algorithm that maintains an embedding of a dynamic graph into a sparse spanner. We also show how our dynamic spanner can be applied to give a deterministic data structure that maintains a fully dynamic low-stretch spanning tree on graphs with polynomially bounded edge lengths, with subpolynomial average stretch and subpolynomial amortized time per edge update.

Authors: Andrei Graur, Haotian Jiang, Aaron Sidford

In this paper we study the problem of minimizing a submodular function $f : 2^V \rightarrow \mathbb{R}$ that is guaranteed to have a $k$-sparse minimizer. We give a deterministic algorithm that computes an additive $\epsilon$-approximate minimizer of such $f$ in $\widetilde{O}(\mathsf{poly}(k) \log(|f|/\epsilon))$ parallel depth using a polynomial number of queries to an evaluation oracle of $f$, where $|f| = \max_{S \subseteq V} |f(S)|$. Further, we give a randomized algorithm that computes an exact minimizer of $f$ with high probability using $\widetilde{O}(|V| \cdot \mathsf{poly}(k))$ queries and polynomial time. When $k = \widetilde{O}(1)$, our algorithms use either nearly-constant parallel depth or a nearly-linear number of evaluation oracle queries. All previous algorithms for this problem either use $\Omega(|V|)$ parallel depth or $\Omega(|V|^2)$ queries.

In contrast to state-of-the-art weakly-polynomial and strongly-polynomial time algorithms for SFM, our algorithms use first-order optimization methods, e.g., mirror descent and follow the regularized leader. We introduce what we call {\em sparse dual certificates}, which encode information on the structure of sparse minimizers, and both our parallel and sequential algorithms provide new algorithmic tools for allowing first-order optimization methods to efficiently compute them. Correspondingly, our algorithm does not invoke fast matrix multiplication or general linear system solvers and in this sense is more combinatorial than previous state-of-the-art methods.

I've mentioned Kannan's proof that \(\Sigma_2^p\) does not have \(n^2\) size-circuits before. A similar proof shows that \(\Sigma_2^E = \mathrm{NTIME}^\mathrm{NP}(2^{O(n)})\) does not have polynomial-size circuits in general. You can create a language in the third-level of the exponential-time hierarchy that has maximum circuit complexity. Now if SAT doesn't have poly-size circuits you are done. Otherwise the polynomial-time hierarchy collapses to \(\Sigma_2^p\) which means the exponential-time hierarchy collapse to \(\Sigma_2^E\).

Can you show \(\Sigma_2^E\) has near exponential-size circuit complexity? The above proof doesn't quite work. The problem is that while a polynomial of a polynomial is polynomial, a subexponential function of a subexponential function could be superexponential. You can only make the proof work for circuit-size half-exponential, i.e., function \(f\) such that \(f(f(n)) = 2^{o(n)}\). I don't know of any natural half-exponential functions, but they are much larger than quasi-polynomial and much smaller than exponentials. 

The best known smallest class with an exponential circuit lower bound is for \(\Delta_2^E=E^{\Sigma_2^P}\) due to Miltersen, Vinodchandran and Watanabe from the last millennium. 

Lijie Chen, Shuichi Hirahara and Hanlin Ren have a new paper showing that in fact \(\Sigma_2^E\) does require exponential-size circuits. They have the same bound for smaller classes if you allow a bit of advice. 

You've seen these authors names before in this blog. The future of computational complexity is in good hands.

By Lance Fortnow

With a memorial to William Wulf

Anita Jones will be attending the next 2023 National Academy of Engineering’s annual meeting in Washington DC. Kathryn and I will travel there this weekend. Here is a photo of her winning the Philip Hauge Abelson award in 2012, the top honor of the American Association for the Advancement of Science. (The JFIF original there is sharper; see this for why.)

Unfortunately Anita’s dear husband—Bill Wulf—will not be there. He passed away recently, so she will be helping NAE celebrate his strong contributions to computer science.

We wrote a memorial to Bill last March. I have known both of them well for a long time.

NAE Meeting

Anita will be leading the third item on the 2023 NAE agenda:

• New Member Inductions and Awards Celebration

• Recipients of the Simon Ramo Founders Award and Arthur M. Bueche Award will be recognized, followed by an evening celebratory reception

• Celebration of Life: NAE President William A. “Bill” Wulf, NAE President 1996-2007
  Notes by Cameron Fletcher and Ed Lazowska.

• Technical Forum—Engineering the Future for Sustainability: Measuring and Communicating Our Progress

Added: There will be a live-stream of the Bill Wulf Celebration of Life from 4:00-5:30 ET on Sunday, October 1st. A stream link will appear atop the page https://www.nae.edu/ on that day.

Bill obtained his PhD at the University of Virginia and retired there, but rose through the ranks at CMU beginning in 1968. That is when I knew him first. Here is CMU’s memorial on Bill Wulf.

Some History with Anita

I have a long association with Anita—we were both graduate students at CMU at the same time. I left to my first job at Yale and she stayed on at CMU as her first job. We did work together on security in 1978, which became a book:

Foundations of Secure Computation, Academic Press by Richard DeMillo, Richard Lipton, Anita Jones and David Dobkin.

The book had little impact but was fun to write together.

I visited Anita when she was a second-in-command at the Department of Defense (DoD) at the Pentagon.

She served as the DoD Director of Defense Research and Engineering. As noted there, the director reports directly to the Secretary and Deputy Secretary of Defense. That’s what I mean by a second-in-command. She managed the science and technology program, including the development of new technology. The DoD science and technology program delivers new, technology-based capability to the military. Often the DoD investment in a technology spans a decade because it is not sufficient to do the research; the technology has to be reduced to practice and then applied.

Her office was huge but was filled with bland office furniture. The size was very large, but the quality of the furniture was poor. Not that I am a great expert on quality of office furniture, but it was clearly not expensive. Ken, speaking as a neutral party, infers this conveyed that she was not trying to sell any party on any one proposed system but was actively concerned with the good function (“nuts and bolts”) of all of them.

Open Problems

I look forward to seeing Anita and to hearing her comments about Bill.

[added Fletcher-Lazowska notes and update about the livestream; fixed author: I (KWR) edit the posts but I did not add any more than epsilon content to this one.]

By rjlipton