Theory of Computing Report

Sunday, September 25

TR22-136 | Rounds vs Communication Tradeoffs for Maximal Independent Sets | Sepehr Assadi, Gillat Kol, Zhijun Zhang

from ECCC Papers
We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both its endpoints and is thus shared by two players. The players communicate in simultaneous rounds by posting their messages on a shared blackboard visible to all players, with the goal of computing an MIS of the graph. While the MIS problem is well studied in other distributed models, and while shared blackboard is, perhaps, the simplest broadcast model, lower bounds for our problem were only known against one-round protocols. We present a lower bound on the round-communication tradeoff for computing an MIS in this model. Specifically, we show that when $r$ rounds of interaction are allowed, at least one player needs to communicate $\Omega(n^{1/20^{r+1}})$ bits. In particular, with logarithmic bandwidth, finding an MIS requires $\Omega(\log\log{n})$ rounds. This lower bound can be compared with the algorithm of Ghaffari, Gouleakis, Konrad, Mitrovi ?c, and Rubinfeld [PODC 2018] that solves MIS in $O(\log\log{n})$ rounds but with a logarithmic bandwidth for an average player. Additionally, our lower bound further extends to the closely related problem of maximal bipartite matching. The presence of edge-sharing gives the algorithms in our model a surprising power and numerous algorithmic results exploiting this power are known. For a similar reason, proving lower bounds in this model is much more challenging, as this sharing in the players' inputs prohibits the use of standard number-in-hand communication complexity arguments. Thus, to prove our results, we devise a new round elimination framework, which we call partial-input embedding, that may also be useful in future work for proving round-sensitive lower bounds in the presence of shared inputs. Finally, we discuss several implications of our results to multi-round (adaptive) distributed sketching algorithms, broadcast congested clique, and to the welfare maximization problem in two-sided matching markets.
We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both its endpoints and is thus shared by two players. The players communicate in simultaneous rounds by posting their messages on a shared blackboard visible to all players, with the goal of computing an MIS of the graph. While the MIS problem is well studied in other distributed models, and while shared blackboard is, perhaps, the simplest broadcast model, lower bounds for our problem were only known against one-round protocols. We present a lower bound on the round-communication tradeoff for computing an MIS in this model. Specifically, we show that when $r$ rounds of interaction are allowed, at least one player needs to communicate $\Omega(n^{1/20^{r+1}})$ bits. In particular, with logarithmic bandwidth, finding an MIS requires $\Omega(\log\log{n})$ rounds. This lower bound can be compared with the algorithm of Ghaffari, Gouleakis, Konrad, Mitrovi ?c, and Rubinfeld [PODC 2018] that solves MIS in $O(\log\log{n})$ rounds but with a logarithmic bandwidth for an average player. Additionally, our lower bound further extends to the closely related problem of maximal bipartite matching. The presence of edge-sharing gives the algorithms in our model a surprising power and numerous algorithmic results exploiting this power are known. For a similar reason, proving lower bounds in this model is much more challenging, as this sharing in the players' inputs prohibits the use of standard number-in-hand communication complexity arguments. Thus, to prove our results, we devise a new round elimination framework, which we call partial-input embedding, that may also be useful in future work for proving round-sensitive lower bounds in the presence of shared inputs. Finally, we discuss several implications of our results to multi-round (adaptive) distributed sketching algorithms, broadcast congested clique, and to the welfare maximization problem in two-sided matching markets.

TR22-135 | Decision Tree Complexity versus Block Sensitivity and Degree | Swagato Sanyal, Supartha Poddar, Rahul Chugh

from ECCC Papers
Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It is known that decision tree complexity is bounded above by the cube of block sensitivity, and the cube of polynomial degree. However, the widest separation between decision tree complexity and each of block sensitivity and degree that is witnessed by known Boolean functions is quadratic. Proving quadratic relations between these measures would resolve several open questions in decision tree complexity. For example, we get a tight relation between decision tree complexity and square of randomized decision tree complexity and a tight relation between zero-error randomized decision tree complexity and square of fractional block sensitivity, resolving an open question raised by Aaronson. In this work, we investigate the tightness of the existing cubic upper bounds.  We improve the cubic upper bounds for many interesting classes of Boolean functions. We show that for graph properties and for functions with a constant number of alternations, both of the cubic upper bounds can be improved to quadratic. We define a class of Boolean functions, which we call the zebra functions, that comprises Boolean functions where each monotone path from $0^n$ to $1^n$ has an equal number of alternations. This class contains the symmetric and monotone functions as its subclasses. We show that for any zebra function, decision tree complexity is at most the square of block sensitivity, and certificate complexity is at most the square of degree.  Finally, we show using a lifting theorem of communication complexity by G{\"{o}}{\"{o}}s, Pitassi and Watson that the task of proving an improved upper bound on the decision tree complexity for all functions is in a sense equivalent to the potentially easier task of proving a similar upper bound on communication complexity for each bi-partition of the input variables, for all functions. In particular, this implies that to bound the decision tree complexity it suffices to bound smaller measures like parity decision tree complexity, subcube decision tree complexity and decision tree rank, that are defined in terms of models that can be efficiently simulated by communication protocols.
Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It is known that decision tree complexity is bounded above by the cube of block sensitivity, and the cube of polynomial degree. However, the widest separation between decision tree complexity and each of block sensitivity and degree that is witnessed by known Boolean functions is quadratic. Proving quadratic relations between these measures would resolve several open questions in decision tree complexity. For example, we get a tight relation between decision tree complexity and square of randomized decision tree complexity and a tight relation between zero-error randomized decision tree complexity and square of fractional block sensitivity, resolving an open question raised by Aaronson. In this work, we investigate the tightness of the existing cubic upper bounds.  We improve the cubic upper bounds for many interesting classes of Boolean functions. We show that for graph properties and for functions with a constant number of alternations, both of the cubic upper bounds can be improved to quadratic. We define a class of Boolean functions, which we call the zebra functions, that comprises Boolean functions where each monotone path from $0^n$ to $1^n$ has an equal number of alternations. This class contains the symmetric and monotone functions as its subclasses. We show that for any zebra function, decision tree complexity is at most the square of block sensitivity, and certificate complexity is at most the square of degree.  Finally, we show using a lifting theorem of communication complexity by G{\"{o}}{\"{o}}s, Pitassi and Watson that the task of proving an improved upper bound on the decision tree complexity for all functions is in a sense equivalent to the potentially easier task of proving a similar upper bound on communication complexity for each bi-partition of the input variables, for all functions. In particular, this implies that to bound the decision tree complexity it suffices to bound smaller measures like parity decision tree complexity, subcube decision tree complexity and decision tree rank, that are defined in terms of models that can be efficiently simulated by communication protocols.

TR22-134 | Some Games on Turing Machines and Power from Random Strings | Alexey Milovanov, Greg McLellan

from ECCC Papers
Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger. Power from random strings. \emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea was later developed in several others papers. We prove new lower bounds for $Q^R_{tt}$ and $Q^R_{sa}$: - Oblivious-NP is subset of $Q^R_{tt}$; - Oblivious-MA is subset of $Q^R_{sa}$. Here $Q$ means quazi-polynomial-time; ``sa'' means sub-adaptive reduction - a new type of reduction that we introduce. This type of reduction is not weaker than truth-table reduction and is not stronger than Turing reduction. Also we prove upper bounds for BBP^R_{tt} and P^R_{sa} following [E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random strings.]: P^R_{sa} is subset of EXP BBP^R_{tt} is subset of AEXP(poly). Here AEXP(poly) is the class of languages decidable in exponential time by an alternating Turing machine that switches from an existential to a universal state or vice versa at most polynomial times. Finally we analyze some games that originate in [E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random strings.]. We prove completeness of these games. These results show that methods in this can not prove better upper bounds for P^R, NP^R and P^R_{tt} than known.
Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger. Power from random strings. \emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea was later developed in several others papers. We prove new lower bounds for $Q^R_{tt}$ and $Q^R_{sa}$: - Oblivious-NP is subset of $Q^R_{tt}$; - Oblivious-MA is subset of $Q^R_{sa}$. Here $Q$ means quazi-polynomial-time; ``sa'' means sub-adaptive reduction - a new type of reduction that we introduce. This type of reduction is not weaker than truth-table reduction and is not stronger than Turing reduction. Also we prove upper bounds for BBP^R_{tt} and P^R_{sa} following [E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random strings.]: P^R_{sa} is subset of EXP BBP^R_{tt} is subset of AEXP(poly). Here AEXP(poly) is the class of languages decidable in exponential time by an alternating Turing machine that switches from an existential to a universal state or vice versa at most polynomial times. Finally we analyze some games that originate in [E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random strings.]. We prove completeness of these games. These results show that methods in this can not prove better upper bounds for P^R, NP^R and P^R_{tt} than known.

Friday, September 23

Open-Rank Professor of Computer Science at Pomona College (apply by October 15, 2022)

from CCI: jobs
Pomona College seeks applications for two Open-Rank (assistant, associate, or full) Professor of Computer Science positions, to begin on July 1, 2023. All subfields of computer science will be considered. Candidates should have a broad background in computer science, be excellent teachers, have an active research program, and be excited about directing undergraduate research. Website: […]

Pomona College seeks applications for two Open-Rank (assistant, associate, or full) Professor of Computer Science positions, to begin on July 1, 2023. All subfields of computer science will be considered. Candidates should have a broad background in computer science, be excellent teachers, have an active research program, and be excited about directing undergraduate research.

Website: https://academicjobsonline.org/ajo/jobs/22190
Email: cssearch@pomona.edu

By shacharlovett

Solving the General Case of Rank-3 Maker-Breaker Games in Polynomial Time

from arXiv: Computational Complexity

Authors: Lear Bahack

A rank-3 Maker-Breaker game is played on a hypergraph in which all hyperedges are sets of at most 3 vertices. The two players of the game, called Maker and Breaker, move alternately. On his turn, maker chooses a vertex to be withdrawn from all hyperedges, while Breaker on her turn chooses a vertex and delete all the hyperedges containing that vertex. Maker wins when by the end of his turn some hyperedge is completely covered, i.e. the last remaining vertex of that hyperedge is withdrawn. Breaker wins when by the end of her turn, all hyperedges have been deleted.

Solving a Maker-Breaker game is the computational problem of choosing an optimal move, or equivalently, deciding which player has a winning strategy in a configuration. The complexity of solving two degenerate cases of rank-3 games has been proven before to be polynomial. In this paper, we show that the general case of rank-3 Maker-Breaker games is also solvable in polynomial time.

Authors: Lear Bahack

A rank-3 Maker-Breaker game is played on a hypergraph in which all hyperedges are sets of at most 3 vertices. The two players of the game, called Maker and Breaker, move alternately. On his turn, maker chooses a vertex to be withdrawn from all hyperedges, while Breaker on her turn chooses a vertex and delete all the hyperedges containing that vertex. Maker wins when by the end of his turn some hyperedge is completely covered, i.e. the last remaining vertex of that hyperedge is withdrawn. Breaker wins when by the end of her turn, all hyperedges have been deleted.

Solving a Maker-Breaker game is the computational problem of choosing an optimal move, or equivalently, deciding which player has a winning strategy in a configuration. The complexity of solving two degenerate cases of rank-3 games has been proven before to be polynomial. In this paper, we show that the general case of rank-3 Maker-Breaker games is also solvable in polynomial time.

Hyperstable Sets with Voting and Algorithmic Hardness Applications

from arXiv: Computational Complexity

Authors: Steven Heilman

The noise stability of a Euclidean set $A$ with correlation $\rho$ is the probability that $(X,Y)\in A\times A$, where $X,Y$ are standard Gaussian random vectors with correlation $\rho\in(0,1)$. It is well-known that a Euclidean set of fixed Gaussian volume that maximizes noise stability must be a half space.

For a partition of Euclidean space into $m>2$ parts each of Gaussian measure $1/m$, it is still unknown what sets maximize the sum of their noise stabilities. In this work, we classify partitions maximizing noise stability that are also critical points for the derivative of noise stability with respect to $\rho$. We call a partition satisfying these conditions hyperstable. Uner the assumption that a maximizing partition is hyperstable, we prove:

* a (conditional) version of the Plurality is Stablest Conjecture for $3$ or $4$ candidates.

* a (conditional) sharp Unique Games Hardness result for MAX-m-CUT for $m=3$ or $4$

* a (conditional) version of the Propeller Conjecture of Khot and Naor for $4$ sets.

We also show that a symmetric set that is hyperstable must be star-shaped.

For partitions of Euclidean space into $m>2$ parts of fixed (but perhaps unequal) Gaussian measure, the hyperstable property can only be satisfied when all of the parts have Gaussian measure $1/m$. So, as our main contribution, we have identified a possible strategy for proving the full Plurality is Stablest Conjecture and the full sharp hardness for MAX-m-CUT: to prove both statements, it suffices to show that sets maximizing noise stability are hyperstable. This last point is crucial since any proof of the Plurality is Stablest Conjecture must use a property that is special to partitions of sets into equal measures, since the conjecture is false in the unequal measure case.

Authors: Steven Heilman

The noise stability of a Euclidean set $A$ with correlation $\rho$ is the probability that $(X,Y)\in A\times A$, where $X,Y$ are standard Gaussian random vectors with correlation $\rho\in(0,1)$. It is well-known that a Euclidean set of fixed Gaussian volume that maximizes noise stability must be a half space.

For a partition of Euclidean space into $m>2$ parts each of Gaussian measure $1/m$, it is still unknown what sets maximize the sum of their noise stabilities. In this work, we classify partitions maximizing noise stability that are also critical points for the derivative of noise stability with respect to $\rho$. We call a partition satisfying these conditions hyperstable. Uner the assumption that a maximizing partition is hyperstable, we prove:

* a (conditional) version of the Plurality is Stablest Conjecture for $3$ or $4$ candidates.

* a (conditional) sharp Unique Games Hardness result for MAX-m-CUT for $m=3$ or $4$

* a (conditional) version of the Propeller Conjecture of Khot and Naor for $4$ sets.

We also show that a symmetric set that is hyperstable must be star-shaped.

For partitions of Euclidean space into $m>2$ parts of fixed (but perhaps unequal) Gaussian measure, the hyperstable property can only be satisfied when all of the parts have Gaussian measure $1/m$. So, as our main contribution, we have identified a possible strategy for proving the full Plurality is Stablest Conjecture and the full sharp hardness for MAX-m-CUT: to prove both statements, it suffices to show that sets maximizing noise stability are hyperstable. This last point is crucial since any proof of the Plurality is Stablest Conjecture must use a property that is special to partitions of sets into equal measures, since the conjecture is false in the unequal measure case.

Output Mode Switching for Parallel Five-bar Manipulators Using a Graph-based Path Planner

from arXiv: Computational Geometry

Authors: Parker B. Edwards, Aravind Baskar, Caroline Hills, Mark Plecnik, Jonathan D. Hauenstein

The configuration manifolds of parallel manipulators exhibit more nonlinearity than serial manipulators. Qualitatively, they can be seen to possess extra folds. By projecting such manifolds onto spaces of engineering relevance, such as an output workspace or an input actuator space, these folds cast edges that exhibit nonsmooth behavior. For example, inside the global workspace bounds of a five-bar linkage appear several local workspace bounds that only constrain certain output modes of the mechanism. The presence of such boundaries, which manifest in both input and output projections, serve as a source of confusion when these projections are studied exclusively instead of the configuration manifold itself. Particularly, the design of nonsymmetric parallel manipulators has been confounded by the presence of exotic projections in their input and output spaces. In this paper, we represent the configuration space with a radius graph, then weight each edge by solving an optimization problem using homotopy continuation to quantify transmission quality. We then employ a graph path planner to approximate geodesics between configuration points that avoid regions of low transmission quality. Our methodology automatically generates paths capable of transitioning between non-neighboring output modes, a motion which involves osculating multiple workspace boundaries (local, global, or both). We apply our technique to two nonsymmetric five-bar examples that demonstrate how transmission properties and other characteristics of the workspace can be selected by switching output modes.

Authors: Parker B. Edwards, Aravind Baskar, Caroline Hills, Mark Plecnik, Jonathan D. Hauenstein

The configuration manifolds of parallel manipulators exhibit more nonlinearity than serial manipulators. Qualitatively, they can be seen to possess extra folds. By projecting such manifolds onto spaces of engineering relevance, such as an output workspace or an input actuator space, these folds cast edges that exhibit nonsmooth behavior. For example, inside the global workspace bounds of a five-bar linkage appear several local workspace bounds that only constrain certain output modes of the mechanism. The presence of such boundaries, which manifest in both input and output projections, serve as a source of confusion when these projections are studied exclusively instead of the configuration manifold itself. Particularly, the design of nonsymmetric parallel manipulators has been confounded by the presence of exotic projections in their input and output spaces. In this paper, we represent the configuration space with a radius graph, then weight each edge by solving an optimization problem using homotopy continuation to quantify transmission quality. We then employ a graph path planner to approximate geodesics between configuration points that avoid regions of low transmission quality. Our methodology automatically generates paths capable of transitioning between non-neighboring output modes, a motion which involves osculating multiple workspace boundaries (local, global, or both). We apply our technique to two nonsymmetric five-bar examples that demonstrate how transmission properties and other characteristics of the workspace can be selected by switching output modes.

Maths, Computation and Flamenco: overview and challenges

from arXiv: Computational Geometry

Authors: José-Miguel Díaz-Báñez, Nadine Kroher

Flamenco is a rich performance-oriented art music genre from Southern Spain which attracts a growing community of aficionados around the globe. Due to its improvisational and expressive nature, its unique musical characteristics, and the fact that the genre is largely undocumented, flamenco poses a number of interesting mathematical and computational challenges. Most existing approaches in Musical Information Retrieval (MIR) were developed in the context of popular or classical music and do often not generalize well to non-Western music traditions, in particular when the underlying music theoretical assumptions do not hold for these genres. Over the recent decade, a number of computational problems related to the automatic analysis of flamenco music have been defined and several methods addressing a variety of musical aspects have been proposed. This paper provides an overview of the challenges which arise in the context of computational analysis of flamenco music and outlines an overview of existing approaches.

Authors: José-Miguel Díaz-Báñez, Nadine Kroher

Flamenco is a rich performance-oriented art music genre from Southern Spain which attracts a growing community of aficionados around the globe. Due to its improvisational and expressive nature, its unique musical characteristics, and the fact that the genre is largely undocumented, flamenco poses a number of interesting mathematical and computational challenges. Most existing approaches in Musical Information Retrieval (MIR) were developed in the context of popular or classical music and do often not generalize well to non-Western music traditions, in particular when the underlying music theoretical assumptions do not hold for these genres. Over the recent decade, a number of computational problems related to the automatic analysis of flamenco music have been defined and several methods addressing a variety of musical aspects have been proposed. This paper provides an overview of the challenges which arise in the context of computational analysis of flamenco music and outlines an overview of existing approaches.

Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries

from arXiv: Data Structures and Algorithms

Authors: Antoine Amarilli

We study the uniform query reliability problem, which asks, for a fixed Boolean query Q, given an instance I, how many subinstances of I satisfy Q. Equivalently, this is a restricted case of Boolean query evaluation on tuple-independent probabilistic databases where all facts must have probability 1/2. We focus on graph signatures, and on queries closed under homomorphisms. We show that for any such query that is unbounded, i.e., not equivalent to a union of conjunctive queries, the uniform reliability problem is #P-hard. This recaptures the hardness, e.g., of s-t connectedness, which counts how many subgraphs of an input graph have a path between a source and a sink.

This new hardness result on uniform reliability strengthens our earlier hardness result on probabilistic query evaluation for unbounded homomorphism-closed queries (ICDT'20). Indeed, our earlier proof crucially used facts with probability 1, so it did not apply to the unweighted case. The new proof presented in this paper avoids this; it uses our recent hardness result on uniform reliability for non-hierarchical conjunctive queries without self-joins (ICDT'21), along with new techniques.

Authors: Antoine Amarilli

We study the uniform query reliability problem, which asks, for a fixed Boolean query Q, given an instance I, how many subinstances of I satisfy Q. Equivalently, this is a restricted case of Boolean query evaluation on tuple-independent probabilistic databases where all facts must have probability 1/2. We focus on graph signatures, and on queries closed under homomorphisms. We show that for any such query that is unbounded, i.e., not equivalent to a union of conjunctive queries, the uniform reliability problem is #P-hard. This recaptures the hardness, e.g., of s-t connectedness, which counts how many subgraphs of an input graph have a path between a source and a sink.

This new hardness result on uniform reliability strengthens our earlier hardness result on probabilistic query evaluation for unbounded homomorphism-closed queries (ICDT'20). Indeed, our earlier proof crucially used facts with probability 1, so it did not apply to the unweighted case. The new proof presented in this paper avoids this; it uses our recent hardness result on uniform reliability for non-hierarchical conjunctive queries without self-joins (ICDT'21), along with new techniques.

Efficiently Reconfiguring a Connected Swarm of Labeled Robots

from arXiv: Data Structures and Algorithms

Authors: Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, Arne Schmidt

When considering motion planning for a swarm of $n$ labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, continuous, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been considered before, with recent notable results achieving constant stretch for not necessarily connected reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of $d$, the total duration of an overall schedule can be bounded to $\mathcal{O}(d)$, which is optimal up to constant factors. However, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations (which arise by increasing all dimensions of a given object by the same multiplicative factor) of unlabeled robots.

We resolve these major open problems by (1) establishing a lower bound of $\Omega(\sqrt{n})$ for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected reconfiguration can be achieved. In addition, we show that (3) it is NP-hard to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved.

Authors: Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, Arne Schmidt

When considering motion planning for a swarm of $n$ labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, continuous, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been considered before, with recent notable results achieving constant stretch for not necessarily connected reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of $d$, the total duration of an overall schedule can be bounded to $\mathcal{O}(d)$, which is optimal up to constant factors. However, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations (which arise by increasing all dimensions of a given object by the same multiplicative factor) of unlabeled robots.

We resolve these major open problems by (1) establishing a lower bound of $\Omega(\sqrt{n})$ for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected reconfiguration can be achieved. In addition, we show that (3) it is NP-hard to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved.

Learning-Augmented Algorithms for Online Linear and Semidefinite Programming

from arXiv: Data Structures and Algorithms

Authors: Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, Samson Zhou

Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and quadratically-constrained quadratic programming, while also yielding efficient solvers, both in theory and in practice. However, there exist known impossibility results for approximating the optimal solution when constraints for covering SDPs arrive in an online fashion. In this paper, we study online covering linear and semidefinite programs in which the algorithm is augmented with advice from a possibly erroneous predictor. We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant-factor approximation to the optimal solution, i.e., consistency. On the other hand, if the predictor is inaccurate, under some technical conditions, we achieve results that match both the classical optimal upper bounds and the tight lower bounds up to constant factors, i.e., robustness.

More broadly, we introduce a framework that extends both (1) the online set cover problem augmented with machine-learning predictors, studied by Bamas, Maggiori, and Svensson (NeurIPS 2020), and (2) the online covering SDP problem, initiated by Elad, Kale, and Naor (ICALP 2016). Specifically, we obtain general online learning-augmented algorithms for covering linear programs with fractional advice and constraints, and initiate the study of learning-augmented algorithms for covering SDP problems.

Our techniques are based on the primal-dual framework of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) and can be further adjusted to handle constraints where the variables lie in a bounded region, i.e., box constraints.

Authors: Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, Samson Zhou

Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and quadratically-constrained quadratic programming, while also yielding efficient solvers, both in theory and in practice. However, there exist known impossibility results for approximating the optimal solution when constraints for covering SDPs arrive in an online fashion. In this paper, we study online covering linear and semidefinite programs in which the algorithm is augmented with advice from a possibly erroneous predictor. We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant-factor approximation to the optimal solution, i.e., consistency. On the other hand, if the predictor is inaccurate, under some technical conditions, we achieve results that match both the classical optimal upper bounds and the tight lower bounds up to constant factors, i.e., robustness.

More broadly, we introduce a framework that extends both (1) the online set cover problem augmented with machine-learning predictors, studied by Bamas, Maggiori, and Svensson (NeurIPS 2020), and (2) the online covering SDP problem, initiated by Elad, Kale, and Naor (ICALP 2016). Specifically, we obtain general online learning-augmented algorithms for covering linear programs with fractional advice and constraints, and initiate the study of learning-augmented algorithms for covering SDP problems.

Our techniques are based on the primal-dual framework of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) and can be further adjusted to handle constraints where the variables lie in a bounded region, i.e., box constraints.

A cubic algorithm for computing the Hermite normal form of a nonsingular integer matrix

from arXiv: Data Structures and Algorithms

Authors: Stavros Birmpilis, George Labahn, Arne Storjohann

A Las Vegas randomized algorithm is given to compute the Hermite normal form of a nonsingular integer matrix $A$ of dimension $n$. The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by $O(n^3 (\log n + \log ||A||)^2(\log n)^2)$ bit operations, where $||A||= \max_{ij} |A_{ij}|$ denotes the largest entry of $A$ in absolute value. A variant of the algorithm that uses pseudo-linear integer multiplication is given that has running time $(n^3 \log ||A||)^{1+o(1)}$ bit operations, where the exponent $"+o(1)"$ captures additional factors $c_1 (\log n)^{c_2} (\log \log ||A||)^{c_3}$ for positive real constants $c_1,c_2,c_3$.

Authors: Stavros Birmpilis, George Labahn, Arne Storjohann

A Las Vegas randomized algorithm is given to compute the Hermite normal form of a nonsingular integer matrix $A$ of dimension $n$. The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by $O(n^3 (\log n + \log ||A||)^2(\log n)^2)$ bit operations, where $||A||= \max_{ij} |A_{ij}|$ denotes the largest entry of $A$ in absolute value. A variant of the algorithm that uses pseudo-linear integer multiplication is given that has running time $(n^3 \log ||A||)^{1+o(1)}$ bit operations, where the exponent $"+o(1)"$ captures additional factors $c_1 (\log n)^{c_2} (\log \log ||A||)^{c_3}$ for positive real constants $c_1,c_2,c_3$.

Popular Edges with Critical Nodes

from arXiv: Data Structures and Algorithms

Authors: Kushagra Chatterjee, Prajakta Nimbhorkar

In the popular edge problem, the input is a bipartite graph $G = (A \cup B,E)$ where $A$ and $B$ denote a set of men and a set of women respectively, and each vertex in $A\cup B$ has a strict preference ordering over its neighbours. A matching $M$ in $G$ is said to be {\em popular} if there is no other matching $M'$ such that the number of vertices that prefer $M'$ to $M$ is more than the number of vertices that prefer $M$ to $M'$. The goal is to determine, whether a given edge $e$ belongs to some popular matching in $G$. A polynomial-time algorithm for this problem appears in \cite{CK18}. We consider the popular edge problem when some men or women are prioritized or critical. A matching that matches all the critical nodes is termed as a feasible matching. It follows from \cite{Kavitha14,Kavitha21,NNRS21,NN17} that, when $G$ admits a feasible matching, there always exists a matching that is popular among all feasible matchings. We give a polynomial-time algorithm for the popular edge problem in the presence of critical men or women. We also show that an analogous result does not hold in the many-to-one setting, which is known as the Hospital-Residents Problem in literature, even when there are no critical nodes.

Authors: Kushagra Chatterjee, Prajakta Nimbhorkar

In the popular edge problem, the input is a bipartite graph $G = (A \cup B,E)$ where $A$ and $B$ denote a set of men and a set of women respectively, and each vertex in $A\cup B$ has a strict preference ordering over its neighbours. A matching $M$ in $G$ is said to be {\em popular} if there is no other matching $M'$ such that the number of vertices that prefer $M'$ to $M$ is more than the number of vertices that prefer $M$ to $M'$. The goal is to determine, whether a given edge $e$ belongs to some popular matching in $G$. A polynomial-time algorithm for this problem appears in \cite{CK18}. We consider the popular edge problem when some men or women are prioritized or critical. A matching that matches all the critical nodes is termed as a feasible matching. It follows from \cite{Kavitha14,Kavitha21,NNRS21,NN17} that, when $G$ admits a feasible matching, there always exists a matching that is popular among all feasible matchings. We give a polynomial-time algorithm for the popular edge problem in the presence of critical men or women. We also show that an analogous result does not hold in the many-to-one setting, which is known as the Hospital-Residents Problem in literature, even when there are no critical nodes.

Canadian Traveller Problem with Predictions

from arXiv: Data Structures and Algorithms

Authors: Evripidis Bampis, Bruno Escoffier, Michalis Xefteris

In this work, we consider the $k$-Canadian Traveller Problem ($k$-CTP) under the learning-augmented framework proposed by Lykouris & Vassilvitskii. $k$-CTP is a generalization of the shortest path problem, and involves a traveller who knows the entire graph in advance and wishes to find the shortest route from a source vertex $s$ to a destination vertex $t$, but discovers online that some edges (up to $k$) are blocked once reaching them. A potentially imperfect predictor gives us the number and the locations of the blocked edges.

We present a deterministic and a randomized online algorithm for the learning-augmented $k$-CTP that achieve a tradeoff between consistency (quality of the solution when the prediction is correct) and robustness (quality of the solution when there are errors in the prediction). Moreover, we prove a matching lower bound for the deterministic case establishing that the tradeoff between consistency and robustness is optimal, and show a lower bound for the randomized algorithm. Finally, we prove several deterministic and randomized lower bounds on the competitive ratio of $k$-CTP depending on the prediction error, and complement them, in most cases, with matching upper bounds.

Authors: Evripidis Bampis, Bruno Escoffier, Michalis Xefteris

In this work, we consider the $k$-Canadian Traveller Problem ($k$-CTP) under the learning-augmented framework proposed by Lykouris & Vassilvitskii. $k$-CTP is a generalization of the shortest path problem, and involves a traveller who knows the entire graph in advance and wishes to find the shortest route from a source vertex $s$ to a destination vertex $t$, but discovers online that some edges (up to $k$) are blocked once reaching them. A potentially imperfect predictor gives us the number and the locations of the blocked edges.

We present a deterministic and a randomized online algorithm for the learning-augmented $k$-CTP that achieve a tradeoff between consistency (quality of the solution when the prediction is correct) and robustness (quality of the solution when there are errors in the prediction). Moreover, we prove a matching lower bound for the deterministic case establishing that the tradeoff between consistency and robustness is optimal, and show a lower bound for the randomized algorithm. Finally, we prove several deterministic and randomized lower bounds on the competitive ratio of $k$-CTP depending on the prediction error, and complement them, in most cases, with matching upper bounds.

Approximating $(p,2)$ flexible graph connectivity via the primal-dual method

from arXiv: Data Structures and Algorithms

Authors: Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur

We consider the Flexible Graph Connectivity model (denoted FGC) introduced by Adjiashvili, Hommelsheim and M\"uhlenthaler (IPCO 2020, Mathematical Programming 2021), and its generalization, $(p,q)$-FGC, where $p \geq 1$ and $q \geq 0$ are integers, introduced by Boyd et al.\ (FSTTCS 2021). In the $(p,q)$-FGC model, we have an undirected connected graph $G=(V,E)$, non-negative costs $c$ on the edges, and a partition $(\mathcal{S}, \mathcal{U})$ of $E$ into a set of safe edges $\mathcal{S}$ and a set of unsafe edges $\mathcal{U}$. A subset $F \subseteq E$ of edges is called feasible if for any set $F'\subseteq\mathcal{U}$ with $|F'| \leq q$, the subgraph $(V, F \setminus F')$ is $p$-edge connected. The goal is to find a feasible edge-set of minimum cost.

For the special case of $(p,q)$-FGC when $q = 2$, we give an $O(1)$ approximation algorithm, thus improving on the logarithmic approximation ratio of Boyd et al. (FSTTCS 2021). Our algorithm is based on the primal-dual method for covering an uncrossable family, due to Williamson et al. (Combinatorica 1995). We conclude by studying weakly uncrossable families, which are a generalization of the well-known notion of an uncrossable family.

Authors: Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur

We consider the Flexible Graph Connectivity model (denoted FGC) introduced by Adjiashvili, Hommelsheim and M\"uhlenthaler (IPCO 2020, Mathematical Programming 2021), and its generalization, $(p,q)$-FGC, where $p \geq 1$ and $q \geq 0$ are integers, introduced by Boyd et al.\ (FSTTCS 2021). In the $(p,q)$-FGC model, we have an undirected connected graph $G=(V,E)$, non-negative costs $c$ on the edges, and a partition $(\mathcal{S}, \mathcal{U})$ of $E$ into a set of safe edges $\mathcal{S}$ and a set of unsafe edges $\mathcal{U}$. A subset $F \subseteq E$ of edges is called feasible if for any set $F'\subseteq\mathcal{U}$ with $|F'| \leq q$, the subgraph $(V, F \setminus F')$ is $p$-edge connected. The goal is to find a feasible edge-set of minimum cost.

For the special case of $(p,q)$-FGC when $q = 2$, we give an $O(1)$ approximation algorithm, thus improving on the logarithmic approximation ratio of Boyd et al. (FSTTCS 2021). Our algorithm is based on the primal-dual method for covering an uncrossable family, due to Williamson et al. (Combinatorica 1995). We conclude by studying weakly uncrossable families, which are a generalization of the well-known notion of an uncrossable family.

Thursday, September 22

Faculty at Claremont McKenna College (apply by November 15, 2022)

from CCI: jobs
The Department of Mathematical Sciences at Claremont McKenna College invites applications for a tenure-track position, at the assistant professor level, in Probability, Statistics, and Statistical Computing. Website: www.mathjobs.org/jobs/list/20279 Email: sarah.cannon@cmc.edu; Ckao@claremontmckenna.edu

The Department of Mathematical Sciences at Claremont McKenna College invites applications for a tenure-track position, at the assistant professor level, in Probability, Statistics, and Statistical Computing.

Website: https://www.mathjobs.org/jobs/list/20279
Email: sarah.cannon@cmc.edu; Ckao@claremontmckenna.edu

By shacharlovett

Tenure track assistant professor at CUNY’s Baruch College (apply by November 7, 2022)

from CCI: jobs
Baruch College, part of CUNY, lies at the heart of Manhattan. It is regularly ranked as the country’s top college for social mobility. Since Baruch College was traditionally CUNY’s business school, it did not include Computer Science. Our computer science major will start in August 2023. We are hiring professors that will help shape and […]

Baruch College, part of CUNY, lies at the heart of Manhattan. It is regularly ranked as the country’s top college for social mobility. Since Baruch College was traditionally CUNY’s business school, it did not include Computer Science. Our computer science major will start in August 2023. We are hiring professors that will help shape and grow computer science at Baruch.

Website: https://geometrynyc.wixsite.com/csjobs
Email: warren.gordon@baruch.cuny.edu

By shacharlovett

Cheating at Chess—Not Again

from Richard Lipton
Play the opening like a book, the middle game like a magician, and the end game like a machine — Rudolf Spielmann Kenneth Regan is my dear friend and co-writer of this blog. He obtained his doctorate—technically D.Phil not PhD—in 1986 for a thesis titled On the Separation of Complexity Classes from the University of […]


Play the opening like a book, the middle game like a magician, and the end game like a machine — Rudolf Spielmann

Kenneth Regan is my dear friend and co-writer of this blog. He obtained his doctorate—technically D.Phil not PhD—in 1986 for a thesis titled On the Separation of Complexity Classes from the University of Oxford under Dominic Welsh. He has, however, been enmeshed this month in a story quite separate from complexity classes.

It was Ken’s birthday just last week and we wish him many more.

Cheating at Chess

Ken was the 1977 US Junior co-champion and once held the record of youngest USCF Master since Bobby Fischer. He holds the title of International Master with a rating of 2372. Ken is perhaps the strongest chess player ever with a doctorate in complexity theory.

He is certainly the world best at both complexity theory and cheating at chess. Ken is one of the leading experts in detecting cheating in games played in real tournaments.

He has, however, been occupied by a major story that erupted after the world champion, Magnus Carlsen, lost to the American teenager and bottom-rated participant Hans Niemann in the third round of the Sinquefield Cup in St. Louis. The next day, Labor Day, Carlsen abruptly withdrew from the tournament with no explanation beyond a cryptic tweet. This was widely regarded as an insinuation of some kind of cheating. Ken was involved daily monitoring the event and was cited in a subsequent press release as having found nothing amiss.

Nevertheless—really everthemore—this has sparked renewed discussion of cheating at chess and measures to protect tournaments at all levels. Let’s go into that.

Detecting Cheating

How does one cheat at chess? Imagine Bob is playing a game in a live chess tournament. Bob is a strong player but is not nearly as strong as his opponent Ted. How does Bob cheat?

The basic idea is quite simple: Bob uses a computer program {P} to make moves for him. He types Ted’s moves into {P} and then makes its moves. The reason this is so powerful is that the ranking of the computer program {P} is likely much higher than Ted’s. It could be ranked at 3000 or even higher. This means that Bob is likely to not lose to Ted but perhaps even beat him.

The challenge for Bob to cheat in this manner is that he must ask the program {P} for its moves without being detected. Bob is not allowed to have a digital device like a phone or a laptop to ask the program {P} for its next move. This is the challenge that Bob, the cheater, is faced with. He must enter Ted’s last move and then follow {P}‘s move without it being noticed that he invoked the program {P}. This is the challenge that the cheater must solve.

The cheater may be able to send the moves to the program {P} in various ways. In some cases Bob has been found to use some hidden device to get this information to {P}. He also may use clever ways to get the moves from {P}.

Why Is Detection Hard?

Ken is one of the world’s foremost experts on using predictive analytics to help detect computer-assisted cheating in chess tournaments. Why is this hard? There are several reasons that this is difficult: But the central point is expressed by Alexander Grischuk who notes that “only a very stupid Bob who stubbornly plays the computer’s first line” is likely to get detected.

Let’s examine what Grischuk means. Bob as above is trying to use {P}‘s moves to defeat Ted. Grischuk’s point is that Bob is stupid if he blindly uses the first move that the program {P} suggests. Programs often suggest more than one move that is safe to play. This makes detection much harder.

An even more powerful point is that what if Bob consults more than one program. Perhaps Bob checks the top moves from several programs {P_1, P_2, \dots, P_6}. This could make the detection of his cheating even more difficult.

Bob could use similar ideas to make the detection that he is consulting a program even more complicated. This is why Ken’s checking to see if cheating occurred is so difficult. He tries to stay ahead on the detection end. For instance, his model is not predicated on identifying which program was used, and the provisionally-deployed ideas explored with his students here quantify departure from human predictivity apart from any programs.

Consult this for a recent claim that Niemann used anal beads to signal moves. Even Elon Musk raised this possibility. Just an extreme example of why detecting cheating is tough.

Losing in Translation

The chess story took another twist when Carlsen and Niemann faced each other on Monday in the Julius Baer Generations Cup, an online tournament sponsored by Carlsen’s own organization. Carlsen played one move and then resigned the game—again giving no comment. Much effort has been expended in trying to translate exactly what Carlsen meant by losing in this manner.

Two years ago, a story in the Guardian newspaper subtitled “paranoia has become the culture” featured Ken and efforts to avert cheating in tournaments that were moved online on account of the pandemic. Its quoting Ken included an example of translation from English to English:

“The pandemic has brought me as much work in a single day as I have had in a year previously,” said Prof Kenneth Regan, an international chess master and computer scientist whose model is relied on by the sport’s governing body, FIDE, to detect suspicious patterns of play. “It has ruined my sabbatical.”

What Ken actually said was, “It ate my sabbatical.”

Now Ken was mentioned in the Guardian yesterday and again today. Today’s mention linked a longer article on the ChessBase site explaining his methods and conclusions to date. Ken may have more to say after the developments—and ongoing media contacts—settle down.

Open Problems

How will chess come out of the current controversies? I hope Ken had a happy birthday in the meantime.

By rjlipton

Capturing Bisimulation-Invariant Exponential-Time Complexity Classes

from arXiv: Computational Complexity

Authors: Florian Bruse (University of Kassel, Kassel, Germany), David Kronenberger (University of Kassel, Kassel, Germany), Martin Lange (University of Kassel, Kassel, Germany)

Otto's Theorem characterises the bisimulation-invariant PTIME queries over graphs as exactly those that can be formulated in the polyadic mu-calculus, hinging on the Immerman-Vardi Theorem which characterises PTIME (over ordered structures) by First-Order Logic with least fixpoints. This connection has been extended to characterise bisimulation-invariant EXPTIME by an extension of the polyadic mu-calculus with functions on predicates, making use of Immerman's characterisation of EXPTIME by Second-Order Logic with least fixpoints. In this paper we show that the bisimulation-invariant versions of all classes in the exponential time hierarchy have logical counterparts which arise as extensions of the polyadic mu-calculus by higher-order functions. This makes use of the characterisation of k-EXPTIME by Higher-Order Logic (of order k+1) with least fixpoints, due to Freire and Martins.

Authors: Florian Bruse (University of Kassel, Kassel, Germany), David Kronenberger (University of Kassel, Kassel, Germany), Martin Lange (University of Kassel, Kassel, Germany)

Otto's Theorem characterises the bisimulation-invariant PTIME queries over graphs as exactly those that can be formulated in the polyadic mu-calculus, hinging on the Immerman-Vardi Theorem which characterises PTIME (over ordered structures) by First-Order Logic with least fixpoints. This connection has been extended to characterise bisimulation-invariant EXPTIME by an extension of the polyadic mu-calculus with functions on predicates, making use of Immerman's characterisation of EXPTIME by Second-Order Logic with least fixpoints. In this paper we show that the bisimulation-invariant versions of all classes in the exponential time hierarchy have logical counterparts which arise as extensions of the polyadic mu-calculus by higher-order functions. This makes use of the characterisation of k-EXPTIME by Higher-Order Logic (of order k+1) with least fixpoints, due to Freire and Martins.

Schema-Based Automata Determinization

from arXiv: Computational Complexity

Authors: Joachim Niehren (Inria, Université de Lille, France), Momar Sakho (Inria, Université de Lille, France), Antonio Al Serhali (Inria, Université de Lille, France)

We propose an algorithm for schema-based determinization of finite automata on words and of step-wise hedge automata on nested words. The idea is to integrate schema-based cleaning directly into automata determinization. We prove the correctness of our new algorithm and show that it is alway smore efficient than standard determinization followed by schema-based cleaning. Our implementation permits to obtain a small deterministic automaton for an example of an XPath query, where standard determinization yields a huge stepwise hedge automaton for which schema-based cleaning runs out of memory.

Authors: Joachim Niehren (Inria, Université de Lille, France), Momar Sakho (Inria, Université de Lille, France), Antonio Al Serhali (Inria, Université de Lille, France)

We propose an algorithm for schema-based determinization of finite automata on words and of step-wise hedge automata on nested words. The idea is to integrate schema-based cleaning directly into automata determinization. We prove the correctness of our new algorithm and show that it is alway smore efficient than standard determinization followed by schema-based cleaning. Our implementation permits to obtain a small deterministic automaton for an example of an XPath query, where standard determinization yields a huge stepwise hedge automaton for which schema-based cleaning runs out of memory.

BQP is not in NP

from arXiv: Computational Complexity

Authors: Jonah Librande

Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.

Authors: Jonah Librande

Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.

Downward Self-Reducibility in TFNP

from arXiv: Computational Complexity

Authors: Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

A problem is \emph{downward self-reducible} if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is well studied and it is known that all downward self-reducible problems are in \textsc{PSPACE}. In this paper, we initiate the study of downward self-reducible search problems which are guaranteed to have a solution -- that is, the downward self-reducible problems in \textsc{TFNP}. We show that most natural $\PLS$-complete problems are downward self-reducible and any downward self-reducible problem in \textsc{TFNP} is contained in \textsc{PLS}. Furthermore, if the downward self-reducible problem is in \textsc{UTFNP} (i.e. it has a unique solution), then it is actually contained in \textsc{CLS}. This implies that if integer factoring is \emph{downward self-reducible} then it is in fact in \textsc{CLS}, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.

Authors: Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

A problem is \emph{downward self-reducible} if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is well studied and it is known that all downward self-reducible problems are in \textsc{PSPACE}. In this paper, we initiate the study of downward self-reducible search problems which are guaranteed to have a solution -- that is, the downward self-reducible problems in \textsc{TFNP}. We show that most natural $\PLS$-complete problems are downward self-reducible and any downward self-reducible problem in \textsc{TFNP} is contained in \textsc{PLS}. Furthermore, if the downward self-reducible problem is in \textsc{UTFNP} (i.e. it has a unique solution), then it is actually contained in \textsc{CLS}. This implies that if integer factoring is \emph{downward self-reducible} then it is in fact in \textsc{CLS}, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.

The Dispersive Art Gallery Problem

from arXiv: Computational Geometry

Authors: Christian Rieck, Christian Scheffer

We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets with largest possible distances between these guards. To the best of our knowledge, this variant has not been considered before.We call it the Dispersive Art Gallery Problem. In particular, in the dispersive art gallery problem we are given a polygon $\mathcal{P}$ and a real number $\ell$, and want to decide whether $\mathcal{P}$ has a guard set such that every pair of guards in this set is at least a distance of $\ell$ apart.

In this paper, we study the vertex guard variant of this problem for the class of polyominoes. We consider rectangular visibility and distances as geodesics in the $L_1$-metric. Our results are as follows. We give a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most $3$. On the positive side, we describe an algorithm that computes guard sets for simple polyominoes that match this upper bound, i.e., the algorithm constructs worst-case optimal solutions. We also study the computational complexity of computing guard sets that maximize the smallest distance between all pairs of guards within the guard sets. We prove that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least $5$ in a given polyomino is NP-complete.

We were also able to find an optimal dynamic programming approach that computes a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes, i.e., computes optimal solutions. Because the shapes constructed in the NP-hardness reduction are thin as well (but have holes), this result completes the case for thin polyominoes.

Authors: Christian Rieck, Christian Scheffer

We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets with largest possible distances between these guards. To the best of our knowledge, this variant has not been considered before.We call it the Dispersive Art Gallery Problem. In particular, in the dispersive art gallery problem we are given a polygon $\mathcal{P}$ and a real number $\ell$, and want to decide whether $\mathcal{P}$ has a guard set such that every pair of guards in this set is at least a distance of $\ell$ apart.

In this paper, we study the vertex guard variant of this problem for the class of polyominoes. We consider rectangular visibility and distances as geodesics in the $L_1$-metric. Our results are as follows. We give a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most $3$. On the positive side, we describe an algorithm that computes guard sets for simple polyominoes that match this upper bound, i.e., the algorithm constructs worst-case optimal solutions. We also study the computational complexity of computing guard sets that maximize the smallest distance between all pairs of guards within the guard sets. We prove that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least $5$ in a given polyomino is NP-complete.

We were also able to find an optimal dynamic programming approach that computes a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes, i.e., computes optimal solutions. Because the shapes constructed in the NP-hardness reduction are thin as well (but have holes), this result completes the case for thin polyominoes.

Efficient inspection of underground galleries using k robots with limited energy

from arXiv: Computational Geometry

Authors: Sergey Bereg, L. Evaristo Caraballo, José Miguel Díaz-Báñez

We study the problem of optimally inspecting an underground (underwater) gallery with k agents. We consider a gallery with a single opening and with a tree topology rooted at the opening. Due to the small diameter of the pipes (caves), the agents are small robots with limited autonomy and there is a supply station at the gallery's opening. Therefore, they are initially placed at the root and periodically need to return to the supply station. Our goal is to design off-line strategies to efficiently cover the tree with $k$ small robots. We consider two objective functions: the covering time (maximum collective time) and the covering distance (total traveled distance). The maximum collective time is the maximum time spent by a robot needs to finish its assigned task (assuming that all the robots start at the same time); the total traveled distance is the sum of the lengths of all the covering walks. Since the problems are intractable for big trees, we propose approximation algorithms. Both efficiency and accuracy of the suboptimal solutions are empirically showed for random trees through intensive numerical experiments.

Authors: Sergey Bereg, L. Evaristo Caraballo, José Miguel Díaz-Báñez

We study the problem of optimally inspecting an underground (underwater) gallery with k agents. We consider a gallery with a single opening and with a tree topology rooted at the opening. Due to the small diameter of the pipes (caves), the agents are small robots with limited autonomy and there is a supply station at the gallery's opening. Therefore, they are initially placed at the root and periodically need to return to the supply station. Our goal is to design off-line strategies to efficiently cover the tree with $k$ small robots. We consider two objective functions: the covering time (maximum collective time) and the covering distance (total traveled distance). The maximum collective time is the maximum time spent by a robot needs to finish its assigned task (assuming that all the robots start at the same time); the total traveled distance is the sum of the lengths of all the covering walks. Since the problems are intractable for big trees, we propose approximation algorithms. Both efficiency and accuracy of the suboptimal solutions are empirically showed for random trees through intensive numerical experiments.

Characterizing the Decidability of Finite State Automata Team Games with Communication

from arXiv: Data Structures and Algorithms

Authors: Michael Coulombe (Massachusetts Institute of Technology), Jayson Lynch (Cheriton School of Computer Science, University of Waterloo)

In this paper we define a new model of limited communication for multiplayer team games of imperfect information. We prove that the Team DFA Game and Team Formula Game, which have bounded state, remain undecidable when players have a rate of communication which is less than the rate at which they make moves in the game. We also show that meeting this communication threshold causes these games to be decidable.

Authors: Michael Coulombe (Massachusetts Institute of Technology), Jayson Lynch (Cheriton School of Computer Science, University of Waterloo)

In this paper we define a new model of limited communication for multiplayer team games of imperfect information. We prove that the Team DFA Game and Team Formula Game, which have bounded state, remain undecidable when players have a rate of communication which is less than the rate at which they make moves in the game. We also show that meeting this communication threshold causes these games to be decidable.

Parametric Synthesis of Computational Circuits for Complex Quantum Algorithms

from arXiv: Data Structures and Algorithms

Authors: Cesar Borisovich Pronin, Andrey Vladimirovich Ostroukh

At the moment, quantum circuits are created mainly by manually placing logic elements on lines that symbolize quantum bits. The purpose of creating Quantum Circuit Synthesizer "Naginata" was due to the fact that even with a slight increase in the number of operations in a quantum algorithm, leads to the significant increase in size of the corresponding quantum circuit. This causes serious difficulties both in creating and debugging these quantum circuits. The purpose of our quantum synthesizer is enabling users an opportunity to implement quantum algorithms using higher-level commands. This is achieved by creating generic blocks for frequently used operations such as: the adder, multiplier, digital comparator (comparison operator), etc. Thus, the user could implement a quantum algorithm by using these generic blocks, and the quantum synthesizer would create a suitable circuit for this algorithm, in a format that is supported by the chosen quantum computation environment. This approach greatly simplifies the processes of development and debugging a quantum algorithm. The proposed approach for implementing quantum algorithms has a potential application in the field of machine learning, in this regard, we provided an example of creating a circuit for training a simple neural network. Neural networks have a significant impact on the technological development of the transport and road complex, and there is a potential for improving the reliability and efficiency of their learning process by utilizing quantum computation, through the introduction of quantum computing.

Authors: Cesar Borisovich Pronin, Andrey Vladimirovich Ostroukh

At the moment, quantum circuits are created mainly by manually placing logic elements on lines that symbolize quantum bits. The purpose of creating Quantum Circuit Synthesizer "Naginata" was due to the fact that even with a slight increase in the number of operations in a quantum algorithm, leads to the significant increase in size of the corresponding quantum circuit. This causes serious difficulties both in creating and debugging these quantum circuits. The purpose of our quantum synthesizer is enabling users an opportunity to implement quantum algorithms using higher-level commands. This is achieved by creating generic blocks for frequently used operations such as: the adder, multiplier, digital comparator (comparison operator), etc. Thus, the user could implement a quantum algorithm by using these generic blocks, and the quantum synthesizer would create a suitable circuit for this algorithm, in a format that is supported by the chosen quantum computation environment. This approach greatly simplifies the processes of development and debugging a quantum algorithm. The proposed approach for implementing quantum algorithms has a potential application in the field of machine learning, in this regard, we provided an example of creating a circuit for training a simple neural network. Neural networks have a significant impact on the technological development of the transport and road complex, and there is a potential for improving the reliability and efficiency of their learning process by utilizing quantum computation, through the introduction of quantum computing.

Exact and Sampling Methods for Mining Higher-Order Motifs in Large Hypergraphs

from arXiv: Data Structures and Algorithms

Authors: Quintino Francesco Lotito, Federico Musciotto, Federico Battiston, Alberto Montresor

Network motifs are patterns of interactions occurring among a small set of nodes in a graph. They highlight fundamental aspects of the interplay between the topology and the dynamics of complex networks and have a wide range of real-world applications. Motif analysis has been extended to a variety of network models that allow for a richer description of the interactions of a system, including weighted, temporal, multilayer, and, more recently, higher-order networks. Generalizing network motifs to capture patterns of group interactions is not only interesting from the fundamental perspective of understanding complex systems, but also proposes unprecedented computational challenges. In this work, we focus on the problem of counting occurrences of sub-hypergraph patterns in very large higher-order networks. We show that, by directly exploiting higher-order structures, we speed up the counting process compared to applying traditional data mining techniques for network motifs. Moreover, by including hyperedge sampling techniques, computational complexity is further reduced at the cost of small errors in the estimation of motif frequency. We evaluate our algorithms on several real-world datasets describing face-to-face interactions, co-authorship and human communication. We show that our approximated algorithm not only allows to speed up the performance, but also to extract larger higher-order motifs beyond the computational limits of an exact approach.

Authors: Quintino Francesco Lotito, Federico Musciotto, Federico Battiston, Alberto Montresor

Network motifs are patterns of interactions occurring among a small set of nodes in a graph. They highlight fundamental aspects of the interplay between the topology and the dynamics of complex networks and have a wide range of real-world applications. Motif analysis has been extended to a variety of network models that allow for a richer description of the interactions of a system, including weighted, temporal, multilayer, and, more recently, higher-order networks. Generalizing network motifs to capture patterns of group interactions is not only interesting from the fundamental perspective of understanding complex systems, but also proposes unprecedented computational challenges. In this work, we focus on the problem of counting occurrences of sub-hypergraph patterns in very large higher-order networks. We show that, by directly exploiting higher-order structures, we speed up the counting process compared to applying traditional data mining techniques for network motifs. Moreover, by including hyperedge sampling techniques, computational complexity is further reduced at the cost of small errors in the estimation of motif frequency. We evaluate our algorithms on several real-world datasets describing face-to-face interactions, co-authorship and human communication. We show that our approximated algorithm not only allows to speed up the performance, but also to extract larger higher-order motifs beyond the computational limits of an exact approach.

On Reachable Assignments under Dichotomous Preferences

from arXiv: Data Structures and Algorithms

Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents. In particular, we consider the situation where each agent has a dichotomous preference over the items, that is, each agent evaluates each item as acceptable or unacceptable. Furthermore, we assume that communication between agents is limited, and the relationship is represented by an undirected graph. Then, a pair of agents can exchange their items only if they are connected by an edge and the involved items are acceptable. We prove that this problem is PSPACE-complete even when the communication graph is complete (that is, every pair of agents can exchange their items), and this problem can be solved in polynomial time if an input graph is a tree.

Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents. In particular, we consider the situation where each agent has a dichotomous preference over the items, that is, each agent evaluates each item as acceptable or unacceptable. Furthermore, we assume that communication between agents is limited, and the relationship is represented by an undirected graph. Then, a pair of agents can exchange their items only if they are connected by an edge and the involved items are acceptable. We prove that this problem is PSPACE-complete even when the communication graph is complete (that is, every pair of agents can exchange their items), and this problem can be solved in polynomial time if an input graph is a tree.

Improved Approximation for Two-Edge-Connectivity

from arXiv: Data Structures and Algorithms

Authors: Mohit Garg, Fabrizio Grandoni, Afrouz Jabal Ameli

The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the $2$-Edge-Connected Spanning Subgraph problem (2-ECSS): given an undirected graph $G$, find a $2$-edge-connected spanning subgraph $H$ of $G$ with the minimum number of edges (in particular, $H$ remains connected after the removal of one arbitrary edge).

2-ECSS is NP-hard and the best-known (polynomial-time) approximation factor for this problem is $4/3$. Interestingly, this factor was achieved with drastically different techniques by [Hunkenschr{\"o}der, Vempala and Vetta '00,'19] and [Seb{\"o} and Vygen, '14]. In this paper we present an improved $\frac{118}{89}+\epsilon<1.326$ approximation for 2-ECSS.

The key ingredient in our approach (which might also be helpful in future work) is a reduction to a special type of structured graphs: our reduction preserves approximation factors up to $6/5$. While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are "almost" 3-vertex-connected: more precisely, given any 2-vertex-cut $\{u,v\}$ of a structured graph $G=(V,E)$, $G[V\setminus \{u,v\}]$ has exactly 2 connected components, one of which contains exactly one node of degree $2$ in $G$.

Authors: Mohit Garg, Fabrizio Grandoni, Afrouz Jabal Ameli

The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the $2$-Edge-Connected Spanning Subgraph problem (2-ECSS): given an undirected graph $G$, find a $2$-edge-connected spanning subgraph $H$ of $G$ with the minimum number of edges (in particular, $H$ remains connected after the removal of one arbitrary edge).

2-ECSS is NP-hard and the best-known (polynomial-time) approximation factor for this problem is $4/3$. Interestingly, this factor was achieved with drastically different techniques by [Hunkenschr{\"o}der, Vempala and Vetta '00,'19] and [Seb{\"o} and Vygen, '14]. In this paper we present an improved $\frac{118}{89}+\epsilon<1.326$ approximation for 2-ECSS.

The key ingredient in our approach (which might also be helpful in future work) is a reduction to a special type of structured graphs: our reduction preserves approximation factors up to $6/5$. While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are "almost" 3-vertex-connected: more precisely, given any 2-vertex-cut $\{u,v\}$ of a structured graph $G=(V,E)$, $G[V\setminus \{u,v\}]$ has exactly 2 connected components, one of which contains exactly one node of degree $2$ in $G$.

Avoid One's Doom: Finding Cliff-Edge Configurations in Petri Nets

from arXiv: Data Structures and Algorithms

Authors: Giann Karlo Aguirre-Samboní (INRIA and LMF, CNRS and ENS Paris-Saclay, Université Paris-Saclay), Stefan Haar (INRIA and LMF, CNRS and ENS Paris-Saclay, Université Paris-Saclay), Loïc Paulevé (Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800), Stefan Schwoon (INRIA and LMF, CNRS and ENS Paris-Saclay, Université Paris-Saclay), Nick Würdemann (Department of Computing Science, University of Oldenburg)

A crucial question in analyzing a concurrent system is to determine its long-run behaviour, and in particular, whether there are irreversible choices in its evolution, leading into parts of the reachability space from which there is no return to other parts. Casting this problem in the unifying framework of safe Petri nets, our previous work has provided techniques for identifying attractors, i.e. terminal strongly connected components of the reachability space, whose attraction basins we wish to determine. Here, we provide a solution for the case of safe Petri nets. Our algorithm uses net unfoldings and provides a map of all of the system's configurations (concurrent executions) that act as cliff-edges, i.e. any maximal extension for those configurations lies in some basin that is considered fatal. The computation turns out to require only a relatively small prefix of the unfolding, just twice the depth of Esparza's complete prefix.

Authors: Giann Karlo Aguirre-Samboní (INRIA and LMF, CNRS and ENS Paris-Saclay, Université Paris-Saclay), Stefan Haar (INRIA and LMF, CNRS and ENS Paris-Saclay, Université Paris-Saclay), Loïc Paulevé (Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800), Stefan Schwoon (INRIA and LMF, CNRS and ENS Paris-Saclay, Université Paris-Saclay), Nick Würdemann (Department of Computing Science, University of Oldenburg)

A crucial question in analyzing a concurrent system is to determine its long-run behaviour, and in particular, whether there are irreversible choices in its evolution, leading into parts of the reachability space from which there is no return to other parts. Casting this problem in the unifying framework of safe Petri nets, our previous work has provided techniques for identifying attractors, i.e. terminal strongly connected components of the reachability space, whose attraction basins we wish to determine. Here, we provide a solution for the case of safe Petri nets. Our algorithm uses net unfoldings and provides a map of all of the system's configurations (concurrent executions) that act as cliff-edges, i.e. any maximal extension for those configurations lies in some basin that is considered fatal. The computation turns out to require only a relatively small prefix of the unfolding, just twice the depth of Esparza's complete prefix.

Quasipolynomial-time algorithms for repulsive Gibbs point processes

from arXiv: Data Structures and Algorithms

Authors: Matthew Jenssen, Marcus Michelen, Mohan Ravichandran

We demonstrate a quasipolynomial-time deterministic approximation algorithm for the partition function of a Gibbs point process interacting via a repulsive potential. This result holds for all activities $\lambda$ for which the partition function satisfies a zero-free assumption in a neighborhood of the interval $[0,\lambda]$. As a corollary, we obtain a quasipolynomial-time deterministic approximation algorithm for all $\lambda < e/\Delta_\phi$, where $\Delta_\phi$ is the potential-weighted connective constant of the potential $\phi$. Our algorithm approximates coefficients of the cluster expansion of the partition function and uses the interpolation method of Barvinok to extend this approximation throughout the zero-free region.

Authors: Matthew Jenssen, Marcus Michelen, Mohan Ravichandran

We demonstrate a quasipolynomial-time deterministic approximation algorithm for the partition function of a Gibbs point process interacting via a repulsive potential. This result holds for all activities $\lambda$ for which the partition function satisfies a zero-free assumption in a neighborhood of the interval $[0,\lambda]$. As a corollary, we obtain a quasipolynomial-time deterministic approximation algorithm for all $\lambda < e/\Delta_\phi$, where $\Delta_\phi$ is the potential-weighted connective constant of the potential $\phi$. Our algorithm approximates coefficients of the cluster expansion of the partition function and uses the interpolation method of Barvinok to extend this approximation throughout the zero-free region.

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification

from arXiv: Data Structures and Algorithms

Authors: Arun Jambulapati, Yang P. Liu, Aaron Sidford

We present an algorithm that given any $n$-vertex, $m$-edge, rank $r$ hypergraph constructs a spectral sparsifier with $O(n \varepsilon^{-2} \log n \log r)$ hyperedges in nearly-linear $\widetilde{O}(mr)$ time. This improves in both size and efficiency over a line of work (Bansal-Svensson-Trevisan 2019, Kapralov-Krauthgamer-Tardos-Yoshida 2021) for which the previous best size was $O(\min\{n \varepsilon^{-4} \log^3 n,nr^3 \varepsilon^{-2} \log n\})$ and runtime was $\widetilde{O}(mr + n^{O(1)})$.

Independent Result: In an independent work, Lee (Lee 2022) also shows how to compute a spectral hypergraph sparsifier with $O(n \varepsilon^{-2} \log n \log r)$ hyperedges.

Authors: Arun Jambulapati, Yang P. Liu, Aaron Sidford

We present an algorithm that given any $n$-vertex, $m$-edge, rank $r$ hypergraph constructs a spectral sparsifier with $O(n \varepsilon^{-2} \log n \log r)$ hyperedges in nearly-linear $\widetilde{O}(mr)$ time. This improves in both size and efficiency over a line of work (Bansal-Svensson-Trevisan 2019, Kapralov-Krauthgamer-Tardos-Yoshida 2021) for which the previous best size was $O(\min\{n \varepsilon^{-4} \log^3 n,nr^3 \varepsilon^{-2} \log n\})$ and runtime was $\widetilde{O}(mr + n^{O(1)})$.

Independent Result: In an independent work, Lee (Lee 2022) also shows how to compute a spectral hypergraph sparsifier with $O(n \varepsilon^{-2} \log n \log r)$ hyperedges.

Wednesday, September 21

POSTED UPDATED VERSION OF Computers and Intractability: A guide to Algorithmic Lower Bounds posted (New title)

from Computational Complexity

We have posted a revised version of 


Computational Intractability: A Guide to Algorithmic Lower Bounds

by Demaine-Gasarch-Hajiaghayi

The book is here.

(For the original post about it, edited it to use the new title (see below), see HERE.) 


We  changed the title (the title above is the new one) 

since the earlier title looked too much

like the title of Garey's and Johnson's classic. While that was intentional we 

later felt that it was too close to their title and might cause confusion. 

Of course changing the title might also cause confusion; however, 

this post (and we will email various people as well) will stem that confusion. 


We welcome corrections, suggestions and comments on the book. Email us at hardness-book@mit.edu


By gasarch

We have posted a revised version of 


Computational Intractability: A Guide to Algorithmic Lower Bounds

by Demaine-Gasarch-Hajiaghayi

The book is here.

(For the original post about it, edited it to use the new title (see below), see HERE.) 


We  changed the title (the title above is the new one) 

since the earlier title looked too much

like the title of Garey's and Johnson's classic. While that was intentional we 

later felt that it was too close to their title and might cause confusion. 

Of course changing the title might also cause confusion; however, 

this post (and we will email various people as well) will stem that confusion. 


We welcome corrections, suggestions and comments on the book. Email us at hardness-book@mit.edu


By gasarch

Counting paths in convex polygons

from David Eppstein
Let’s count non-crossing paths through the all points of a convex polygon. There is a very simple formula for this, \(n2^{n-3}\) undirected paths through an \(n\)-gon, but why? Here’s a simple coloring-based argument that immediately gives this formula.

Let’s count non-crossing paths through the all points of a convex polygon. There is a very simple formula for this, \(n2^{n-3}\) undirected paths through an \(n\)-gon, but why? Here’s a simple coloring-based argument that immediately gives this formula.

Choose a coloring for the points of the polygon, red and blue, and choose a starting point for the path. Build a path, starting from this point, by the following rule: if you are at a red point, go to the next available point clockwise, and if you are at a blue point, go to the next available point counterclockwise.

Generating a non-crossing path through all points of a convex polygon, by using a 2-coloring of the points to determing the direction of each step

There are \(n2^n\) choices of starting point and coloring, but each path is counted eight times, because the colors of the last two points on the path don’t make a difference to where it goes, and because each path is also traced in the opposite direction using the other end as its starting point. Dividing \(n2^n\) by eight gives the formula.

This same idea also works to count non-crossing paths that are allowed to skip some of the points of the polygon. Now, color each point red, blue, or yellow. Use the same rule for building a path, but ignore the yellow points: start on a red or blue point, and when searching for an available point only go to another red or blue point.

Generating a non-crossing path through some points of a convex polygon, by using a 3-coloring of the points to determing the direction of each step

There are \(3^n\) choices of coloring. They have different numbers of choices of starting point, but by cyclically permuting the colors you can group them into \(3^{n-1}\) triples of colorings that together have exactly \(2n\) available (non-yellow) starting points. Each path is counted eight times just like before, so this argument would seem to give the formula \(2n\cdot 3^{n-1} / 8\) for the number of paths. But it’s not quite right. For one thing, it’s not even an integer.

The problem is, what happens when you color all but one of the points yellow, and that one remaining point red or blue? You get a sequence of one point only: does that count as a path? If we count these as length-zero paths (as I would prefer), then they are undercounted, because they do not have two ends, and they only have one point whose coloring (red or blue) is irrelevant, rather than the usual two points. When we divide by eight we make their contribution too small. If we don’t count them (as OEIS tells me was the definition used in a 2020 Bulgarian mathematics contest) then they are overcounted, because they contribute to the formula and shouldn’t.

Adjusting for these one-point paths gives two alternative formulas:

\[\frac{n}{4}(3^{n-1}+3)\]

if we are counting one-point zero-length paths, or

\[\frac{n}{4}(3^{n-1}-1),\]

the formula from OEIS, if we are not counting them.

(Discuss on Mastodon)

By David Eppstein

postdoc at TU Eindhoven, University of Amsterdam, Leiden University, CWI (apply by October 31, 2022)

from CCI: jobs
The NETWORKS project is a collaboration of world-leading researchers from four institutions in The Netherlands: TU Eindhoven, University of Amsterdam, Leiden University and CWI. Research in NETWORKS focuses on stochastics and algorithmics for network problems. Would you like to become a postdoc in the NETWORKS project? Then we invite you to apply for one of […]

The NETWORKS project is a collaboration of world-leading researchers from four institutions in The Netherlands: TU Eindhoven, University of Amsterdam, Leiden University and CWI. Research in NETWORKS focuses on stochastics and algorithmics for network problems. Would you like to become a postdoc in the NETWORKS project? Then we invite you to apply for one of these positions.

Website: https://www.thenetworkcenter.nl/Open-Positions/openposition/30/8-Postdoctoral-fellows-in-Stochastics-and-Algorithmics-COFUND-
Email: info@thenetworkcenter.nl

By shacharlovett

TCS+ talk: Wednesday, September 28 — Joakim Blikstad, KTH Stockholm

from TCS+ Seminar Series
The next TCS+ talk will take place this coming Wednesday, September 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Joakim Blikstad from KTH Stockholm will speak about “Nearly Optimal Communication and Query Complexity of Bipartite Matching” (abstract below). You can reserve a spot as an individual or […]

The next TCS+ talk will take place this coming Wednesday, September 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Joakim Blikstad from KTH Stockholm will speak about “Nearly Optimal Communication and Query Complexity of Bipartite Matching” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: With a simple application of the cutting planes method, we settle the complexities of the bipartite maximum matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models. Our results answer open problems that have been raised repeatedly since at least three decades ago [Hajnal, Maass, and Turan STOC’88; Ivanyos, Klauck, Lee, Santha, and de Wolf FSTTCS’12; Dobzinski, Nisan, and Oren STOC’14; Nisan SODA’21] and tighten the lower bounds shown by Beniamini and Nisan [STOC’21] and Zhang [ICALP’04]. Our communication protocols also work for some generalizations of BMM, such as maximum-cost bipartite b-matching and transshipment, using only Õ(|V|) bits of communications.

To appear in FOCS’22. Joint work with Jan van den Brand, Yuval Efron, Danupon Nanongkai, and Sagnik Mukhopadhyay. preprint: https://arxiv.org/abs/2208.02526

By plustcs

Teaching professor at UC San Diego (apply by October 15, 2022)

from CCI: jobs
UC San Diego Computer Science department seeks applications for an Assistant Teaching Professor. Teaching Professors are full members of the academic senate and are eligible for Security of Employment, analogous to tenure. Teaching Professors have an increased emphasis on teaching, while maintaining an active program of research, in their research area and/or education. Website: apol-recruit.ucsd.edu/JPF03253 […]

UC San Diego Computer Science department seeks applications for an Assistant Teaching Professor. Teaching Professors are full members of the academic senate and are eligible for Security of Employment, analogous to tenure. Teaching Professors have an increased emphasis on teaching, while maintaining an active program of research, in their research area and/or education.

Website: https://apol-recruit.ucsd.edu/JPF03253
Email: shachar.lovett@gmail.com

By shacharlovett

Intrinsic Simulations and Universality in Automata Networks

from arXiv: Computational Complexity

Authors: Martín Ríos-Wilson, Guillaume Theyssier (I2M)

An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. They are studied both from the dynamical and the computational complexity point of view. Inspired from well-established notions in the context of cellular automata, we develop a theory of intrinsic simulations and universality for families of automata networks. We establish many consequences of intrinsic universality in terms of complexity of orbits (periods of attractors, transients, etc) as well as hardness of the standard well-studied decision problems for automata networks (short/long term prediction, reachability, etc). In the way, we prove orthogonality results for these problems: the hardness of a single one does not imply hardness of the others, while intrinsic universality implies hardness of all of them. As a complement, we develop a proof technique to establish intrinsic simulation and universality results which is suitable to deal with families of symmetric networks were connections are non-oriented. It is based on an operation of glueing of networks, which allows to produce complex orbits in large networks from compatible pseudo-orbits in small networks. As an illustration, we give a short proof that the family of networks were each node obeys the rule of the 'game of life' cellular automaton is strongly universal. This formalism and proof technique is also applied in a companion paper devoted to studying the effect of update schedules on intrinsic universality for concrete symmetric families of automata networks.

Authors: Martín Ríos-Wilson, Guillaume Theyssier (I2M)

An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. They are studied both from the dynamical and the computational complexity point of view. Inspired from well-established notions in the context of cellular automata, we develop a theory of intrinsic simulations and universality for families of automata networks. We establish many consequences of intrinsic universality in terms of complexity of orbits (periods of attractors, transients, etc) as well as hardness of the standard well-studied decision problems for automata networks (short/long term prediction, reachability, etc). In the way, we prove orthogonality results for these problems: the hardness of a single one does not imply hardness of the others, while intrinsic universality implies hardness of all of them. As a complement, we develop a proof technique to establish intrinsic simulation and universality results which is suitable to deal with families of symmetric networks were connections are non-oriented. It is based on an operation of glueing of networks, which allows to produce complex orbits in large networks from compatible pseudo-orbits in small networks. As an illustration, we give a short proof that the family of networks were each node obeys the rule of the 'game of life' cellular automaton is strongly universal. This formalism and proof technique is also applied in a companion paper devoted to studying the effect of update schedules on intrinsic universality for concrete symmetric families of automata networks.

VEST is W[2]-hard

from arXiv: Computational Complexity

Authors: Michael Skotnica

In this short note, we show that the problem of VEST is $W[2]$-hard for parameter $k$. This strengthens a result of Matou\v{s}ek, who showed $W[1]$-hardness of that problem. The consequence of this result is that computing the $k$-th homotopy group of a $d$-dimensional space for $d > 3$ is $W[2]$-hard for parameter $k$.

Authors: Michael Skotnica

In this short note, we show that the problem of VEST is $W[2]$-hard for parameter $k$. This strengthens a result of Matou\v{s}ek, who showed $W[1]$-hardness of that problem. The consequence of this result is that computing the $k$-th homotopy group of a $d$-dimensional space for $d > 3$ is $W[2]$-hard for parameter $k$.

A tight bound for the number of edges of matchstick graphs

from arXiv: Computational Geometry

Authors: Jérémy Lavollée, Konrad Swanepoel

A matchstick graph is a plane graph with edges drawn as unit-distance line segments. Harborth introduced these graphs in 1986 and conjectured that the maximum number of edges for a matchstick graph on $n$ vertices is $\lfloor 3n-\sqrt{12n-3} \rfloor$. In this paper we prove this conjecture for all $n\geq 1$. The main geometric ingredient of the proof is an isoperimetric inequality related to Lhuilier's inequality.

Authors: Jérémy Lavollée, Konrad Swanepoel

A matchstick graph is a plane graph with edges drawn as unit-distance line segments. Harborth introduced these graphs in 1986 and conjectured that the maximum number of edges for a matchstick graph on $n$ vertices is $\lfloor 3n-\sqrt{12n-3} \rfloor$. In this paper we prove this conjecture for all $n\geq 1$. The main geometric ingredient of the proof is an isoperimetric inequality related to Lhuilier's inequality.

Natural Wave Numbers, Natural Wave Co-numbers, and the Computation of the Primes

from arXiv: Data Structures and Algorithms

Authors: Terence R. Smith

The paper exploits an isomorphism between the natural numbers N and a space U of periodic sequences of the roots of unity in constructing a recursive procedure for representing and computing the prime numbers. The nth wave number ${\bf u}_n$ is the countable sequence of the nth roots of unity having frequencies k/n for all integer phases k. The space U is closed under a commutative and associative binary operation ${\bf u}_m \odot{\bf u}_n={\bf u}_{mn}$, termed the circular product, and is isomorphic with N under their respective product operators. Functions are defined on U that partition wave numbers into two complementary sequences, of which the co-number $ {\overset {\bf \ast }{ \bf u}}_n$ is a function of a wave number in which zeros replace its positive roots of unity. The recursive procedure $ {\overset {\bf \ast }{ \bf U}}_{N+1}= {\overset {\bf \ast }{ \bf U}}_{N}\odot{\overset {\bf \ast }{\bf u}}_{{N+1}}$ represents prime numbers explicitly in terms of preceding prime numbers, starting with $p_1=2$, and is shown never to terminate. If ${p}_1, ... , { p}_{N+1}$ are the first $N+1$ prime phases, then the phases in the range $p_{N+1} \leq k < p^2_{N+1}$ that are associated with the non-zero terms of $ {\overset {\bf \ast }{\bf U}}_{N}$ are, together with $ p_1, ...,p_N$, all of the prime phases less than $p^2_{N+1}$. When applied with all of the primes identified at the previous step, the recursive procedure identifies approximately $7^{2(N-1)}/(2(N-1)ln7)$ primes at each iteration for $ N>1$. When the phases of wave numbers are represented in modular arithmetic, the prime phases are representable in terms of sums of reciprocals of the initial set of prime phases and have a relation with the zeta-function.

Authors: Terence R. Smith

The paper exploits an isomorphism between the natural numbers N and a space U of periodic sequences of the roots of unity in constructing a recursive procedure for representing and computing the prime numbers. The nth wave number ${\bf u}_n$ is the countable sequence of the nth roots of unity having frequencies k/n for all integer phases k. The space U is closed under a commutative and associative binary operation ${\bf u}_m \odot{\bf u}_n={\bf u}_{mn}$, termed the circular product, and is isomorphic with N under their respective product operators. Functions are defined on U that partition wave numbers into two complementary sequences, of which the co-number $ {\overset {\bf \ast }{ \bf u}}_n$ is a function of a wave number in which zeros replace its positive roots of unity. The recursive procedure $ {\overset {\bf \ast }{ \bf U}}_{N+1}= {\overset {\bf \ast }{ \bf U}}_{N}\odot{\overset {\bf \ast }{\bf u}}_{{N+1}}$ represents prime numbers explicitly in terms of preceding prime numbers, starting with $p_1=2$, and is shown never to terminate. If ${p}_1, ... , { p}_{N+1}$ are the first $N+1$ prime phases, then the phases in the range $p_{N+1} \leq k < p^2_{N+1}$ that are associated with the non-zero terms of $ {\overset {\bf \ast }{\bf U}}_{N}$ are, together with $ p_1, ...,p_N$, all of the prime phases less than $p^2_{N+1}$. When applied with all of the primes identified at the previous step, the recursive procedure identifies approximately $7^{2(N-1)}/(2(N-1)ln7)$ primes at each iteration for $ N>1$. When the phases of wave numbers are represented in modular arithmetic, the prime phases are representable in terms of sums of reciprocals of the initial set of prime phases and have a relation with the zeta-function.

Data structures for topologically sound higher-dimensional diagram rewriting

from arXiv: Data Structures and Algorithms

Authors: Amar Hadzihasanovic, Diana Kessler

We present a computational implementation of diagrammatic sets, a model of higher-dimensional diagram rewriting that is "topologically sound": diagrams admit a functorial interpretation as homotopies in cell complexes. This has potential applications both in the formalisation of higher algebra and category theory and in computational algebraic topology. We describe data structures for well-formed shapes of diagrams of arbitrary dimensions and provide a solution to their isomorphism problem in time $O(n^3 \log n)$. On top of this, we define a type theory for rewriting in diagrammatic sets and provide a semantic characterisation of its syntactic category. All data structures and algorithms are implemented in the Python library rewalt, which also supports various visualisations of diagrams.

Authors: Amar Hadzihasanovic, Diana Kessler

We present a computational implementation of diagrammatic sets, a model of higher-dimensional diagram rewriting that is "topologically sound": diagrams admit a functorial interpretation as homotopies in cell complexes. This has potential applications both in the formalisation of higher algebra and category theory and in computational algebraic topology. We describe data structures for well-formed shapes of diagrams of arbitrary dimensions and provide a solution to their isomorphism problem in time $O(n^3 \log n)$. On top of this, we define a type theory for rewriting in diagrammatic sets and provide a semantic characterisation of its syntactic category. All data structures and algorithms are implemented in the Python library rewalt, which also supports various visualisations of diagrams.

Exact Matching and the Top-k Perfect Matching Problem

from arXiv: Data Structures and Algorithms

Authors: Nicolas El Maalouly, Lasse Wulf

The aim of this note is to provide a reduction of the Exact Matching problem to the Top-$k$ Perfect Matching Problem. Together with earlier work by El Maalouly, this shows that the two problems are polynomial-time equivalent.

The Exact Matching Problem is a well-known 40 years old problem for which a randomized, but no deterministic poly-time algorithm has been discovered. The Top-$k$ Perfect Matching Problem is the problem of finding a perfect matching which maximizes the total weight of the $k$ heaviest edges contained in it.

Authors: Nicolas El Maalouly, Lasse Wulf

The aim of this note is to provide a reduction of the Exact Matching problem to the Top-$k$ Perfect Matching Problem. Together with earlier work by El Maalouly, this shows that the two problems are polynomial-time equivalent.

The Exact Matching Problem is a well-known 40 years old problem for which a randomized, but no deterministic poly-time algorithm has been discovered. The Top-$k$ Perfect Matching Problem is the problem of finding a perfect matching which maximizes the total weight of the $k$ heaviest edges contained in it.

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint

from arXiv: Data Structures and Algorithms

Authors: Max Klimm, Martin Knaack

This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature $B$ of the submodular function. For the extreme cases $c=0$ corresponding to a modular objective, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c=1$ it yields a robustness factor of $\approx 0.35$ improving over the best previously known robustness factor of $\approx 0.06$.

Authors: Max Klimm, Martin Knaack

This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature $B$ of the submodular function. For the extreme cases $c=0$ corresponding to a modular objective, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c=1$ it yields a robustness factor of $\approx 0.35$ improving over the best previously known robustness factor of $\approx 0.06$.

Development of a Parallel BAT and Its Applications in Binary-state Network Reliability Problems

from arXiv: Data Structures and Algorithms

Authors: Wei-Chang Yeh

Various networks are broadly and deeply applied in real-life applications. Reliability is the most important index for measuring the performance of all network types. Among the various algorithms, only implicit enumeration algorithms, such as depth-first-search, breadth-search-first, universal generating function methodology, binary-decision diagram, and binary-addition-tree algorithm (BAT), can be used to calculate the exact network reliability. However, implicit enumeration algorithms can only be used to solve small-scale network reliability problems. The BAT was recently proposed as a simple, fast, easy-to-code, and flexible make-to-fit exact-solution algorithm. Based on the experimental results, the BAT and its variants outperformed other implicit enumeration algorithms. Hence, to overcome the above-mentioned obstacle as a result of the size problem, a new parallel BAT (PBAT) was proposed to improve the BAT based on compute multithread architecture to calculate the binary-state network reliability problem, which is fundamental for all types of network reliability problems. From the analysis of the time complexity and experiments conducted on 20 benchmarks of binary-state network reliability problems, PBAT was able to efficiently solve medium-scale network reliability problems.

Authors: Wei-Chang Yeh

Various networks are broadly and deeply applied in real-life applications. Reliability is the most important index for measuring the performance of all network types. Among the various algorithms, only implicit enumeration algorithms, such as depth-first-search, breadth-search-first, universal generating function methodology, binary-decision diagram, and binary-addition-tree algorithm (BAT), can be used to calculate the exact network reliability. However, implicit enumeration algorithms can only be used to solve small-scale network reliability problems. The BAT was recently proposed as a simple, fast, easy-to-code, and flexible make-to-fit exact-solution algorithm. Based on the experimental results, the BAT and its variants outperformed other implicit enumeration algorithms. Hence, to overcome the above-mentioned obstacle as a result of the size problem, a new parallel BAT (PBAT) was proposed to improve the BAT based on compute multithread architecture to calculate the binary-state network reliability problem, which is fundamental for all types of network reliability problems. From the analysis of the time complexity and experiments conducted on 20 benchmarks of binary-state network reliability problems, PBAT was able to efficiently solve medium-scale network reliability problems.

Modeling the Small-World Phenomenon with Road Networks

from arXiv: Data Structures and Algorithms

Authors: Michael T. Goodrich, Evrim Ozel

Dating back to two famous experiments by the social-psychologist, Stanley Milgram, in the 1960s, the small-world phenomenon is the idea that all people are connected through a short chain of acquaintances that can be used to route messages. Many subsequent papers have attempted to model this phenomenon, with most concentrating on the "short chain" of acquaintances rather than their ability to efficiently route messages. In this paper, we study the small-world navigability of the U.S. road network, with the goal of providing a model that explains how messages in the original small-world experiments could be routed along short paths using U.S. roads. To this end, we introduce the Neighborhood Preferential Attachment model, which combines elements from Kleinberg's model and the Barab\'asi-Albert model, such that long-range links are chosen according to both the degrees and (road-network) distances of vertices in the network. We empirically evaluate all three models by running a decentralized routing algorithm, where each vertex only has knowledge of its own neighbors, and find that our model outperforms both of these models in terms of the average hop length. Moreover, our experiments indicate that similar to the Barab\'asi-Albert model, networks generated by our model are scale-free, which could be a more realistic representation of acquaintanceship links in the original small-world experiment.

Authors: Michael T. Goodrich, Evrim Ozel

Dating back to two famous experiments by the social-psychologist, Stanley Milgram, in the 1960s, the small-world phenomenon is the idea that all people are connected through a short chain of acquaintances that can be used to route messages. Many subsequent papers have attempted to model this phenomenon, with most concentrating on the "short chain" of acquaintances rather than their ability to efficiently route messages. In this paper, we study the small-world navigability of the U.S. road network, with the goal of providing a model that explains how messages in the original small-world experiments could be routed along short paths using U.S. roads. To this end, we introduce the Neighborhood Preferential Attachment model, which combines elements from Kleinberg's model and the Barab\'asi-Albert model, such that long-range links are chosen according to both the degrees and (road-network) distances of vertices in the network. We empirically evaluate all three models by running a decentralized routing algorithm, where each vertex only has knowledge of its own neighbors, and find that our model outperforms both of these models in terms of the average hop length. Moreover, our experiments indicate that similar to the Barab\'asi-Albert model, networks generated by our model are scale-free, which could be a more realistic representation of acquaintanceship links in the original small-world experiment.

On the Correlation Gap of Matroids

from arXiv: Data Structures and Algorithms

Authors: Edin Husić, Zhuan Khye Koh, Georg Loho, László A. Végh

A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is $1-1/e$, and this is tight even for simple matroid rank functions.

We initiate a fine-grained study of correlation gaps of matroid rank functions. In particular, we present improved lower bounds on the correlation gap as parametrized by the rank and the girth of the matroid. We also show that the worst correlation gap of a weighted matroid rank function is achieved under uniform weights. Such improved lower bounds have direct applications for submodular maximization under matroid constraints, mechanism design, and contention resolution schemes. Previous work relied on implicit correlation gap bounds for problems such as list decoding and approval voting.

Authors: Edin Husić, Zhuan Khye Koh, Georg Loho, László A. Végh

A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is $1-1/e$, and this is tight even for simple matroid rank functions.

We initiate a fine-grained study of correlation gaps of matroid rank functions. In particular, we present improved lower bounds on the correlation gap as parametrized by the rank and the girth of the matroid. We also show that the worst correlation gap of a weighted matroid rank function is achieved under uniform weights. Such improved lower bounds have direct applications for submodular maximization under matroid constraints, mechanism design, and contention resolution schemes. Previous work relied on implicit correlation gap bounds for problems such as list decoding and approval voting.

Tuesday, September 20

TR22-133 | Downward Self-Reducibility in TFNP | Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

from ECCC Papers
A problem is downward self-reducible if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is well studied and it is known that all downward self-reducible problems are in PSPACE. In this paper, we initiate the study of downward self-reducible search problems which are guaranteed to have a solution — that is, the downward self-reducible problems in TFNP. We show that most natural PLS-complete problems are downward self-reducible and any downward self-reducible problem in TFNP is contained in PLS. Furthermore, if the downward self-reducible problem is in UTFNP (i.e. it has a unique solution), then it is actually contained in CLS. This implies that if integer factoring is downward self-reducible then it is in fact in CLS, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.
A problem is downward self-reducible if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is well studied and it is known that all downward self-reducible problems are in PSPACE. In this paper, we initiate the study of downward self-reducible search problems which are guaranteed to have a solution — that is, the downward self-reducible problems in TFNP. We show that most natural PLS-complete problems are downward self-reducible and any downward self-reducible problem in TFNP is contained in PLS. Furthermore, if the downward self-reducible problem is in UTFNP (i.e. it has a unique solution), then it is actually contained in CLS. This implies that if integer factoring is downward self-reducible then it is in fact in CLS, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.

Better Hardness Results for the Minimum Spanning Tree Congestion Problem

from arXiv: Computational Complexity

Authors: Huong Luu, Marek Chrobak

In the spanning tree congestion problem, given a connected graph $G$, the objective is to compute a spanning tree $T$ in $G$ for which the maximum edge congestion is minimized, where the congestion of an edge $e$ of $T$ is the number of vertex pairs adjacent in $G$ for which the path connecting them in $T$ traverses $e$. The problem is known to be NP-hard, but its approximability is still poorly understood, and it is not even known whether the optimum can be efficiently approximated with ratio $o(n)$. In the decision version of this problem, denoted STC-$K$, we need to determine if $G$ has a spanning tree with congestion at most $K$. It is known that STC-$K$ is NP-complete for $K\ge 8$, and this implies a lower bound of $1.125$ on the approximation ratio of minimizing congestion. On the other hand, $3$-STC can be solved in polynomial time, with the complexity status of this problem for $K\in \{4,5,6,7\}$ remaining an open problem. We substantially improve the earlier hardness result by proving that STC-$K$ is NP-complete for $K\ge 5$. This leaves only the case $K=4$ open, and improves the lower bound on the approximation ratio to $1.2$.

Authors: Huong Luu, Marek Chrobak

In the spanning tree congestion problem, given a connected graph $G$, the objective is to compute a spanning tree $T$ in $G$ for which the maximum edge congestion is minimized, where the congestion of an edge $e$ of $T$ is the number of vertex pairs adjacent in $G$ for which the path connecting them in $T$ traverses $e$. The problem is known to be NP-hard, but its approximability is still poorly understood, and it is not even known whether the optimum can be efficiently approximated with ratio $o(n)$. In the decision version of this problem, denoted STC-$K$, we need to determine if $G$ has a spanning tree with congestion at most $K$. It is known that STC-$K$ is NP-complete for $K\ge 8$, and this implies a lower bound of $1.125$ on the approximation ratio of minimizing congestion. On the other hand, $3$-STC can be solved in polynomial time, with the complexity status of this problem for $K\in \{4,5,6,7\}$ remaining an open problem. We substantially improve the earlier hardness result by proving that STC-$K$ is NP-complete for $K\ge 5$. This leaves only the case $K=4$ open, and improves the lower bound on the approximation ratio to $1.2$.

On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors

from arXiv: Computational Complexity

Authors: Alex Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu

Locally Decodable Codes (LDCs) are error-correcting codes $C:\Sigma^n\rightarrow \Sigma^m$ with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson et al. showed how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Insdel LDCs were first studied by Ostrovsky and Paskin-Cherniavsky, and are further motivated by recent advances in DNA random access bio-technologies, in which the goal is to retrieve individual files from a DNA storage database. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries, over the binary alphabet. This answers a question explicitly raised by Gur and Lachish. Our result exhibits a "phase-transition"-type behavior on the codeword length for constant-query Hamming RLDCs. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with with parameters matching those of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs.

Authors: Alex Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu

Locally Decodable Codes (LDCs) are error-correcting codes $C:\Sigma^n\rightarrow \Sigma^m$ with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson et al. showed how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Insdel LDCs were first studied by Ostrovsky and Paskin-Cherniavsky, and are further motivated by recent advances in DNA random access bio-technologies, in which the goal is to retrieve individual files from a DNA storage database. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries, over the binary alphabet. This answers a question explicitly raised by Gur and Lachish. Our result exhibits a "phase-transition"-type behavior on the codeword length for constant-query Hamming RLDCs. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with with parameters matching those of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs.