Search

Solving and designing puzzles, creating sculpture and architecture, and inventing magic tricks all lead to fun and interesting algorithmic problems. This paper describes some of our explorations into these areas. [ABSTRACT FROM AUTHOR]

This paper introduces the notion of distributed verification without preprocessing. It focuses on the Minimum-weight Spanning Tree (MST) verification problem and establishes tight upper and lower bounds for the time and message complexities of this problem. Specifically, we provide an MST verification algorithm that achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time, where m is the number of edges in the given graph G, n is the number of nodes, and D is G's diameter. On the other hand, we show that any MST verification algorithm must send $\tilde{\varOmega}(m)$ messages and incur $\tilde{\varOmega}(\sqrt{n} + D)$ time in worst case. Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of $\tilde{\varOmega}(m)$ messages and $\tilde{\varOmega}(\sqrt{n} + D)$ time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time. Specifically, the best known time-optimal algorithm (using ${\tilde{O}}(\sqrt {n} + D)$ time) requires O( m+ n) messages, and the best known message-optimal algorithm (using ${\tilde{O}}(m)$ messages) requires O( n) time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction. [ABSTRACT FROM AUTHOR]

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar “taste” may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player’s real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead. [ABSTRACT FROM AUTHOR]

A bipartite graph G=( U, W, E) with vertex set V= U∪ W is convex if there exists an ordering of the vertices of W such that for each u∈ U, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(| V|+| E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs has remained unknown. In this paper, we present an O(| V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct, we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound. [ABSTRACT FROM AUTHOR]

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0< ε<1, by examining function values of f over o(| D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε| D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f, which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f. In this paper, we prove the existence of a set of quartet topologies of error number at least $c{n\choose 4}$ for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O( n/ ε) queries, and is of one-sided error and non-adaptive. [ABSTRACT FROM AUTHOR]

Fischer and Rabin proved in (Proceedings of the SIAM-AMS Symposium in Applied Mathematics, vol. 7, pp. 27–41, ) that the decision problem for Presburger Arithmetic has at least double exponential worst-case complexity (for deterministic and for nondeterministic Turing machines). In Kapovich et al. (J. Algebra 264(2):665–694, ) a theory of generic-case complexity was developed, where algorithmic problems are studied on “most” inputs instead of set of all inputs. A question rises about existing of more efficient (say, polynomial) generic algorithm deciding Presburger Arithmetic on a set of closed formulas of asymptotic density 1. We prove in this paper that there is not an exponential generic decision algorithm working correctly on an input set of asymptotic density exponentially converging to 1 (so-called strongly generic sets). [ABSTRACT FROM AUTHOR]

In this paper we find upper bounds for the mincut value of Cayley graphs over abelian groups. These results provide a significant improvement of those in Annextein and Baumslag (Math. Syst. Theory 26(3):271–291, []). [ABSTRACT FROM AUTHOR]

In this paper we classify several algorithmic problems in group theory in the complexity classes PZK and SZK (problems with perfect/statistical zero-knowledge proofs respectively). Prior to this, these problems were known to be in $\mbox {\rm AM}\cap \mbox {\rm coAM}$ . As $\mbox {\rm PZK}\subseteq \mbox {\rm SZK}\subseteq \mbox {\rm AM}\cap \mbox {\rm coAM}$ , we have a tighter upper bound for these problems. Specifically: [ABSTRACT FROM AUTHOR]

This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤ α≤ ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem. [ABSTRACT FROM AUTHOR]

We introduce new data structures for compressed suffix trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log|A|) bits for a text of length n on an alphabet A. This is a remarkable improvement on current suffix trees which require O(n log n) bits. Though some components of suffix trees have been compressed, there is no linear-size data structure for suffix trees with full functionality such as computing suffix links, string-depths and lowest common ancestors. The data structure proposed in this paper is the first one that has linear size and supports all operations efficiently. Any algorithm running on a suffix tree can also be executed on our compressed suffix trees with a slight slowdown of a factor of polylog(n). [ABSTRACT FROM AUTHOR]

Any Boolean function can be defined by a Boolean circuit, provided we may use sufficiently strong functions in its gates. On the other hand, what Boolean functions can be defined depends on these gate functions: Each set B of gate functions defines the class of Boolean functions that can be defined by circuits over B. Although these classes have been known since the 1920s, their computational complexity was never investigated. In this paper we will study how difficult it is to decide for a Boolean function f and a class B, whether f is in B. Moreover, we will provide such a decision algorithm with additional information: How difficult is it to decide whether or not f is in B, provided we already know a circuit for f, but with gates from another class A? Given such a circuit, we know that f is in A. Is the problem harder if we do not have a concrete representation for f, but still know that it is from A? For nearly all possible combinations, we show that this is not the case, and that the problem is either in P or coNP-complete. [ABSTRACT FROM AUTHOR]

We extend earlier works on the relation of prefix arrays of indeterminate strings to undirected graphs and border arrays. If integer array y is the prefix array for indeterminate string w, then we say w satisfies y. We use a graph theoretic approach to construct a string on a minimum alphabet size which satisfies a given prefix array. We relate the problem of finding a minimum alphabet size to finding edge clique covers of a particular graph, allowing us to bound the minimum alphabet size by $n+\sqrt {n}$ for indeterminate strings, where n is the size of the prefix array. When we restrict ourselves to prefix arrays for partial words, we bound the minimum alphabet size by $\left \lceil \sqrt {2n} \right \rceil $ . Moreover, we show that this bound is tight up to a constant multiple by using Sidon sets. We also study the relationship between prefix arrays and border arrays. We give necessary and sufficient conditions for a border array and prefix array to be satisfied by the same indeterminate string. We show that the slowly-increasing property completely characterizes border arrays for indeterminate strings, whence there are exactly C distinct border arrays of size n for indeterminate strings (here C is the nth Catalan number). We give an algorithm to enumerate all prefix arrays for partial words of a given size, n. Our algorithm has a time complexity of n times the output size, that is, the number of valid prefix arrays for partial words of length n. We also bound the number of prefix arrays for partial words of a given size using Stirling numbers of the second kind. [ABSTRACT FROM AUTHOR]

A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vertices added to G, one at a time, be coloured so that at each stage the current graph is ecologically coloured? If the answer is yes, then we say that the pair ( G, c) is ecologically online extendible. By generalizing the well-known First-Fit algorithm, we are able to characterize when ( G, c) is ecologically online extendible, and to show that deciding whether ( G, c) is ecologically extendible can be done in polynomial time. We also describe when the extension is possible using only colours from a given finite set C. For the case where c is a colouring of G in which each vertex is coloured distinctly, we give a simple characterization of when ( G, c) is ecologically online extendible using only the colours of c, and we also show that ( G, c) is always online extendible using the colours of c plus one extra colour. We also study (off-line) ecological H-colourings (an H-colouring of G is a homomorphism from G to H). We study the problem of deciding whether G has an ecological H-colouring for some fixed H and give a characterization of its computational complexity in terms of the structure of H. [ABSTRACT FROM AUTHOR]

Since Grover’s seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items x1,..., x n and we would like to find i: x i=1. We consider a new variant of this problem in which evaluating x i for different i may take a different number of time steps. Let t i be the number of time steps required to evaluate x i. If the numbers t i are known in advance, we give an algorithm that solves the problem in $O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})$ steps. This is optimal, as we also show a matching lower bound. The case, when t i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions. [ABSTRACT FROM AUTHOR]

We present a deterministic Logspace procedure, which, given a bipartite planar graph on n vertices, assigns O(log n) bits long weights to its edges so that the minimum weight perfect matching in the graph becomes unique. The Isolation Lemma as described in Mulmuley et al. (Combinatorica 7(1):105–131, ) achieves the same for general graphs using randomness, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the perfect matching problem in bipartite planar graphs to testing whether a matrix is singular, under the promise that its determinant is 0 or 1, thus obtaining a highly parallel $\mathsf{SPL}$ algorithm for both decision and construction versions of the bipartite perfect matching problem. This improves the earlier known bounds of non-uniform $\mathsf{SPL}$ by Allender et al. (J. Comput. Syst. Sci. 59(2):164–181, ) and $\mathsf{NC}$2 by Miller and Naor (SIAM J. Comput. 24:1002–1017, ), and by Mahajan and Varadarajan (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp. 351–357, ). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite planar graphs, which has been open for a long time. Further we try to find the lower bound on the number of bits needed for deterministically isolating a perfect matching. We show that our particular method for isolation will require Ω(log n) bits. Our techniques are elementary. [ABSTRACT FROM AUTHOR]

We investigate the complexity of equivalence problems for {∪,∩,−,+,×}-circuits computing sets of natural numbers. These problems were first introduced by Stockmeyer and Meyer (1973). We continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C= L, P,Π, PSPACE, NEXP, and beyond. McKenzie and Wagner (2003) studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an improved upper bound for the case of {∪,∩,−,+,×}-circuits. [ABSTRACT FROM AUTHOR]

We give a general model of partially asynchronous, distributed load-balancing algorithms for the discrete load model in parallel computers, where the processor loads are treated as non-negative integers. We prove that all load-balancing algorithms in this model are finite. This means that all load-balancing algorithms based on this model are guaranteed to reach a stable situation at a certain time (which depends on the particular algorithm) at which no load will be sent from one processor to another. With an additional assumption, we prove that the largest load difference between any two processors, in the final stable situation of the load-balancing algorithms in this model, is upper-bounded by the diameter of the topology. [ABSTRACT FROM AUTHOR]

We present approximation algorithms for two closely related bicriteria problems. Given a graph with two weight functions on the edges, length and cost, we consider the Bounded-Diameter Minimum-Cost Steiner Tree (BDMST) problem and the Bounded-Diameter Minimum-Cardinality Edge Addition (BDMC) problem. We present a parameterized approximation algorithm for the BDMST problem with a bicriteria approximation ratio of (O(p log s/log p),O(log s/log p)) where the first factor gives the relaxation on the diameter bound, the second factor is the cost-approximation factor, s is the number of required nodes and p, 1 ≤ p < s, is an input parameter. The parameter p allows a trade-off between the two approximation factors. This is the first improvement of the cost-approximation factor since the scheme proposed by Marathe et al. [9]. For example, p can be set to sα to obtain an (O(sα),O(1)) approximation for a constant α. The algorithm is very simple and is suitable for distributed implementations. We also present the first algorithm for Bounded-Hops Minimum-Cost Steiner Tree for complete graphs with triangle inequality. This model includes graphs defined by points in a Euclidean space of any dimension. The algorithm guarantees an approximation ratio of (O(logds),O(logds)) where d is the bound on the diameter. This is an improvement over the general-case approximation when d is comparable with s. For example, the ratio is (O(1),O(1)) for any d = sα where α is a constant between 0 and 1. For the case where the number of terminals is a constant and all edge lengths are unit, we have a polynomial-time algorithm. This can be extended to any length function providing a (1 + ε) in the approximation with ε showing up in the time complexity of the algorithm. For another special case, where the cost of any edge is either 1 or 0 and the length of each edge is positive, an algorithm with approximation ratio of (O(log(c log s)), O(log(c log s))) is presented, where c is the cost of the optimal solution. This approximation is a significant improvement over (O(log s),O(log s)) when the cost of the solution c is much smaller than the number of terminals s. This is useful when an existing multicast network is to be modified to accommodate new terminals with the addition of as few new edges as possible. We also propose an approximation algorithm for the Bounded-Diameter Minimum-Cardinality Edge Addition problem, which achieves an O(log n) approximation while relaxing the diameter bound by 2. While this ratio is the same as the one claimed in [3], this algorithm is simple and combinatorial rather than based on the Linear Program solution and can be readily modified for a distributed implementation. [ABSTRACT FROM AUTHOR]

We study the distribution of values of additive functions related to numeration systems defined via regular languages. [ABSTRACT FROM AUTHOR]