Last Update

OPML feed of all feeds.

Subscribe to the Atom feed, RSS feed, or follow on Twitter, to stay up to date.

Source on GitHub.

Maintained by Nima Anari, Arnab Bhattacharyya, Gautam Kamath.

Powered by Pluto.

Theory of Computing Report

Friday, September 29

Where do hard problems really exist?

from arXiv: Computational Complexity

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: 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.

On finding dense sub-lattices as low energy states of a quantum Hamiltonian

from arXiv: Computational Complexity

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: 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.

QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more

from arXiv: Computational Complexity

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: 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.

Circuit-to-Hamiltonian from tensor networks and fault tolerance

from arXiv: Computational Complexity

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: 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.

The subpower membership problem of 2-nilpotent algebras

from arXiv: Computational Complexity

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: 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.

Local minima in quantum systems

from arXiv: Computational Complexity

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: 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.

Multi-Swap $k$-Means++

from arXiv: Computational Geometry

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: 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.

Minimum Monotone Tree Decomposition of Density Functions Defined on Graphs

from arXiv: Data Structures and Algorithms

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: 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.

An algorithm for $g$-invariant on unary Hermitian lattices over imaginary quadratic fields

from arXiv: Data Structures and Algorithms

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: 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.

Sampling Methods for Inner Product Sketching

from arXiv: Data Structures and Algorithms

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: 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.

Matrix Multiplication Verification Using Coding Theory

from arXiv: Data Structures and Algorithms

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: 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).

Cut a Numeric String into Required Pieces

from arXiv: Data Structures and Algorithms

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: 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.

Deterministic Fully Dynamic SSSP and More

from arXiv: Data Structures and Algorithms

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, 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.

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow

from arXiv: Data Structures and Algorithms

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: 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.

Sparse Submodular Function Minimization

from arXiv: Data Structures and Algorithms

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.

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.

Thursday, September 28

Half-Exponential No More

from Computational Complexity

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

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

2023 NAE Meeting

from Richard Lipton

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 […]


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

Patterns Induce Injectivity: A New Thinking in Constructing Injective Local Rules of 1D Cellular Automata over $\mathbb{F}_2$

from arXiv: Computational Complexity

Authors: Defu Lin, Weilin Chen, Chen Wang, Junchi Ma, Chao Wang

We discovered that certain patterns called injective patterns remain stable during the revolution process, allowing us to create many reversible CA simply by using them to design the revolution rules. By examining injective patterns, we investigated their structural stability during revolutions. This led us to discover extended patterns and pattern mixtures that can create more reversible cellular automata. Furthermore, our research proposed a new way to study the reversibility of CA by observing the structure of local rule $f$. In this paper, we will explicate our study and propose an efficient method for finding the injective patterns. Our algorithms can find injective rules and generate local rule $f$ by traversing $2^{N}$, instead of $2^{2^{N}}$ to check all injective rules and pick the injective ones.

Authors: Defu Lin, Weilin Chen, Chen Wang, Junchi Ma, Chao Wang

We discovered that certain patterns called injective patterns remain stable during the revolution process, allowing us to create many reversible CA simply by using them to design the revolution rules. By examining injective patterns, we investigated their structural stability during revolutions. This led us to discover extended patterns and pattern mixtures that can create more reversible cellular automata. Furthermore, our research proposed a new way to study the reversibility of CA by observing the structure of local rule $f$. In this paper, we will explicate our study and propose an efficient method for finding the injective patterns. Our algorithms can find injective rules and generate local rule $f$ by traversing $2^{N}$, instead of $2^{2^{N}}$ to check all injective rules and pick the injective ones.

The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems

from arXiv: Computational Complexity

Authors: Manuel Bodirsky, Žaneta Semanišinová, Carsten Lutz

Valued constraint satisfaction problems (VCSPs) are a large class of computational optimisation problems. If the variables of a VCSP take values from a finite domain, then recent results in constraint satisfaction imply that the problem is in P or NP-complete, depending on the set of admitted cost functions. Here we study the larger class of cost functions over countably infinite domains that have an oligomorphic automorphism group. We present a hardness condition based on a generalisation of pp-constructability as known for (classical) CSPs. We also provide a universal-algebraic polynomial-time tractability condition, based on the concept of fractional polymorphisms.

We apply our general theory to study the computational complexity of resilience problems in database theory (under bag semantics). We show how to construct, for every fixed conjunctive query (and more generally for every union of conjunctive queries), a set of cost functions with an oligomorphic automorphism group such that the resulting VCSP is polynomial-time equivalent to the resilience problem; we only require that the query is connected and show that this assumption can be made without loss of generality. For the case where the query is acylic, we obtain a complexity dichotomy of the resilience problem, based on the dichotomy for finite-domain VCSPs. To illustrate the utility of our methods, we exemplarily settle the complexity of a (non-acyclic) conjunctive query whose computational complexity remained open in the literature by verifying that it satisfies our tractability condition. We conjecture that for resilience problems, our hardness and tractability conditions match, which would establish a complexity dichotomy for resilience problems for (unions of) conjunctive queries.

Authors: Manuel Bodirsky, Žaneta Semanišinová, Carsten Lutz

Valued constraint satisfaction problems (VCSPs) are a large class of computational optimisation problems. If the variables of a VCSP take values from a finite domain, then recent results in constraint satisfaction imply that the problem is in P or NP-complete, depending on the set of admitted cost functions. Here we study the larger class of cost functions over countably infinite domains that have an oligomorphic automorphism group. We present a hardness condition based on a generalisation of pp-constructability as known for (classical) CSPs. We also provide a universal-algebraic polynomial-time tractability condition, based on the concept of fractional polymorphisms.

We apply our general theory to study the computational complexity of resilience problems in database theory (under bag semantics). We show how to construct, for every fixed conjunctive query (and more generally for every union of conjunctive queries), a set of cost functions with an oligomorphic automorphism group such that the resulting VCSP is polynomial-time equivalent to the resilience problem; we only require that the query is connected and show that this assumption can be made without loss of generality. For the case where the query is acylic, we obtain a complexity dichotomy of the resilience problem, based on the dichotomy for finite-domain VCSPs. To illustrate the utility of our methods, we exemplarily settle the complexity of a (non-acyclic) conjunctive query whose computational complexity remained open in the literature by verifying that it satisfies our tractability condition. We conjecture that for resilience problems, our hardness and tractability conditions match, which would establish a complexity dichotomy for resilience problems for (unions of) conjunctive queries.

Orbit closures, stabilizer limits and intermediate $G$-varieties

from arXiv: Computational Complexity

Authors: Bharat Adsul, Milind Sohoni, K V Subrahmanyam

In this paper we study the orbit closure problem for a reductive group $G\subseteq GL(X)$ acting on a finite dimensional vector space $V$ over ${\mathbb C}$. We assume that the center of $GL(X)$ lies within $G$ and acts on $V$ through a fixed non-trivial character. We study points $y,z\in V$ where (i) $z$ is obtained as the leading term of the action of a 1-parameter subgroup $\lambda (t)\subseteq G$ on $y$, and (ii) $y$ and $z$ have large distinctive stabilizers $K,H \subseteq G$. Let $O(z)$ (resp. $O(y)$) denote the $G$-orbits of $z$ (resp. $y$), and $\overline{O(z)}$ (resp. $\overline{O(y)}$) their closures, then (i) implies that $z\in \overline{O(y)}$. We address the question: under what conditions can (i) and (ii) be simultaneously satisfied, i.e, there exists a 1-PS $\lambda \subseteq G$ for which $z$ is observed as a limit of $y$.

Using $\lambda$, we develop a leading term analysis which applies to $V$ as well as to ${\cal G}= Lie(G)$ the Lie algebra of $G$ and its subalgebras ${\cal K}$ and ${\cal H}$, the Lie algebras of $K$ and $H$ respectively. Through this we construct the Lie algebra $\hat{\cal K} \subseteq {\cal H}$ which connects $y$ and $z$ through their Lie algebras. We develop the properties of $\hat{\cal K}$ and relate it to the action of ${\cal H}$ on $\overline{N}=V/T_z O(z)$, the normal slice to the orbit $O(z)$. Next, we examine the possibility of {\em intermediate $G$-varieties} $W$ which lie between the orbit closures of $z$ and $y$, i.e. $\overline{O(z)} \subsetneq W \subsetneq O(y)$. These intermediate varieties are constructed using the grading obtained from $\lambda $ by its action on $V$ and ${\cal G}$.

The paper hopes to contribute to the Geometric Complexity Theory approach of addressing problems in computational complexity in theoretical computer science.

Authors: Bharat Adsul, Milind Sohoni, K V Subrahmanyam

In this paper we study the orbit closure problem for a reductive group $G\subseteq GL(X)$ acting on a finite dimensional vector space $V$ over ${\mathbb C}$. We assume that the center of $GL(X)$ lies within $G$ and acts on $V$ through a fixed non-trivial character. We study points $y,z\in V$ where (i) $z$ is obtained as the leading term of the action of a 1-parameter subgroup $\lambda (t)\subseteq G$ on $y$, and (ii) $y$ and $z$ have large distinctive stabilizers $K,H \subseteq G$. Let $O(z)$ (resp. $O(y)$) denote the $G$-orbits of $z$ (resp. $y$), and $\overline{O(z)}$ (resp. $\overline{O(y)}$) their closures, then (i) implies that $z\in \overline{O(y)}$. We address the question: under what conditions can (i) and (ii) be simultaneously satisfied, i.e, there exists a 1-PS $\lambda \subseteq G$ for which $z$ is observed as a limit of $y$.

Using $\lambda$, we develop a leading term analysis which applies to $V$ as well as to ${\cal G}= Lie(G)$ the Lie algebra of $G$ and its subalgebras ${\cal K}$ and ${\cal H}$, the Lie algebras of $K$ and $H$ respectively. Through this we construct the Lie algebra $\hat{\cal K} \subseteq {\cal H}$ which connects $y$ and $z$ through their Lie algebras. We develop the properties of $\hat{\cal K}$ and relate it to the action of ${\cal H}$ on $\overline{N}=V/T_z O(z)$, the normal slice to the orbit $O(z)$. Next, we examine the possibility of {\em intermediate $G$-varieties} $W$ which lie between the orbit closures of $z$ and $y$, i.e. $\overline{O(z)} \subsetneq W \subsetneq O(y)$. These intermediate varieties are constructed using the grading obtained from $\lambda $ by its action on $V$ and ${\cal G}$.

The paper hopes to contribute to the Geometric Complexity Theory approach of addressing problems in computational complexity in theoretical computer science.

Voxel Graph Operators: Topological Voxelization, Graph Generation, and Derivation of Discrete Differential Operators from Voxel Complexes

from arXiv: Computational Geometry

Authors: Pirouz Nourian, Shervin Azadi

In this paper, we present a novel workflow consisting of algebraic algorithms and data structures for fast and topologically accurate conversion of vector data models such as Boundary Representations into voxels (topological voxelization); spatially indexing them; constructing connectivity graphs from voxels; and constructing a coherent set of multivariate differential and integral operators from these graphs. Topological Voxelization is revisited and presented in the paper as a reversible mapping of geometric models from $\mathbb{R}^3$ to $\mathbb{Z}^3$ to $\mathbb{N}^3$ and eventually to an index space created by Morton Codes in $\mathbb{N}$ while ensuring the topological validity of the voxel models; namely their topological thinness and their geometrical consistency. In addition, we present algorithms for constructing graphs and hyper-graph connectivity models on voxel data for graph traversal and field interpolations and utilize them algebraically in elegantly discretizing differential and integral operators for geometric, graphical, or spatial analyses and digital simulations. The multi-variate differential and integral operators presented in this paper can be used particularly in the formulation of Partial Differential Equations for physics simulations.

Authors: Pirouz Nourian, Shervin Azadi

In this paper, we present a novel workflow consisting of algebraic algorithms and data structures for fast and topologically accurate conversion of vector data models such as Boundary Representations into voxels (topological voxelization); spatially indexing them; constructing connectivity graphs from voxels; and constructing a coherent set of multivariate differential and integral operators from these graphs. Topological Voxelization is revisited and presented in the paper as a reversible mapping of geometric models from $\mathbb{R}^3$ to $\mathbb{Z}^3$ to $\mathbb{N}^3$ and eventually to an index space created by Morton Codes in $\mathbb{N}$ while ensuring the topological validity of the voxel models; namely their topological thinness and their geometrical consistency. In addition, we present algorithms for constructing graphs and hyper-graph connectivity models on voxel data for graph traversal and field interpolations and utilize them algebraically in elegantly discretizing differential and integral operators for geometric, graphical, or spatial analyses and digital simulations. The multi-variate differential and integral operators presented in this paper can be used particularly in the formulation of Partial Differential Equations for physics simulations.

The Maximum Cover with Rotating Field of View

from arXiv: Computational Geometry

Authors: Igor Potapov, Jason Ralph, Theofilos Triommatis

Imagine a polygon-shaped platform $P$ and only one static spotlight outside $P$; which direction should the spotlight face to light most of $P$? This problem occurs in maximising the visibility, as well as in limiting the uncertainty in localisation problems. More formally, we define the following maximum cover problem: "Given a convex polygon $P$ and a Field Of View (FOV) with a given centre and inner angle $\phi$; find the direction (an angle of rotation $\theta$) of the FOV such that the intersection between the FOV and $P$ has the maximum area". In this paper, we provide the theoretical foundation for the analysis of the maximum cover with a rotating field of view. The main challenge is that the function of the area $A_{\phi}(\theta)$, with the angle of rotation $\theta$ and the fixed inner angle $\phi$, cannot be approximated directly. We found an alternative way to express it by various compositions of a function $A_{\theta}(\phi)$ (with a restricted inner angle $\phi$ and a fixed direction $\theta$). We show that $A_{\theta}(\phi)$ has an analytical solution in the special case of a two-sector intersection and later provides a constrictive solution for the original problem. Since the optimal solution is a real number, we develop an algorithm that approximates the direction of the field of view, with precision $\varepsilon$, and complexity $\mathcal{O}(n(\log{n}+(\log{\varepsilon})/\phi))$.

Authors: Igor Potapov, Jason Ralph, Theofilos Triommatis

Imagine a polygon-shaped platform $P$ and only one static spotlight outside $P$; which direction should the spotlight face to light most of $P$? This problem occurs in maximising the visibility, as well as in limiting the uncertainty in localisation problems. More formally, we define the following maximum cover problem: "Given a convex polygon $P$ and a Field Of View (FOV) with a given centre and inner angle $\phi$; find the direction (an angle of rotation $\theta$) of the FOV such that the intersection between the FOV and $P$ has the maximum area". In this paper, we provide the theoretical foundation for the analysis of the maximum cover with a rotating field of view. The main challenge is that the function of the area $A_{\phi}(\theta)$, with the angle of rotation $\theta$ and the fixed inner angle $\phi$, cannot be approximated directly. We found an alternative way to express it by various compositions of a function $A_{\theta}(\phi)$ (with a restricted inner angle $\phi$ and a fixed direction $\theta$). We show that $A_{\theta}(\phi)$ has an analytical solution in the special case of a two-sector intersection and later provides a constrictive solution for the original problem. Since the optimal solution is a real number, we develop an algorithm that approximates the direction of the field of view, with precision $\varepsilon$, and complexity $\mathcal{O}(n(\log{n}+(\log{\varepsilon})/\phi))$.

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time

from arXiv: Data Structures and Algorithms

Authors: V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

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.

Authors: V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

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.

Generalised 3D Morton and Hilbert Orderings

from arXiv: Data Structures and Algorithms

Authors: David Walker

This document describes algorithms for generating general Morton and Hilbert orderings for three-dimensional data volumes.

Authors: David Walker

This document describes algorithms for generating general Morton and Hilbert orderings for three-dimensional data volumes.

The $st$-Planar Edge Completion Problem is Fixed-Parameter Tractable

from arXiv: Data Structures and Algorithms

Authors: Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov

The problem of deciding whether a biconnected planar digraph $G=(V,E)$ can be augmented to become an $st$-planar graph by adding a set of oriented edges $E' \subseteq V \times V$ is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set $E'$.

Authors: Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov

The problem of deciding whether a biconnected planar digraph $G=(V,E)$ can be augmented to become an $st$-planar graph by adding a set of oriented edges $E' \subseteq V \times V$ is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set $E'$.

Composable Coresets for Determinant Maximization: Greedy is Almost Optimal

from arXiv: Data Structures and Algorithms

Authors: Siddharth Gollapudi, Sepideh Mahabadi, Varun Sivashankar

Given a set of $n$ vectors in $\mathbb{R}^d$, the goal of the \emph{determinant maximization} problem is to pick $k$ vectors with the maximum volume. Determinant maximization is the MAP-inference task for determinantal point processes (DPP) and has recently received considerable attention for modeling diversity. As most applications for the problem use large amounts of data, this problem has been studied in the relevant \textit{composable coreset} setting. In particular, [Indyk-Mahabadi-OveisGharan-Rezaei--SODA'20, ICML'19] showed that one can get composable coresets with optimal approximation factor of $\tilde O(k)^k$ for the problem, and that a local search algorithm achieves an almost optimal approximation guarantee of $O(k)^{2k}$. In this work, we show that the widely-used Greedy algorithm also provides composable coresets with an almost optimal approximation factor of $O(k)^{3k}$, which improves over the previously known guarantee of $C^{k^2}$, and supports the prior experimental results showing the practicality of the greedy algorithm as a coreset. Our main result follows by showing a local optimality property for Greedy: swapping a single point from the greedy solution with a vector that was not picked by the greedy algorithm can increase the volume by a factor of at most $(1+\sqrt{k})$. This is tight up to the additive constant $1$. Finally, our experiments show that the local optimality of the greedy algorithm is even lower than the theoretical bound on real data sets.

Authors: Siddharth Gollapudi, Sepideh Mahabadi, Varun Sivashankar

Given a set of $n$ vectors in $\mathbb{R}^d$, the goal of the \emph{determinant maximization} problem is to pick $k$ vectors with the maximum volume. Determinant maximization is the MAP-inference task for determinantal point processes (DPP) and has recently received considerable attention for modeling diversity. As most applications for the problem use large amounts of data, this problem has been studied in the relevant \textit{composable coreset} setting. In particular, [Indyk-Mahabadi-OveisGharan-Rezaei--SODA'20, ICML'19] showed that one can get composable coresets with optimal approximation factor of $\tilde O(k)^k$ for the problem, and that a local search algorithm achieves an almost optimal approximation guarantee of $O(k)^{2k}$. In this work, we show that the widely-used Greedy algorithm also provides composable coresets with an almost optimal approximation factor of $O(k)^{3k}$, which improves over the previously known guarantee of $C^{k^2}$, and supports the prior experimental results showing the practicality of the greedy algorithm as a coreset. Our main result follows by showing a local optimality property for Greedy: swapping a single point from the greedy solution with a vector that was not picked by the greedy algorithm can increase the volume by a factor of at most $(1+\sqrt{k})$. This is tight up to the additive constant $1$. Finally, our experiments show that the local optimality of the greedy algorithm is even lower than the theoretical bound on real data sets.

On the Power of SVD in the Stochastic Block Model

from arXiv: Data Structures and Algorithms

Authors: Xinyu Mao, Jiapeng Zhang

A popular heuristic method for improving clustering results is to apply dimensionality reduction before running clustering algorithms. It has been observed that spectral-based dimensionality reduction tools, such as PCA or SVD, improve the performance of clustering algorithms in many applications. This phenomenon indicates that spectral method not only serves as a dimensionality reduction tool, but also contributes to the clustering procedure in some sense. It is an interesting question to understand the behavior of spectral steps in clustering problems.

As an initial step in this direction, this paper studies the power of vanilla-SVD algorithm in the stochastic block model (SBM). We show that, in the symmetric setting, vanilla-SVD algorithm recovers all clusters correctly. This result answers an open question posed by Van Vu (Combinatorics Probability and Computing, 2018) in the symmetric setting.

Authors: Xinyu Mao, Jiapeng Zhang

A popular heuristic method for improving clustering results is to apply dimensionality reduction before running clustering algorithms. It has been observed that spectral-based dimensionality reduction tools, such as PCA or SVD, improve the performance of clustering algorithms in many applications. This phenomenon indicates that spectral method not only serves as a dimensionality reduction tool, but also contributes to the clustering procedure in some sense. It is an interesting question to understand the behavior of spectral steps in clustering problems.

As an initial step in this direction, this paper studies the power of vanilla-SVD algorithm in the stochastic block model (SBM). We show that, in the symmetric setting, vanilla-SVD algorithm recovers all clusters correctly. This result answers an open question posed by Van Vu (Combinatorics Probability and Computing, 2018) in the symmetric setting.

Multi-dimensional Data Quick Query for Blockchain-based Federated Learning

from arXiv: Data Structures and Algorithms

Authors: Jiaxi Yang, Sheng Cao, Peng xiangLi, Xiong Li, Xiaosong Zhang

Due to the drawbacks of Federated Learning (FL) such as vulnerability of a single central server, centralized federated learning is shifting to decentralized federated learning, a paradigm which takes the advantages of blockchain. A key enabler for adoption of blockchain-based federated learning is how to select suitable participants to train models collaboratively. Selecting participants by storing and querying the metadata of data owners on blockchain could ensure the reliability of selected data owners, which is helpful to obtain high-quality models in FL. However, querying multi-dimensional metadata on blockchain needs to traverse every transaction in each block, making the query time-consuming. An efficient query method for multi-dimensional metadata in the blockchain for selecting participants in FL is absent and challenging. In this paper, we propose a novel data structure to improve the query efficiency within each block named MerkleRB-Tree. In detail, we leverage Minimal Bounding Rectangle(MBR) and bloom-filters for the query process of multi-dimensional continuous-valued attributes and discrete-valued attributes respectively. Furthermore, we migrate the idea of the skip list along with an MBR and a bloom filter at the head of each block to enhance the query efficiency for inter-blocks. The performance analysis and extensive evaluation results on the benchmark dataset demonstrate the superiority of our method in blockchain-based FL.

Authors: Jiaxi Yang, Sheng Cao, Peng xiangLi, Xiong Li, Xiaosong Zhang

Due to the drawbacks of Federated Learning (FL) such as vulnerability of a single central server, centralized federated learning is shifting to decentralized federated learning, a paradigm which takes the advantages of blockchain. A key enabler for adoption of blockchain-based federated learning is how to select suitable participants to train models collaboratively. Selecting participants by storing and querying the metadata of data owners on blockchain could ensure the reliability of selected data owners, which is helpful to obtain high-quality models in FL. However, querying multi-dimensional metadata on blockchain needs to traverse every transaction in each block, making the query time-consuming. An efficient query method for multi-dimensional metadata in the blockchain for selecting participants in FL is absent and challenging. In this paper, we propose a novel data structure to improve the query efficiency within each block named MerkleRB-Tree. In detail, we leverage Minimal Bounding Rectangle(MBR) and bloom-filters for the query process of multi-dimensional continuous-valued attributes and discrete-valued attributes respectively. Furthermore, we migrate the idea of the skip list along with an MBR and a bloom filter at the head of each block to enhance the query efficiency for inter-blocks. The performance analysis and extensive evaluation results on the benchmark dataset demonstrate the superiority of our method in blockchain-based FL.

Frequency and cardinality recovery from sketched data: a novel approach bridging Bayesian and frequentist views

from arXiv: Data Structures and Algorithms

Authors: Mario Beraha, Stefano Favaro, Matteo Sesia

We study how to recover the frequency of a symbol in a large discrete data set, using only a compressed representation, or sketch, of those data obtained via random hashing. This is a classical problem in computer science, with various algorithms available, such as the count-min sketch. However, these algorithms often assume that the data are fixed, leading to overly conservative and potentially inaccurate estimates when dealing with randomly sampled data. In this paper, we consider the sketched data as a random sample from an unknown distribution, and then we introduce novel estimators that improve upon existing approaches. Our method combines Bayesian nonparametric and classical (frequentist) perspectives, addressing their unique limitations to provide a principled and practical solution. Additionally, we extend our method to address the related but distinct problem of cardinality recovery, which consists of estimating the total number of distinct objects in the data set. We validate our method on synthetic and real data, comparing its performance to state-of-the-art alternatives.

Authors: Mario Beraha, Stefano Favaro, Matteo Sesia

We study how to recover the frequency of a symbol in a large discrete data set, using only a compressed representation, or sketch, of those data obtained via random hashing. This is a classical problem in computer science, with various algorithms available, such as the count-min sketch. However, these algorithms often assume that the data are fixed, leading to overly conservative and potentially inaccurate estimates when dealing with randomly sampled data. In this paper, we consider the sketched data as a random sample from an unknown distribution, and then we introduce novel estimators that improve upon existing approaches. Our method combines Bayesian nonparametric and classical (frequentist) perspectives, addressing their unique limitations to provide a principled and practical solution. Additionally, we extend our method to address the related but distinct problem of cardinality recovery, which consists of estimating the total number of distinct objects in the data set. We validate our method on synthetic and real data, comparing its performance to state-of-the-art alternatives.

Computing Permanents and Counting Hamiltonian Cycles Faster

from arXiv: Data Structures and Algorithms

Authors: Baitian Li

We show that the permanent of an $n\times n$ matrix of $\operatorname{poly}(n)$-bit integers and the number of Hamiltonian cycles of an $n$-vertex graph can both be computed in time $2^{n-\Omega(\sqrt{n})}$, improving an earlier algorithm of Bj\"orklund, Kaski, and Williams (Algorithmica 2019) that runs in time $2^{n - \Omega\left(\sqrt{n/\log \log n}\right)}$.

A key tool of our approach is to design a data structure that supports fast "$r$-order evaluation" of permanent and Hamiltonian cycles, which cooperates with the new approach on multivariate multipoint evaluation by Bhargava, Ghosh, Guo, Kumar, and Umans (FOCS 2022).

Authors: Baitian Li

We show that the permanent of an $n\times n$ matrix of $\operatorname{poly}(n)$-bit integers and the number of Hamiltonian cycles of an $n$-vertex graph can both be computed in time $2^{n-\Omega(\sqrt{n})}$, improving an earlier algorithm of Bj\"orklund, Kaski, and Williams (Algorithmica 2019) that runs in time $2^{n - \Omega\left(\sqrt{n/\log \log n}\right)}$.

A key tool of our approach is to design a data structure that supports fast "$r$-order evaluation" of permanent and Hamiltonian cycles, which cooperates with the new approach on multivariate multipoint evaluation by Bhargava, Ghosh, Guo, Kumar, and Umans (FOCS 2022).

Fast Locality Sensitive Hashing with Theoretical Guarantee

from arXiv: Data Structures and Algorithms

Authors: Zongyuan Tan, Hongya Wang, Bo Xu, Minjie Luo, Ming Du

Locality-sensitive hashing (LSH) is an effective randomized technique widely used in many machine learning tasks. The cost of hashing is proportional to data dimensions, and thus often the performance bottleneck when dimensionality is high and the number of hash functions involved is large. Surprisingly, however, little work has been done to improve the efficiency of LSH computation. In this paper, we design a simple yet efficient LSH scheme, named FastLSH, under l2 norm. By combining random sampling and random projection, FastLSH reduces the time complexity from O(n) to O(m) (m<n), where n is the data dimensionality and m is the number of sampled dimensions. Moreover, FastLSH has provable LSH property, which distinguishes it from the non-LSH fast sketches. We conduct comprehensive experiments over a collection of real and synthetic datasets for the nearest neighbor search task. Experimental results demonstrate that FastLSH is on par with the state-of-the-arts in terms of answer quality, space occupation and query efficiency, while enjoying up to 80x speedup in hash function evaluation. We believe that FastLSH is a promising alternative to the classic LSH scheme.

Authors: Zongyuan Tan, Hongya Wang, Bo Xu, Minjie Luo, Ming Du

Locality-sensitive hashing (LSH) is an effective randomized technique widely used in many machine learning tasks. The cost of hashing is proportional to data dimensions, and thus often the performance bottleneck when dimensionality is high and the number of hash functions involved is large. Surprisingly, however, little work has been done to improve the efficiency of LSH computation. In this paper, we design a simple yet efficient LSH scheme, named FastLSH, under l2 norm. By combining random sampling and random projection, FastLSH reduces the time complexity from O(n) to O(m) (m<n), where n is the data dimensionality and m is the number of sampled dimensions. Moreover, FastLSH has provable LSH property, which distinguishes it from the non-LSH fast sketches. We conduct comprehensive experiments over a collection of real and synthetic datasets for the nearest neighbor search task. Experimental results demonstrate that FastLSH is on par with the state-of-the-arts in terms of answer quality, space occupation and query efficiency, while enjoying up to 80x speedup in hash function evaluation. We believe that FastLSH is a promising alternative to the classic LSH scheme.

Sidestepping Barriers for Dominating Set in Parameterized Complexity

from arXiv: Data Structures and Algorithms

Authors: Ioannis Koutis, Michał Włodarczyk, Meirav Zehavi

We study the classic {\sc Dominating Set} problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers by the incorporation of either approximation or larger parameterization. Our results span several parameterization regimes, including: (i,ii,iii) time/ratio-tradeoff for the parameters {\em treewidth}, {\em vertex modulator to constant treewidth} and {\em solution size}; (iv,v) FPT-algorithms for the parameters {\em vertex cover number} and {\em feedback edge set number}; and (vi) compression for the parameter {\em feedback edge set number}.

Authors: Ioannis Koutis, Michał Włodarczyk, Meirav Zehavi

We study the classic {\sc Dominating Set} problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers by the incorporation of either approximation or larger parameterization. Our results span several parameterization regimes, including: (i,ii,iii) time/ratio-tradeoff for the parameters {\em treewidth}, {\em vertex modulator to constant treewidth} and {\em solution size}; (iv,v) FPT-algorithms for the parameters {\em vertex cover number} and {\em feedback edge set number}; and (vi) compression for the parameter {\em feedback edge set number}.

Wednesday, September 27

TR23-146 | On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model | Oded Goldreich, Laliv Tauber

from ECCC Papers

We consider the problem of testing isomorphism to a fixed graph in the bounded-degree graph model. Our main result is that, for almost all $d$-regular $n$-vertex graphs $H$, testing isomorphism to $H$ can be done using $\tildeO({\sqrt n})$ queries. This result is shown to be optimal (up to a polylog factor) by a matching lower bound, which also holds for almost all graphs $H$. The performance of our tester depends on natural graph parameters of the fixed ($n$-vertex) graph $H$ such as its diameter and the minimum radius of ``distinguishing neighborhoods'' (i.e., the minimum $r=r(n)$ such that the ``$r$-neighborhoods'' of the $n$ different vertices are pairwise non-isomorphic).
We consider the problem of testing isomorphism to a fixed graph in the bounded-degree graph model. Our main result is that, for almost all $d$-regular $n$-vertex graphs $H$, testing isomorphism to $H$ can be done using $\tildeO({\sqrt n})$ queries. This result is shown to be optimal (up to a polylog factor) by a matching lower bound, which also holds for almost all graphs $H$. The performance of our tester depends on natural graph parameters of the fixed ($n$-vertex) graph $H$ such as its diameter and the minimum radius of ``distinguishing neighborhoods'' (i.e., the minimum $r=r(n)$ such that the ``$r$-neighborhoods'' of the $n$ different vertices are pairwise non-isomorphic).

On the Tensor Representation and Algebraic Homomorphism of the Neural State Turing Machine

from arXiv: Computational Complexity

Authors: Ankur Mali, Alexander Ororbia, Daniel Kifer, Lee Giles

Recurrent neural networks (RNNs) and transformers have been shown to be Turing-complete, but this result assumes infinite precision in their hidden representations, positional encodings for transformers, and unbounded computation time in general. In practical applications, however, it is crucial to have real-time models that can recognize Turing complete grammars in a single pass. To address this issue and to better understand the true computational power of artificial neural networks (ANNs), we introduce a new class of recurrent models called the neural state Turing machine (NSTM). The NSTM has bounded weights and finite-precision connections and can simulate any Turing Machine in real-time. In contrast to prior work that assumes unbounded time and precision in weights, to demonstrate equivalence with TMs, we prove that a $13$-neuron bounded tensor RNN, coupled with third-order synapses, can model any TM class in real-time. Furthermore, under the Markov assumption, we provide a new theoretical bound for a non-recurrent network augmented with memory, showing that a tensor feedforward network with $25$th-order finite precision weights is equivalent to a universal TM.

Authors: Ankur Mali, Alexander Ororbia, Daniel Kifer, Lee Giles

Recurrent neural networks (RNNs) and transformers have been shown to be Turing-complete, but this result assumes infinite precision in their hidden representations, positional encodings for transformers, and unbounded computation time in general. In practical applications, however, it is crucial to have real-time models that can recognize Turing complete grammars in a single pass. To address this issue and to better understand the true computational power of artificial neural networks (ANNs), we introduce a new class of recurrent models called the neural state Turing machine (NSTM). The NSTM has bounded weights and finite-precision connections and can simulate any Turing Machine in real-time. In contrast to prior work that assumes unbounded time and precision in weights, to demonstrate equivalence with TMs, we prove that a $13$-neuron bounded tensor RNN, coupled with third-order synapses, can model any TM class in real-time. Furthermore, under the Markov assumption, we provide a new theoretical bound for a non-recurrent network augmented with memory, showing that a tensor feedforward network with $25$th-order finite precision weights is equivalent to a universal TM.

On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks

from arXiv: Computational Complexity

Authors: Ankur Mali, Alexander Ororbia, Daniel Kifer, Lee Giles

Artificial neural networks (ANNs) with recurrence and self-attention have been shown to be Turing-complete (TC). However, existing work has shown that these ANNs require multiple turns or unbounded computation time, even with unbounded precision in weights, in order to recognize TC grammars. However, under constraints such as fixed or bounded precision neurons and time, ANNs without memory are shown to struggle to recognize even context-free languages. In this work, we extend the theoretical foundation for the $2^{nd}$-order recurrent network ($2^{nd}$ RNN) and prove there exists a class of a $2^{nd}$ RNN that is Turing-complete with bounded time. This model is capable of directly encoding a transition table into its recurrent weights, enabling bounded time computation and is interpretable by design. We also demonstrate that $2$nd order RNNs, without memory, under bounded weights and time constraints, outperform modern-day models such as vanilla RNNs and gated recurrent units in recognizing regular grammars. We provide an upper bound and a stability analysis on the maximum number of neurons required by $2$nd order RNNs to recognize any class of regular grammar. Extensive experiments on the Tomita grammars support our findings, demonstrating the importance of tensor connections in crafting computationally efficient RNNs. Finally, we show $2^{nd}$ order RNNs are also interpretable by extraction and can extract state machines with higher success rates as compared to first-order RNNs. Our results extend the theoretical foundations of RNNs and offer promising avenues for future explainable AI research.

Authors: Ankur Mali, Alexander Ororbia, Daniel Kifer, Lee Giles

Artificial neural networks (ANNs) with recurrence and self-attention have been shown to be Turing-complete (TC). However, existing work has shown that these ANNs require multiple turns or unbounded computation time, even with unbounded precision in weights, in order to recognize TC grammars. However, under constraints such as fixed or bounded precision neurons and time, ANNs without memory are shown to struggle to recognize even context-free languages. In this work, we extend the theoretical foundation for the $2^{nd}$-order recurrent network ($2^{nd}$ RNN) and prove there exists a class of a $2^{nd}$ RNN that is Turing-complete with bounded time. This model is capable of directly encoding a transition table into its recurrent weights, enabling bounded time computation and is interpretable by design. We also demonstrate that $2$nd order RNNs, without memory, under bounded weights and time constraints, outperform modern-day models such as vanilla RNNs and gated recurrent units in recognizing regular grammars. We provide an upper bound and a stability analysis on the maximum number of neurons required by $2$nd order RNNs to recognize any class of regular grammar. Extensive experiments on the Tomita grammars support our findings, demonstrating the importance of tensor connections in crafting computationally efficient RNNs. Finally, we show $2^{nd}$ order RNNs are also interpretable by extraction and can extract state machines with higher success rates as compared to first-order RNNs. Our results extend the theoretical foundations of RNNs and offer promising avenues for future explainable AI research.

Instance complexity of Boolean functions

from arXiv: Computational Complexity

Authors: Alison Hsiang-Hsuan Liu, Nikhil S. Mande

In the area of query complexity of Boolean functions, the most widely studied cost measure of an algorithm is the worst-case number of queries made by it on an input. Motivated by the most natural cost measure studied in online algorithms, the competitive ratio, we consider a different cost measure for query algorithms for Boolean functions that captures the ratio of the cost of the algorithm and the cost of an optimal algorithm that knows the input in advance. The cost of an algorithm is its largest cost over all inputs. Grossman, Komargodski and Naor [ITCS'20] introduced this measure for Boolean functions, and dubbed it instance complexity. Grossman et al. showed, among other results, that monotone Boolean functions with instance complexity 1 are precisely those that depend on one or two variables.

We complement the above-mentioned result of Grossman et al. by completely characterizing the instance complexity of symmetric Boolean functions. As a corollary we conclude that the only symmetric Boolean functions with instance complexity 1 are the Parity function and its complement. We also study the instance complexity of some graph properties like Connectivity and k-clique containment.

In all the Boolean functions we study above, and those studied by Grossman et al., the instance complexity turns out to be the ratio of query complexity to minimum certificate complexity. It is a natural question to ask if this is the correct bound for all Boolean functions. We show a negative answer in a very strong sense, by analyzing the instance complexity of the Greater-Than and Odd-Max-Bit functions. We show that the above-mentioned ratio is linear in the input size for both of these functions, while we exhibit algorithms for which the instance complexity is a constant.

Authors: Alison Hsiang-Hsuan Liu, Nikhil S. Mande

In the area of query complexity of Boolean functions, the most widely studied cost measure of an algorithm is the worst-case number of queries made by it on an input. Motivated by the most natural cost measure studied in online algorithms, the competitive ratio, we consider a different cost measure for query algorithms for Boolean functions that captures the ratio of the cost of the algorithm and the cost of an optimal algorithm that knows the input in advance. The cost of an algorithm is its largest cost over all inputs. Grossman, Komargodski and Naor [ITCS'20] introduced this measure for Boolean functions, and dubbed it instance complexity. Grossman et al. showed, among other results, that monotone Boolean functions with instance complexity 1 are precisely those that depend on one or two variables.

We complement the above-mentioned result of Grossman et al. by completely characterizing the instance complexity of symmetric Boolean functions. As a corollary we conclude that the only symmetric Boolean functions with instance complexity 1 are the Parity function and its complement. We also study the instance complexity of some graph properties like Connectivity and k-clique containment.

In all the Boolean functions we study above, and those studied by Grossman et al., the instance complexity turns out to be the ratio of query complexity to minimum certificate complexity. It is a natural question to ask if this is the correct bound for all Boolean functions. We show a negative answer in a very strong sense, by analyzing the instance complexity of the Greater-Than and Odd-Max-Bit functions. We show that the above-mentioned ratio is linear in the input size for both of these functions, while we exhibit algorithms for which the instance complexity is a constant.

Generative Escher Meshes

from arXiv: Computational Geometry

Authors: Noam Aigerman, Thibault Groueix

This paper proposes a fully-automatic, text-guided generative method for producing periodic, repeating, tile-able 2D art, such as the one seen on floors, mosaics, ceramics, and the work of M.C. Escher. In contrast to the standard concept of a seamless texture, i.e., square images that are seamless when tiled, our method generates non-square tilings which comprise solely of repeating copies of the same object. It achieves this by optimizing both geometry and color of a 2D mesh, in order to generate a non-square tile in the shape and appearance of the desired object, with close to no additional background details. We enable geometric optimization of tilings by our key technical contribution: an unconstrained, differentiable parameterization of the space of all possible tileable shapes for a given symmetry group. Namely, we prove that modifying the laplacian used in a 2D mesh-mapping technique - Orbifold Tutte Embedding - can achieve all possible tiling configurations for a chosen planar symmetry group. We thus consider both the mesh's tile-shape and its texture as optimizable parameters, rendering the textured mesh via a differentiable renderer. We leverage a trained image diffusion model to define a loss on the resulting image, thereby updating the mesh's parameters based on its appearance matching the text prompt. We show our method is able to produce plausible, appealing results, with non-trivial tiles, for a variety of different periodic tiling patterns.

Authors: Noam Aigerman, Thibault Groueix

This paper proposes a fully-automatic, text-guided generative method for producing periodic, repeating, tile-able 2D art, such as the one seen on floors, mosaics, ceramics, and the work of M.C. Escher. In contrast to the standard concept of a seamless texture, i.e., square images that are seamless when tiled, our method generates non-square tilings which comprise solely of repeating copies of the same object. It achieves this by optimizing both geometry and color of a 2D mesh, in order to generate a non-square tile in the shape and appearance of the desired object, with close to no additional background details. We enable geometric optimization of tilings by our key technical contribution: an unconstrained, differentiable parameterization of the space of all possible tileable shapes for a given symmetry group. Namely, we prove that modifying the laplacian used in a 2D mesh-mapping technique - Orbifold Tutte Embedding - can achieve all possible tiling configurations for a chosen planar symmetry group. We thus consider both the mesh's tile-shape and its texture as optimizable parameters, rendering the textured mesh via a differentiable renderer. We leverage a trained image diffusion model to define a loss on the resulting image, thereby updating the mesh's parameters based on its appearance matching the text prompt. We show our method is able to produce plausible, appealing results, with non-trivial tiles, for a variety of different periodic tiling patterns.

Pattern Formation for Fat Robots with Memory

from arXiv: Computational Geometry

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

Given a set of $n\geq 1$ autonomous, anonymous, indistinguishable, silent, and possibly disoriented mobile unit disk (i.e., fat) robots operating following Look-Compute-Move cycles in the Euclidean plane, we consider the Pattern Formation problem: from arbitrary starting positions, the robots must reposition themselves to form a given target pattern. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between the two robots. We assume that a robot's movement cannot be interrupted by an adversary and that robots have a small $O(1)$-sized memory that they can use to store information, but that cannot be communicated to the other robots. To solve this problem, we present an algorithm that works in three steps. First it establishes mutual visibility, then it elects one robot to be the leader, and finally it forms the required pattern. The whole algorithm runs in $O(n) + O(q \log n)$ rounds, where $q>0$ is related to leader election, which takes $O(q \log n)$ rounds with probability at least $1-n^{-q}$. The algorithms are collision-free and do not require the knowledge of the number of robots.

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

Given a set of $n\geq 1$ autonomous, anonymous, indistinguishable, silent, and possibly disoriented mobile unit disk (i.e., fat) robots operating following Look-Compute-Move cycles in the Euclidean plane, we consider the Pattern Formation problem: from arbitrary starting positions, the robots must reposition themselves to form a given target pattern. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between the two robots. We assume that a robot's movement cannot be interrupted by an adversary and that robots have a small $O(1)$-sized memory that they can use to store information, but that cannot be communicated to the other robots. To solve this problem, we present an algorithm that works in three steps. First it establishes mutual visibility, then it elects one robot to be the leader, and finally it forms the required pattern. The whole algorithm runs in $O(n) + O(q \log n)$ rounds, where $q>0$ is related to leader election, which takes $O(q \log n)$ rounds with probability at least $1-n^{-q}$. The algorithms are collision-free and do not require the knowledge of the number of robots.

Planted Random Number Partitioning Problem

from arXiv: Data Structures and Algorithms

Authors: Eren C. Kızıldağ

We consider the random number partitioning problem (\texttt{NPP}): given a list $X\sim \mathcal{N}(0,I_n)$ of numbers, find a partition $\sigma\in\{-1,1\}^n$ with a small objective value $H(\sigma)=\frac{1}{\sqrt{n}}\left|\langle \sigma,X\rangle\right|$. The \texttt{NPP} is widely studied in computer science; it is also closely related to the design of randomized controlled trials. In this paper, we propose a planted version of the \texttt{NPP}: fix a $\sigma^*$ and generate $X\sim \mathcal{N}(0,I_n)$ conditional on $H(\sigma^*)\le 3^{-n}$. The \texttt{NPP} and its planted counterpart are statistically distinguishable as the smallest objective value under the former is $\Theta(\sqrt{n}2^{-n})$ w.h.p.

Our first focus is on the values of $H(\sigma)$. We show that, perhaps surprisingly, planting does not induce partitions with an objective value substantially smaller than $2^{-n}$: $\min_{\sigma \ne \pm \sigma^*}H(\sigma) = \widetilde{\Theta}(2^{-n})$ w.h.p. Furthermore, we completely characterize the smallest $H(\sigma)$ achieved at any fixed distance from $\sigma^*$. Our second focus is on the algorithmic problem of efficiently finding a partition $\sigma$, not necessarily equal to $\pm\sigma^*$, with a small $H(\sigma)$. We show that planted \texttt{NPP} exhibits an intricate geometrical property known as the multi Overlap Gap Property ($m$-OGP) for values $2^{-\Theta(n)}$. We then leverage the $m$-OGP to show that stable algorithms satisfying a certain anti-concentration property fail to find a $\sigma$ with $H(\sigma)=2^{-\Theta(n)}$.

Our results are the first instance of the $m$-OGP being established and leveraged to rule out stable algorithms for a planted model. More importantly, they show that the $m$-OGP framework can also apply to planted models, if the algorithmic goal is to return a solution with a small objective value.

Authors: Eren C. Kızıldağ

We consider the random number partitioning problem (\texttt{NPP}): given a list $X\sim \mathcal{N}(0,I_n)$ of numbers, find a partition $\sigma\in\{-1,1\}^n$ with a small objective value $H(\sigma)=\frac{1}{\sqrt{n}}\left|\langle \sigma,X\rangle\right|$. The \texttt{NPP} is widely studied in computer science; it is also closely related to the design of randomized controlled trials. In this paper, we propose a planted version of the \texttt{NPP}: fix a $\sigma^*$ and generate $X\sim \mathcal{N}(0,I_n)$ conditional on $H(\sigma^*)\le 3^{-n}$. The \texttt{NPP} and its planted counterpart are statistically distinguishable as the smallest objective value under the former is $\Theta(\sqrt{n}2^{-n})$ w.h.p.

Our first focus is on the values of $H(\sigma)$. We show that, perhaps surprisingly, planting does not induce partitions with an objective value substantially smaller than $2^{-n}$: $\min_{\sigma \ne \pm \sigma^*}H(\sigma) = \widetilde{\Theta}(2^{-n})$ w.h.p. Furthermore, we completely characterize the smallest $H(\sigma)$ achieved at any fixed distance from $\sigma^*$. Our second focus is on the algorithmic problem of efficiently finding a partition $\sigma$, not necessarily equal to $\pm\sigma^*$, with a small $H(\sigma)$. We show that planted \texttt{NPP} exhibits an intricate geometrical property known as the multi Overlap Gap Property ($m$-OGP) for values $2^{-\Theta(n)}$. We then leverage the $m$-OGP to show that stable algorithms satisfying a certain anti-concentration property fail to find a $\sigma$ with $H(\sigma)=2^{-\Theta(n)}$.

Our results are the first instance of the $m$-OGP being established and leveraged to rule out stable algorithms for a planted model. More importantly, they show that the $m$-OGP framework can also apply to planted models, if the algorithmic goal is to return a solution with a small objective value.

Infeasibility of constructing a special orthogonal matrix for the deterministic remote preparation of arbitrary n-qubit state

from arXiv: Data Structures and Algorithms

Authors: Wenjie Liu, Zixian Li, Gonglin Yuan

In this paper, we present a polynomial-complexity algorithm to construct a special orthogonal matrix for the deterministic remote state preparation (DRSP) of an arbitrary n-qubit state, and prove that if n>3, such matrices do not exist. Firstly, the construction problem is split into two sub-problems, i.e., finding a solution of a semi-orthogonal matrix and generating all semi-orthogonal matrices. Through giving the definitions and properties of the matching operators, it is proved that the orthogonality of a special matrix is equivalent to the cooperation of multiple matching operators, and then the construction problem is reduced to the problem of solving an XOR linear equation system, which reduces the construction complexity from exponential to polynomial level. Having proved that each semi-orthogonal matrix can be simplified into a unique form, we use the proposed algorithm to confirm that the unique form does not have any solution when n>3, which means it is infeasible to construct such a special orthogonal matrix for the DRSP of an arbitrary n-qubit state.

Authors: Wenjie Liu, Zixian Li, Gonglin Yuan

In this paper, we present a polynomial-complexity algorithm to construct a special orthogonal matrix for the deterministic remote state preparation (DRSP) of an arbitrary n-qubit state, and prove that if n>3, such matrices do not exist. Firstly, the construction problem is split into two sub-problems, i.e., finding a solution of a semi-orthogonal matrix and generating all semi-orthogonal matrices. Through giving the definitions and properties of the matching operators, it is proved that the orthogonality of a special matrix is equivalent to the cooperation of multiple matching operators, and then the construction problem is reduced to the problem of solving an XOR linear equation system, which reduces the construction complexity from exponential to polynomial level. Having proved that each semi-orthogonal matrix can be simplified into a unique form, we use the proposed algorithm to confirm that the unique form does not have any solution when n>3, which means it is infeasible to construct such a special orthogonal matrix for the DRSP of an arbitrary n-qubit state.

Revisiting Tree Isomorphism: AHU Algorithm with Primes Numbers

from arXiv: Data Structures and Algorithms

Authors: Florian Ingels

The AHU algorithm has been the state of the art since the 1970s for determining in linear time whether two unordered rooted trees are isomorphic or not. However, it has been criticized (by Campbell and Radford) for the way it is written, which requires several (re)readings to be understood, and does not facilitate its analysis. In this paper, we propose an alternative version of the AHU algorithm, which addresses this issue by being designed to be clearer to understand and implement, with the same theoretical complexity and equally fast in practice.. Whereas the key to the linearity of the original algorithm lay on the careful sorting of lists of integers, we replace this step by the multiplication of lists of prime numbers, and prove that this substitution causes no loss in the final complexity of the new algorithm.

Authors: Florian Ingels

The AHU algorithm has been the state of the art since the 1970s for determining in linear time whether two unordered rooted trees are isomorphic or not. However, it has been criticized (by Campbell and Radford) for the way it is written, which requires several (re)readings to be understood, and does not facilitate its analysis. In this paper, we propose an alternative version of the AHU algorithm, which addresses this issue by being designed to be clearer to understand and implement, with the same theoretical complexity and equally fast in practice.. Whereas the key to the linearity of the original algorithm lay on the careful sorting of lists of integers, we replace this step by the multiplication of lists of prime numbers, and prove that this substitution causes no loss in the final complexity of the new algorithm.

Bicriteria Approximation Algorithms for the Submodular Cover Problem

from arXiv: Data Structures and Algorithms

Authors: Wenjing Chen, Victoria G. Crawford

In this paper, we consider the optimization problem Submodular Cover (SCP), which is to find a minimum cardinality subset of a finite universe $U$ such that the value of a submodular function $f$ is above an input threshold $\tau$. In particular, we consider several variants of SCP including the general case, the case where $f$ is additionally assumed to be monotone, and finally the case where $f$ is a regularized monotone submodular function. Our most significant contributions are that: (i) We propose a scalable algorithm for monotone SCP that achieves nearly the same approximation guarantees as the standard greedy algorithm in significantly faster time; (ii) We are the first to develop an algorithm for general SCP that achieves a solution arbitrarily close to being feasible; and finally (iii) we are the first to develop algorithms for regularized SCP. Our algorithms are then demonstrated to be effective in an extensive experimental section on data summarization and graph cut, two applications of SCP.

Authors: Wenjing Chen, Victoria G. Crawford

In this paper, we consider the optimization problem Submodular Cover (SCP), which is to find a minimum cardinality subset of a finite universe $U$ such that the value of a submodular function $f$ is above an input threshold $\tau$. In particular, we consider several variants of SCP including the general case, the case where $f$ is additionally assumed to be monotone, and finally the case where $f$ is a regularized monotone submodular function. Our most significant contributions are that: (i) We propose a scalable algorithm for monotone SCP that achieves nearly the same approximation guarantees as the standard greedy algorithm in significantly faster time; (ii) We are the first to develop an algorithm for general SCP that achieves a solution arbitrarily close to being feasible; and finally (iii) we are the first to develop algorithms for regularized SCP. Our algorithms are then demonstrated to be effective in an extensive experimental section on data summarization and graph cut, two applications of SCP.

On Deterministically Approximating Total Variation Distance

from arXiv: Data Structures and Algorithms

Authors: Weiming Feng, Liqiang Liu, Tianren Liu

Total variation distance (TV distance) is an important measure for the difference between two distributions. Recently, there has been progress in approximating the TV distance between product distributions: a deterministic algorithm for a restricted class of product distributions (Bhattacharyya, Gayen, Meel, Myrisiotis, Pavan and Vinodchandran 2023) and a randomized algorithm for general product distributions (Feng, Guo, Jerrum and Wang 2023). We give a deterministic fully polynomial-time approximation algorithm (FPTAS) for the TV distance between product distributions. Given two product distributions $\mathbb{P}$ and $\mathbb{Q}$ over $[q]^n$, our algorithm approximates their TV distance with relative error $\varepsilon$ in time $O\bigl( \frac{qn^2}{\varepsilon} \log q \log \frac{n}{\varepsilon \Delta_{\text{TV}}(\mathbb{P},\mathbb{Q}) } \bigr)$.

Our algorithm is built around two key concepts: 1) The likelihood ratio as a distribution, which captures sufficient information to compute the TV distance. 2) We introduce a metric between likelihood ratio distributions, called the minimum total variation distance. Our algorithm computes a sparsified likelihood ratio distribution that is close to the original one w.r.t. the new metric. The approximated TV distance can be computed from the sparsified likelihood ratio.

Our technique also implies deterministic FPTAS for the TV distance between Markov chains.

Authors: Weiming Feng, Liqiang Liu, Tianren Liu

Total variation distance (TV distance) is an important measure for the difference between two distributions. Recently, there has been progress in approximating the TV distance between product distributions: a deterministic algorithm for a restricted class of product distributions (Bhattacharyya, Gayen, Meel, Myrisiotis, Pavan and Vinodchandran 2023) and a randomized algorithm for general product distributions (Feng, Guo, Jerrum and Wang 2023). We give a deterministic fully polynomial-time approximation algorithm (FPTAS) for the TV distance between product distributions. Given two product distributions $\mathbb{P}$ and $\mathbb{Q}$ over $[q]^n$, our algorithm approximates their TV distance with relative error $\varepsilon$ in time $O\bigl( \frac{qn^2}{\varepsilon} \log q \log \frac{n}{\varepsilon \Delta_{\text{TV}}(\mathbb{P},\mathbb{Q}) } \bigr)$.

Our algorithm is built around two key concepts: 1) The likelihood ratio as a distribution, which captures sufficient information to compute the TV distance. 2) We introduce a metric between likelihood ratio distributions, called the minimum total variation distance. Our algorithm computes a sparsified likelihood ratio distribution that is close to the original one w.r.t. the new metric. The approximated TV distance can be computed from the sparsified likelihood ratio.

Our technique also implies deterministic FPTAS for the TV distance between Markov chains.

On the Advice Complexity of Online Unit Clustering

from arXiv: Data Structures and Algorithms

Authors: Judit Nagy-György

In online unit clustering a set of n points of a metric space that arrive one by one, partition the points into clusters of diameter at most one, so that number of clusters is minimized. This paper gives linear upper and lower bounds for the advice complexity of 1-competitive online unit clustering algorithms in terms of number of points in $\mathbb{R}^d$ and $\mathbb{Z}^d$.

Authors: Judit Nagy-György

In online unit clustering a set of n points of a metric space that arrive one by one, partition the points into clusters of diameter at most one, so that number of clusters is minimized. This paper gives linear upper and lower bounds for the advice complexity of 1-competitive online unit clustering algorithms in terms of number of points in $\mathbb{R}^d$ and $\mathbb{Z}^d$.

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares

from arXiv: Data Structures and Algorithms

Authors: Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya

We study the online variant of the language distance problem for two classical formal languages, the language of palindromes and the language of squares, and for the two most fundamental distances, the Hamming distance and the edit (Levenshtein) distance. In this problem, defined for a fixed formal language $L$, we are given a string $T$ of length $n$, and the task is to compute the minimal distance to $L$ from every prefix of $T$. We focus on the low-distance regime, where one must compute only the distances smaller than a given threshold $k$. In this work, our contribution is twofold:

- First, we show streaming algorithms, which access the input string $T$ only through a single left-to-right scan. Both for palindromes and squares, our algorithms use $O(k \cdot\mathrm{poly}~\log n)$ space and time per character in the Hamming-distance case and $O(k^2 \cdot\mathrm{poly}~\log n)$ space and time per character in the edit-distance case. These algorithms are randomised by necessity, and they err with probability inverse-polynomial in $n$.

- Second, we show deterministic read-only online algorithms, which are also provided with read-only random access to the already processed characters of $T$. Both for palindromes and squares, our algorithms use $O(k \cdot\mathrm{poly}~\log n)$ space and time per character in the Hamming-distance case and $O(k^4 \cdot\mathrm{poly}~\log n)$ space and amortised time per character in the edit-distance case.

Authors: Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya

We study the online variant of the language distance problem for two classical formal languages, the language of palindromes and the language of squares, and for the two most fundamental distances, the Hamming distance and the edit (Levenshtein) distance. In this problem, defined for a fixed formal language $L$, we are given a string $T$ of length $n$, and the task is to compute the minimal distance to $L$ from every prefix of $T$. We focus on the low-distance regime, where one must compute only the distances smaller than a given threshold $k$. In this work, our contribution is twofold:

- First, we show streaming algorithms, which access the input string $T$ only through a single left-to-right scan. Both for palindromes and squares, our algorithms use $O(k \cdot\mathrm{poly}~\log n)$ space and time per character in the Hamming-distance case and $O(k^2 \cdot\mathrm{poly}~\log n)$ space and time per character in the edit-distance case. These algorithms are randomised by necessity, and they err with probability inverse-polynomial in $n$.

- Second, we show deterministic read-only online algorithms, which are also provided with read-only random access to the already processed characters of $T$. Both for palindromes and squares, our algorithms use $O(k \cdot\mathrm{poly}~\log n)$ space and time per character in the Hamming-distance case and $O(k^4 \cdot\mathrm{poly}~\log n)$ space and amortised time per character in the edit-distance case.

Tuesday, September 26

Postdoctoral Fellow at Yale’s Institute for Foundations of Data Science (FDS) (apply by November 1, 2023)

from CCI: jobs

Yale’s Institute for Foundations of Data Science (FDS) is seeking applications for postdoctoral positions in Data Science. Fully supported, 2-3yr appointments. $95,000 yearly salary plus $10,000 annually for travel and research expenses. No teaching requirement. Flexible mentorship. Independent research. A growing list of members may be found on our web page, fds.yale.edu. Website: academicjobsonline.org/ajo/jobs/25695 Email: […]

Yale’s Institute for Foundations of Data Science (FDS) is seeking applications for postdoctoral positions in Data Science. Fully supported, 2-3yr appointments. $95,000 yearly salary plus $10,000 annually for travel and research expenses. No teaching requirement. Flexible mentorship. Independent research. A growing list of members may be found on our web page, https://fds.yale.edu.

Website: https://academicjobsonline.org/ajo/jobs/25695
Email: daniel.spielman@yale.edu

By shacharlovett

Faster Approximate All Pairs Shortest Paths

from arXiv: Data Structures and Algorithms

Authors: Barna Saha, Christopher Ye

The all pairs shortest path problem (APSP) is one of the foundational problems in computer science. For weighted dense graphs on $n$ vertices, no truly sub-cubic algorithms exist to compute APSP exactly even for undirected graphs. This is popularly known as the APSP conjecture and has played a prominent role in developing the field of fine-grained complexity. The seminal result of Seidel uses fast matrix multiplication (FMM) to compute APSP on unweighted undirected graphs exactly in $\tilde{O}(n^{\omega})$ time, where $\omega=2.372$. Even for unweighted undirected graphs, it is not possible to obtain a $(2-\epsilon)$-approximation of APSP in $o(n^\omega)$ time.

In this paper, we provide a multitude of new results for multiplicative and additive approximations of APSP in undirected graphs for both unweighted and weighted cases. We provide new algorithms for multiplicative 2-approximation of unweighted graphs: a deterministic one that runs in $\tilde{O}(n^{2.072})$ time and a randomized one that runs in $\tilde{O}(n^{2.032})$ on expectation improving upon the best known bound of $\tilde{O}(n^{2.25})$ by Roditty (STOC, 2023). For $2$-approximating paths of length $\geq k$, $k \geq 4$, we provide the first improvement after Dor, Halperin, Zwick (2000) for dense graphs even just using combinatorial methods, and then improve it further using FMM. We next consider additive approximations, and provide improved bounds for all additive $\beta$-approximations, $\beta \geq 4$. For weighted graphs, we show that by allowing small additive errors along with an $(1+\epsilon)$-multiplicative approximation, it is possible to improve upon Zwick's $\tilde{O}(n^\omega)$ algorithm. Our results point out the crucial role that FMM can play even on approximating APSP on unweighted undirected graphs, and reveal new bottlenecks towards achieving a quadratic running time to approximate APSP.

Authors: Barna Saha, Christopher Ye

The all pairs shortest path problem (APSP) is one of the foundational problems in computer science. For weighted dense graphs on $n$ vertices, no truly sub-cubic algorithms exist to compute APSP exactly even for undirected graphs. This is popularly known as the APSP conjecture and has played a prominent role in developing the field of fine-grained complexity. The seminal result of Seidel uses fast matrix multiplication (FMM) to compute APSP on unweighted undirected graphs exactly in $\tilde{O}(n^{\omega})$ time, where $\omega=2.372$. Even for unweighted undirected graphs, it is not possible to obtain a $(2-\epsilon)$-approximation of APSP in $o(n^\omega)$ time.

In this paper, we provide a multitude of new results for multiplicative and additive approximations of APSP in undirected graphs for both unweighted and weighted cases. We provide new algorithms for multiplicative 2-approximation of unweighted graphs: a deterministic one that runs in $\tilde{O}(n^{2.072})$ time and a randomized one that runs in $\tilde{O}(n^{2.032})$ on expectation improving upon the best known bound of $\tilde{O}(n^{2.25})$ by Roditty (STOC, 2023). For $2$-approximating paths of length $\geq k$, $k \geq 4$, we provide the first improvement after Dor, Halperin, Zwick (2000) for dense graphs even just using combinatorial methods, and then improve it further using FMM. We next consider additive approximations, and provide improved bounds for all additive $\beta$-approximations, $\beta \geq 4$. For weighted graphs, we show that by allowing small additive errors along with an $(1+\epsilon)$-multiplicative approximation, it is possible to improve upon Zwick's $\tilde{O}(n^\omega)$ algorithm. Our results point out the crucial role that FMM can play even on approximating APSP on unweighted undirected graphs, and reveal new bottlenecks towards achieving a quadratic running time to approximate APSP.

Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability

from arXiv: Data Structures and Algorithms

Authors: Antoine Amarilli, Timothy van Bremen, Kuldeep S. Meel

Query evaluation over probabilistic databases is a notoriously intractable problem -- not only in combined complexity, but for many natural queries in data complexity as well. This motivates the study of probabilistic query evaluation through the lens of approximation algorithms, and particularly of combined FPRASes, whose runtime is polynomial in both the query and instance size. In this paper, we focus on tuple-independent probabilistic databases over binary signatures, which can be equivalently viewed as probabilistic graphs. We study in which cases we can devise combined FPRASes for probabilistic query evaluation in this setting.

We settle the complexity of this problem for a variety of query and instance classes, by proving both approximability and (conditional) inapproximability results. This allows us to deduce many corollaries of possible independent interest. For example, we show how the results of Arenas et al. on counting fixed-length strings accepted by an NFA imply the existence of an FPRAS for the two-terminal network reliability problem on directed acyclic graphs: this was an open problem until now. We also show that one cannot extend the recent result of van Bremen and Meel that gives a combined FPRAS for self-join-free conjunctive queries of bounded hypertree width on probabilistic databases: neither the bounded-hypertree-width condition nor the self-join-freeness hypothesis can be relaxed. Finally, we complement all our inapproximability results with unconditional lower bounds, showing that DNNF provenance circuits must have at least moderately exponential size in combined complexity.

Authors: Antoine Amarilli, Timothy van Bremen, Kuldeep S. Meel

Query evaluation over probabilistic databases is a notoriously intractable problem -- not only in combined complexity, but for many natural queries in data complexity as well. This motivates the study of probabilistic query evaluation through the lens of approximation algorithms, and particularly of combined FPRASes, whose runtime is polynomial in both the query and instance size. In this paper, we focus on tuple-independent probabilistic databases over binary signatures, which can be equivalently viewed as probabilistic graphs. We study in which cases we can devise combined FPRASes for probabilistic query evaluation in this setting.

We settle the complexity of this problem for a variety of query and instance classes, by proving both approximability and (conditional) inapproximability results. This allows us to deduce many corollaries of possible independent interest. For example, we show how the results of Arenas et al. on counting fixed-length strings accepted by an NFA imply the existence of an FPRAS for the two-terminal network reliability problem on directed acyclic graphs: this was an open problem until now. We also show that one cannot extend the recent result of van Bremen and Meel that gives a combined FPRAS for self-join-free conjunctive queries of bounded hypertree width on probabilistic databases: neither the bounded-hypertree-width condition nor the self-join-freeness hypothesis can be relaxed. Finally, we complement all our inapproximability results with unconditional lower bounds, showing that DNNF provenance circuits must have at least moderately exponential size in combined complexity.

Monday, September 25

Postdoctoral Fellow at University of Saskatchewan, SK and Brock University, ON (apply by October 15, 2023)

from CCI: jobs

A postdoctoral position in theoretical computer science has become available. The postdoc will be working jointly with Dr. Debajyoti Mondal from University of Saskatchewan and Dr. Rahnuma Islam Nishat from Brock University. Potential topics of research include, but not limited to, graph algorithms, computational geometry, approximation algorithms and combinatorics. Website: cosc.brocku.ca/~rnishat/Job_posting.html Email: Debajyoti Mondal (dmondal@cs.usask.ca), […]

A postdoctoral position in theoretical computer science has become available. The postdoc will be working jointly with Dr. Debajyoti Mondal from University of Saskatchewan and Dr. Rahnuma Islam Nishat from Brock University.

Potential topics of research include, but not limited to, graph algorithms, computational geometry, approximation algorithms and combinatorics.

Website: http://cosc.brocku.ca/~rnishat/Job_posting.html
Email: Debajyoti Mondal (dmondal@cs.usask.ca), Rahnuma Islam Nishat (rnishat@brocku.ca)

By shacharlovett

Report from Graph Drawing

from David Eppstein

I just returned from the 31st International Symposium on Graph Drawing and Network Visualization (GD ‘23), held this time in Isola delle Femmine, a small beach town on Sicily near Palermo. Despite the name it is not a separate island; the actual Isola delle Femmine is not the town, but a small barren island about a half kilometer offshore, decorated only by a ruined tower. Several conference participants (not me) swam to the island, several others were turned back by choppy water, and at least two were stung by jellyfish. Other than visiting the hotel beach I didn’t have much of a chance for sightseeing (the weather did not cooperate for the only large block of free time that I had) but I did enjoy the excellent Sicilian food and wine.

I just returned from the 31st International Symposium on Graph Drawing and Network Visualization (GD ‘23), held this time in Isola delle Femmine, a small beach town on Sicily near Palermo. Despite the name it is not a separate island; the actual Isola delle Femmine is not the town, but a small barren island about a half kilometer offshore, decorated only by a ruined tower. Several conference participants (not me) swam to the island, several others were turned back by choppy water, and at least two were stung by jellyfish. Other than visiting the hotel beach I didn’t have much of a chance for sightseeing (the weather did not cooperate for the only large block of free time that I had) but I did enjoy the excellent Sicilian food and wine.

This was my first in-person GD since Barcelona in 2018 and it was good to be back and see old friends. One thing that was very noticeable was a strong level of participation by younger participants, and (unlike the old guard) a healthy gender balance among the younger participants. I think this speaks well to the continuing strength of this research community. There were, naturally, many Italians present, but also many Austrians and Germans, and smaller numbers of others scattered among other countries.

I would have thought the speakers on the last day had the advantage in the audience-voted best presentation award, as the freshest in voters’ minds. But the award went to one of the first-day speakers, Julia Katheder, for her paper “Weakly and strongly fan-planar graphs” (arXiv:2308.08966, with Cheong, Förster, Pfister, and Schlipf) clearing up the past literature on this class of graphs (defined through restrictions on their crossings) in light of the recent discovery that a previous forbidden-subdrawing characterization of them, used in several previous works, was incomplete. I think she sealed the victory by using an actual fan as a prop in her talk, but even without that she was a deserving winner. The two best papers were mine on biplanarity of blowups, in the theory track, and “CelticGraph: drawing graphs as Celtic knots and links” (arXiv:2309.02852, Eades, Gröne, Klein, Eades, Schreiber, Hailer, and Schreiber, with two father-son pairs).

A few other highlights for me from the first day included:

  • Niloufar Fuladi spoke on connections between the crossing number of planar drawings, uncrossed embeddings of graphs on higher-genus surfaces, and the signed pancake-flipping problem from genomics and Bill Gates fame (“Degenerate crossing number and signed reversal distance”, arXiv:2308.10666, with Hubard and de Mesmay).

  • Patricia Bachmann clarified that an old claim of a polynomial time algorithm for 3-coloring circle graphs (or finding 3-page book embeddings of ordered graphs) is certainly wrong (“On the 3-coloring of circle graphs”, arXiv:2309.02258, with Rutter and Stumpf). The complexity of this problem remains open.

  • Paul Jungeblut proved that it is complete for the existential theory of the reals to determine whether a graph has a Lombardi drawing (circular arc edges meeting at equal angles at each vertex): “On the complexity of Lombardi graph drawing”, arXiv:2306.02649).

The second day’s events included an invited talk by Monique Teillaud on the CGAL open-source computational geometry library, the conference business meeting, and a group dinner. At the business meeting we learned that next year’s conference will be in Vienna, with the proceedings publication switching from Springer LNCS to open access on LIPIcs. The proceedings has traditionally appeared several months after the conference, in part to allow the inclusion of a report from the graph drawing contest, and in part because of the lead time between submission of final versions and the proceedings publication; this seems likely to remain true after the changeover. In recent years we have also maintained a pseudo-proceedings on arXiv, so that papers would be available open access (getting open access through LNCS is far too expensive), but this also provided conference participants with timely access to the papers. A discussion ensued over whether we needed to continue to do this. It was left up to the PC chairs and steering committee, but one likely compromise would be to provide participants with the full final versions collected by the PC chair for the LIPIcs proceedings.

For me, the second-day highlights included:

  • András Sebő spoke on boxicity, the minimum dimension for which a graph can be represented as an intersection graph of hyper-rectangles: “Boxicity and interval-orders: Petersen and the complements of line graphs” (arXiv:2309.02062, with Caoduro). Sebő is new to graph drawing, usually working in combinatorial optimization, approximation, packing, and polyhedral combinatorics; I hope he found the community as welcoming as I have usually found it to be.

  • Pavel Valtr enlivened his talk (“Three edge-disjoint plane spanning paths in a point set”, arXiv:2306.07237, with Kindermann, Kratochvil, and Liotta) by presenting part of it on a T-shirt, sadly available only to the paper’s coauthors.

  • If I remember correctly, the presenter of “Cops and robbers on 1-planar graphs” (arXiv:2309.01001, Durocher, Kamali, Kryven, Liu, Mashghdoust, Miller, Zamani Nezhad, Penha Costa, and Zapp) was Myroslav Kryven. The paper proves that three cops can catch a robber on a graph drawn with at most one crossing per edge, when each player can either stay put or move along one edge per turn. That is, 1-planar graphs have cop number at most three.

The final day of the main conference included another invited talk, by Michael Kaufmann on orthogonal drawing, and the award presentations. As well as the ones I already mentioned, there was an audience-voted best-poster contest, won by “What happens in Dagstuhl…” (Klesen, Miller, Montecchiani, Nöllenburg, and Wallinger), a visualization of interactions at this workshop center. My personal favorite was “A collection of benchmark datasets for evaluating graph layout algorithms” (Di Bartolomeo, Puerta, Wilson, Cronvrsanin, and Dunne). Unfortunately it does not seem to be possible to find the posters online, but the benchmarks themselves are on the Open Science Framework. Highlight talks for me included:

  • The entire first session concerned parameterized complexity, including papers on bend-minimal orthogonal planar drawing (arXiv:2308.13665), right-angle-crossing (RAC) drawings (arXiv:2308.10600), simultaneous embedding (2308.11401, and drawing graphs so that the edges line up into a small number of line segments (arXiv:2308.15416). I didn’t notice until after the conference that one of the coauthors on the last of these (not present at the conference) is my former student Sid Gupta.

  • A standard tool in graph drawing is the Schnyder wood, a covering of any 3-connected planar triangulation by three forests. It can alternatively be described by a constrained labeling of corners of the triangles by the numbers 1, 2, and 3, in clockwise order, with the labels appearing in contiguous blocks at each vertex. Éric Fusy spoke about generalizations to 4 trees and 4 labels in 4-connected graphs and to 5 trees and 5 labels in 5-connected graphs (“A Schnyder-type drawing algorithm for 5-connected triangulations”, arXiv:2305.19058, with Bernardi and Liang).

  • Tim Hegemann’s talk (“A simple pipeline for orthogonal graph drawing”, arXiv:2309.01671, with Wolff) was notable to me not so much for its methods, but for the application he presented: a farm machinery company builds large harvesters that each include a unique combination of components. When these machines need repair, the technicians use functional diagrams of these components, depicted with boxes for the components and axis-parallel polylines for their connections. So they need a way of producing large numbers of readable diagrams, automatically.

That wasn’t the end of the gathering, though, because there was a final day for “BeppeFest”, an elaborate celebration of Beppe Liotta’s 60th birthday, featuring two sessions of invited talks by Beppe’s old friends overviewing their joint research, and another dinner including an elaborate show of musical pastiches (several involving the talented Alessandra Tappini), quiz questions for Beppe about past conferences, and congratulatory videos. Happy birthday, again, Beppe!

(Discuss on Mastodon)

By David Eppstein