Lower bounds for sense of direction in regular graphs

A graph G with n vertices and maximum degree cannot be given weak sense of direction using less than colours. It is known that n colours are always sufficient, and it was conjectured that just are really needed, that is, one more colour is sufficient. Nonetheless, it has been shown [3] that for sufficiently large n there are graphs requiring more colours than . In this paper, using recent results in asymptotic graph enumeration, we show that (surprisingly) the same bound holds for regular graphs. We also show that colours are necessary, where d _G is the degree of G.Received: April 2002, Accepted: April 2003, Sebastiano Vigna: Partially supported by the Italian MURST (Finanziamento di iniziative di ricerca diffusa condotte da parte di giovani ricercatori).The results of this paper appeared in a preliminary form in Distributed Computing. 14th International Conference, DISC 2000, Springer-Verlag, 2000.     

Condition-based consensus solvability: a hierarchy of conditions and efficient protocols

The condition-based approach for consensus solvability consists of identifying sets of input vectors, called conditions, for which there exists an asynchronous protocol solving consensus despite the occurrence of up to f process crashes. This paper investigates , the largest set of conditions which allow us to solve the consensus problem in an asynchronous shared memory system.The first part of the paper shows that is made up of a hierarchy of classes of conditions, where d is a parameter (called degree of the condition), starting with and ending with d = 0, where . We prove that each one is strictly contained in the previous one: . Various properties of the hierarchy are also derived. It is shown that a class can be characterized in two equivalent but complementary ways: one is convenient for designing protocols while the other is for analyzing the class properties. The paper also defines a linear family of conditions that can be used to derive many specific conditions. In particular, for each d, two natural conditions are presented.The second part of the paper is devoted to the design of efficient condition-based protocols. A generic condition-based protocol is presented. This protocol can be instantiated with any condition C, , and requires at most shared memory read/write operations per process in the synchronization part of the protocol. Thus, the value (f-d) represents the difficulty of the class . An improvement of the protocol for the conditions in is also presented.Received: 15 November 2001, Accepted: 15 April 2003, Published online: 6 February 2004Parts of it have previously appeared in [23] and [25].     

Some Relations between Approximation Problems and PCPs over the Real Numbers

In [10] it was recently shown that that is the existence of transparent long proofs for was established. The latter denotes the class of real number decision problems verifiable in polynomial time as introduced by Blum et al. [6]. The present paper is devoted to the question what impact a potential full real number theorem would have on approximation issues in the BSS model of computation. We study two natural optimization problems in the BSS model. The first, denoted by MAX-QPS, is related to polynomial systems; the other, MAX-q-CAP, deals with algebraic circuits. Our main results combine the PCP framework over with approximation issues for these two problems. We also give a negative approximation result for a variant of the MAX-QPS problem.     

Coupling and self-stabilization

A randomized self-stabilizing algorithm is an algorithm that, whatever the initial configuration is, reaches a set of М legal configurations} in finite time with probability 1. The proof of convergence towards is generally done by exhibiting a potential function , which measures the “vertical” distance of any configuration to , such that decreases with non-null probability at each step of . We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance between any pair of configurations, such that decreases in expectation at each step of . In contrast with classical methods, our coupling method does not require the knowledge of . In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as examplified here on Herman's mutual exclusion and Iterated Prisoner's Dilemma algorithms in the case of cyclic graphs.     

Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler

We consider asynchronous consensus in the shared-memory setting. We present the first efficient low-contention consensus algorithm for the weak-adversary-scheduler model. The algorithm achieves consensus in total work and (hot-spot) contention, both expected and with high probability. The algorithm assumes the value-oblivious scheduler, which is defined in the paper. Previous efficient consensus algorithms for weak adversaries suffer from memory contention.Yonatan Aumann: This work was partially completed while theauthor was at Harvard University, supported in part by ONRcontract ONR-N00014-91-J-1981.Michael A. Bender: This work was supported inpart by HRL Laboratories, Sandia National Laboratories, and NSF GrantsACI-032497, CCR-0208670, and EIA-0112849. This work was partiallycompleted while the author was at Harvard University, supported inpart by NSF grants CCR-9700365, CCR-9504436, and CCR-9313775.An early version of this paper was presented in the 23rd International Colloquium on Automata, Languages, and Programming (ICALP 96) [8].     

On the Power of Unambiguity in Alternating Machines

Unambiguity in alternating Turing machines has received considerable attention in the context of analyzing globally unique games by Aida et al. [ACRW] and in the design of efficient protocols involving globally unique games by Crasmaru et al. [CGRS]. This paper explores the power of unambiguity in alternating Turing machines in the following settings: 1. We show that unambiguity-based hierarchies-AUPH, UPH, and UPH-are infinite in some relativized world. For each , we construct another relativized world where the unambiguity-based hierarchies collapse so that they have exactly k distinct levels and their k-th levels coincide with PSPACE. These results shed light on the relativized power of the unambiguity-based hierarchies, and parallel the results known for the case of the polynomial hierarchy. 2. For every , we define the bounded-level unambiguous alternating solution class UAS(k) as the class of all sets L for which there exists a polynomial-time alternating Turing machine N, which need not be unambiguous on every input, with at most k alternations such that if and only if x is accepted unambiguously by N. We construct a relativized world where, for all and . 3. Finally, we show that robustly k-level unambiguous alternating polynomial-time Turing machines, i.e., polynomial-time alternating Turing machines that for every oracle have k alternating levels and are unambiguous, accept languages that are computable in , for every oracle A. This generalizes a result of Hartmanis and Hemachandra [HH].     

Fast allocation and deallocation with an improved buddy system

We propose several modifications to the binary buddy system for managing dynamic allocation of memory blocks whose sizes are powers of two. The standard buddy system allocates and deallocates blocks in time in the worst case (and on an amortized basis), where n is the size of the memory. We present three schemes that improve the running time to O(1) time, where the time bound for deallocation is amortized for the first two schemes. The first scheme uses just one more word of memory than the standard buddy system, but may result in greater fragmentation than necessary. The second and third schemes have essentially the same fragmentation as the standard buddy system, and use bits of auxiliary storage, which is but for all and . Finally, we present simulation results estimating the effect of the excess fragmentation in the first scheme.Received: 4 May 2003, Published online: 22 December 2004Gerth Stølting Brodal: Supported by the Carlsberg Foundation (contract number ANS-0257/20). Partially supported by the Future and Emerging Technologies Programme of the EU under contract number IST-1999-14186 (ALCOM-FT). Basic Research in Computer Science, www.brics.dk, funded by the Danish National Research Foundation.Erik D. Demaine: Partially supported by the Natural Science and Engineering Research Council of Canada (NSERC).J. Ian Munro: Supported by the Natural Science and Engineering Research Council of Canada (NSERC) and the Canada Research Chair in Algorithm Design.This paper includes several results that appeared in preliminary form in the Proceedings of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FST & TCS99) [8].     

Random Geometric Graph Diameter in the Unit Ball

The unit ball random geometric graph has as its vertices n points distributed independently and uniformly in the unit ball in , with two vertices adjacent if and only if their ℓ_p-distance is at most λ. Like its cousin the Erdos-Renyi random graph, G has a connectivity threshold: an asymptotic value for λ in terms of n, above which G is connected and below which G is disconnected. In the connected zone we determine upper and lower bounds for the graph diameter of G. Specifically, almost always, , where is the ℓ_p-diameter of the unit ball B. We employ a combination of methods from probabilistic combinatorics and stochastic geometry.     

Coincidental extension of scattered context languages

All the results given in the paper hold true. In the proof of Theorem 1, change steps IV, V, and VI to IV. for every , add to P; V. for every , add , , , , , to P; VI. for every , add to P.     

Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines

This paper investigates two preemptive semi-online scheduling problems to minimize makespan on two uniform machines. In the first semi-online problem, we know in advance that all jobs have their processing times in between p and rp . In the second semi-online problem, we know the size of the largest job in advance. We design an optimal semi-online algorithm which is optimal for every combination of machine speed ratio and job processing time ratio for the first problem, and an optimal semi-online algorithm for every machine speed ratio for the second problem.Received: 2 December 2003, Published online: 16 January 2004This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and National Natural Science Foundation of China (10271110).     

Element distinctness on one-tape Turing machines: a complete solution

We give a complete characterization of the complexity of the element distinctness problem for n elements of bits each on deterministic and nondeterministic one-tape Turing machines. We present an algorithm running in time for deterministic machines and nondeterministic solutions that are of time complexity . For elements of logarithmic size , on nondeterministic machines, these results close the gap between the known lower bound and the previous upper bound . Additional lower bounds are given to show that the upper bounds are optimal for all other possible relations between m and n. The upper bounds employ hashing techniques, while the lower bounds make use of the communication complexity of set disjointness.Received: 23 April 2001, Published online: 2 September 2003Holger Petersen: Supported by Deutsche Akademie der Naturforscher Leopoldina, grant number BMBF-LPD 9901/8-1 of Bundesministerium für Bildung und Forschung.     

The Complexity of Finding Top-Toda-Equivalence-Class Members

We identify two properties that for P-selective sets are effectively computable. Namely, we show that, for any P-selective set, finding a string that is in a given length's top Toda equivalence class (very informally put, a string from that the set's P-selector function declares to be most likely to belong to the set) is computable, and we show that each P-selective set contains a weakly- -rankable subset.     

Real Hypercomputation and Continuity

By the sometimes so-called Main Theorem of Recursive Analysis, every computable real function is necessarily continuous. We wonder whether and which kinds of hypercomputation allow for the effective evaluation of also discontinuous . More precisely the present work considers the following three super-Turing notions of real function computability: - relativized computation; specifically given oracle access to the Halting Problem or its jump ; - encoding input and/or output y = f(x) in weaker ways also related to the Arithmetic Hierarchy; - nondeterministic computation. It turns out that any computable in the first or second sense is still necessarily continuous whereas the third type of hypercomputation provides the required power to evaluate for instance the discontinuous Heaviside function.     

Broadcasting in undirected ad hoc radio networks

We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in expected time in n-node radio networks of diameter D, which is optimal, as it matches the lower bounds of Alon et al. [1] and Kushilevitz and Mansour [16]. Our algorithm improves the best previously known randomized broadcasting algorithm of Bar-Yehuda, Goldreich and Itai [3], running in expected time . (In fact, our result holds also in the setting of n-node directed radio networks of radius D.) For deterministic broadcasting, we show the lower bound on broadcasting time in n-node radio networks of diameter D. This implies previously known lower bounds of Bar-Yehuda, Goldreich and Itai [3] and Bruschi and Del Pinto [5], and is sharper than any of them in many cases. We also give an algorithm working in time , thus shrinking - for the first time - the gap between the upper and the lower bound on deterministic broadcasting time to a logarithmic factor. Received: 1 August 2003, Accepted: 18 March 2005, Published online: 15 June 2005 Dariusz R. Kowalski: This work was done during the stay of Dariusz Kowalski at the Research Chair in Distributed Computing of the Université du Québec en Outaouais, as a postdoctoral fellow. Research supported in part by KBN grant 4T11C04425. Andrzej Pelc: Research of Andrzej Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais.     

Quantum Orlicz Spaces in Information Geometry

Let H₀ be a selfadjoint operator such that Tr is of trace class for some , and let denote the set of ε-bounded forms, i.e., for some 0 $$" align="middle" border="0"> . Let χ := Span . Let denote the underlying set of the quantum information manifold of states of the form . We show that if Tr ,

An algebraic approach for $${\mathcal{H}}$$-matrix preconditioners

Hierarchical matrices ( -matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for -matrices is almost optimal. In this paper we present an algebraic approach for constructing -matrices which combines multilevel clustering methods with -matrix arithmetic to compute the -inverse, -LU, and the -Cholesky factors of a matrix. Then the -inverse, -LU or -Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or AMG, for solving some large, sparse linear systems, and is comparable to other -matrix constructions based on Nested Dissection.     

Efficient Algorithms for k Maximum Sums

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem involves finding the k largest values of for The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a -time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in time in the worst case. Our algorithm is optimal for and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.     

Computational challenges in bounded model checking

We describe several observations regarding the completeness and the complexity of bounded model checking and propose techniques to solve some of the associated computational challenges. We begin by defining the completeness threshold ( ) problem: for every finite model M and an LTL property , there exists a number such that if there is no counterexample to in M of length or less, then M . Finding this number, if it is sufficiently small, offers a practical method for making bounded model checking complete. We describe how to compute an overapproximation to for a general LTL property using Büchi automata, following the Vardi–Wolper LTL model checking framework. This computation is based on finding the initialized diameter and initialized recurrence-diameter (the longest loop-free path from an initial state) of the product automaton. We show a method for finding a recurrence diameter with a formula of size O(klogk) (or O(k(logk)²) in practice), where k is the attempted depth, which is an improvement compared to the previously known method that requires a formula of size in O(k²). Based on the value of , we prove that the complexity of standard SAT-based BMC is doubly exponential and that, consequently, there is a complexity gap of an exponent between this procedure and standard LTL model checking. We discuss ways to bridge this gap.