Abstract Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size $$k^d$$ k d (which is a polynomial as d is a constant), and they do so in time $$m\cdot 2^d {\text {poly}}(d)$$ m · 2 d poly ( d ) for a small polynomial $${\text {poly}}(d)$$ poly ( d ) (which is linear in the hypergraph size for d fixed). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size- $$k^d$$ k d kernel. This paper presents a deterministic solution with worst-case time $$3^d {\text {poly}}(d)$$ 3 d poly ( d ) for updating the kernel upon inserts and time $$5^d {\text {poly}}(d)$$ 5 d poly ( d ) for updates upon deletions. These bounds nearly match the time $$2^d {\text {poly}}(d)$$ 2 d poly ( d ) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times $$O(c^k)$$ O ( c k ) where $$c = d - 1 + O(1/d)$$ c = d - 1 + O ( 1 / d ) equals the best base known for the static setting.

Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size k^d (which is a polynomial kernel size as d is a constant), and they do so in time m⋅ 2^d poly(d) for a small polynomial poly(d) (which is a linear runtime as d is again a constant). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size-k^d hitting set kernel in memory (including moments when no size-k hitting set exists). This paper presents a deterministic solution with worst-case time 3^d poly(d) for updating the kernel upon hyperedge inserts and time 5^d poly(d) for updates upon deletions. These bounds nearly match the time 2^d poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a dynamic hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times O(c^k) where c = d - 1 + O(1/d) equals the best base known for the static setting.

Residuality plays an essential role for learning finite automata. While residual deterministic and non-deterministic automata have been understood quite well, fundamental questions concerning alternating automata (AFA) remain open. Recently, Angluin, Eisenstat, and Fisman (2015) have initiated a systematic study of residual AFAs and proposed an algorithm called AL* – an extension of the popular L* algorithm – to learn AFAs. Based on computer experiments they have conjectured that AL* produces residual AFAs, but have not been able to give a proof. In this paper we disprove this conjecture by constructing a counterexample. As our main positive result we design an efficient learning algorithm, named AL** and give a proof that it outputs residual AFAs only. In addition, we investigate the succinctness of these different FA types in more detail.

Given a string, the task of grammar-based compression is to find a small context-free grammar that generates exactly that string. We investigate the relationship between grammar-based compression of strings over unbounded and bounded alphabets. Specifically, we show how to transform a grammar for a string over an unbounded alphabet into a grammar for a block coding of that string over a fixed bounded alphabet and vice versa. From these constructions, we obtain asymptotically tight relationships between the minimum grammar sizes for strings and their block codings. Furthermore, we exploit an improved bound of our construction for overlap-free block codings to show that a polynomial time algorithm for approximating the minimum grammar for binary strings within a factor of c yields a polynomial time algorithm for approximating the minimum grammar for strings over arbitrary alphabets within a factor of 24c + /spl isin/ (for arbitrary /spl isin/ > 0). Currently, the latter problem is known to be NP-hard to approximate within a factor of 8569/8568. Since there is some hope to prove a nonconstant lower bound, our results may provide a first step towards solving the long standing open question whether minimum grammar-based compression of binary strings is NP-complete.

Several authors have shown that the PARITY-function cannot be computed by unbounded fanin circuits of small depth and polynomial size. Even more, constant depth k circuits of size exp(n/sup /spl ominus/(1/k)/) give wrong results for PARITY for almost half of all inputs. We generalize these results in two directions. First, we obtain similar tight lower bounds for the average case complexity of circuits, measuring the computational delay instead of the static circuit depth. Secondly, with respect to average delay of unbounded fanin circuits we completely classify all parallel prefix functions, for which PARITY is just one prominent example. It is shown that only two cases can occur: a parallel prefix functions f either has the same average complexity as PARITY, that is the average delay has to be of order O(log n/ loglog s) for circuits of size s, or f can be computed with constant average delay and almost linear size there is no complexity level in between. This classification is achieved by analyzing the algebraic structure of semigroups that correspond to parallel prefix functions. It extends methods developed for bounded fanin circuits by the first author in his Ph.D. Thesis.

A new algorithm for learning one-variable pattern languages is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all operations till an algorithm has converged to a correct hypothesis. For the expectation it is shown that for almost all meaningful distributions defining how the pattern variable is replaced by a string to generate random examples of the target pattern language this algorithm converges within a constant number of rounds with a total learning time that is linear in the pattern length. Thus, the algorithm is average-case optimal in a strong sense. Though one-variable pattern languages cannot be inferred finitely, our approach can also be considered as probabilistic finite learning with high confidence.

It was shown some years ago that the computation time for many important Boolean functions of n arguments on concurrent-read exclusive-write parallel random-access machines (CREW PRAMs) of unlimited size is at least $\varphi (n) \approx 0.72\log _2 n$. On the other hand, it is known that every Boolean function of n arguments can be computed in $\varphi (n) + 1$ steps on a CREW PRAM with $n \cdot 2^{n - 1} $ processors and memory cells. In the case of the OR of n bits, n processors and cells are sufficient. In this paper, it is shown that for many important functions, there are CREW PRAM algorithms that almost meet the lower bound in that they take $\varphi (n) + o(\log n)$ steps but use only a small number of processors and memory cells (in most cases, n). In addition, the cells only have to store binary words of bounded length (in most cases, length 1). We call such algorithms “feasible.” The functions concerned include the following: the PARITY function and, more generally, all symmetric functions; a large class of Boolean formulas; some functions over non-Boolean domains $\{ 0, \ldots ,k - 1\} $ for small k, in particular, parallel-prefix sums; addition of n-bit numbers; and sorting ${n / l}$ binary numbers of length l. Further, it is shown that Boolean circuits with fan-in 2, depth d, and size s can be evaluated by CREW PRAMs with fewer than s processors in ,$\varphi (2^d ) + o(d) \approx 0.72d + o(d)$ steps. For the exclusive-read exclusive-write (EREW) PRAM model, a feasible algorithm is described that computes PARITY of n bits in $0.86\log _2 n$ steps.

This paper tries to fully characterize the properties and relationships of space classes defined by Turing machines (TMs) that use less than logarithmic space—be they deterministic, nondeterministic, or alternating (DTMs, NTMs, or ATMs). We provide several examples of specific languages and show that such machines are unable to accept these languages. The basic proof method is a nontrivial extension of the $1^n \mapsto 1^{n + n!} $ technique to alternating TMs. Let 1log denote the logarithmic function log iterated twice, and let $\Sigma _k {\textit{Space}}(S) $ and $\prod _k {\textit{Space}}(S)$ be the complexity classes defined by S-space-bounded ATMs that alternate at most $k - 1$ times and start in an existential (resp., universal) state. Our first result shows that for each $k > 1$, the sets \[ \begin{gathered} \hfill \Sigma _k {\textit{Space}}(1\log )\backslash \Pi _k Space(o(\log )) \quad {\text{and}} \\ \hfill \Pi _k {\textit{Space}}(1\log )\backslash \Sigma _k {\textit{Space}}(o(\log )) \\ \end{gathered} \] are both not empty. This implies that for each $S \in \Omega (1\log ) \cap o(\log )$, the classes \[ \begin{gathered} \Sigma _1 {\textit{Space}}(S) \subset \Sigma _2 {\textit{Space}}(S) \subset \Sigma _3 {\textit{Space}}(S) \subset \cdots \\ \subset \sum\nolimits_k {Space(S) \subset } \sum\nolimits_{k + 1} {Space(S) \subset } \cdots \\ \end{gathered} \] form an infinite hierarchy. Furthermore, this separation is extended to space classes defined by ATMs with a nonconstant alternation bound A provided that the product $A \cdot S$ grows sublogarithmically. These lower bounds can also be used to show that basic closure properties do not hold for such classes. We obtain that for any $S \in \Omega (1\log ) \cap o(\log )$ and all $k > 1$, $\Sigma _k {Space(S)} $ and $\prod _k {\textit{Space}}(S)$ are not closed under complementation and concatenation. Moreover, $\Sigma _k {{\textit{Space}}(S)} $ is not closed under intersection and $\prod _k {\textit{Space}}(S)$ is not closed under union. It is also shown that ATMs recognizing bounded languages can always be guaranteed to halt. For the class of Z-bounded languages with $Z \leqslant \exp S$, we obtain the equality co-$\Sigma _k {{\textit{Space}}(S)} = \Pi _k {\textit{Space}}(S)$. Finally, for sublogarithmic bounded ATMs, we give a separation between the weak and strong space measure and prove a logarithmic lower space bound for the recognition of nonregular context-free languages.

While the synchronization of time-o!-day clocks ordinarily requires information f70w in both directions between the clocks, this information need not j70w directlp via messages.However, to take advantage of indirect information fiow, we have to make a number of

This paper compares the communication complexity of discrete functions under different modes of computation, unifying and extending several known models. Protocols can be deterministic, nondeterministic, or probabilistic. Furthermore, in the last case the error probability may vary. On the other hand, communication can be one-way, two-way, or as an intermediate stage can consist of a fixed number $k > 1$ of rounds. The following main results are obtained. A square gap between deterministic and nondeterministic communication complexity is shown for a specific function, which is the maximum possible. This improves the results of K. Mehlhorn and E. M. Schmidt in [Proc. 14th Annual ACM Symposium on Theory of Computing, 1982, pp. 330–337] and of A. V. Aho, J. D. Ullman, and M. Yannakakis in [Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 133–139]. For probabilistic one-way and two-way protocols linear lower bounds are proved for functions that satisfy certain independence conditions, extending the results of A. C. Yao in [Proc. 11th Annual ACM Symposium on Theory of Computing, 1979, pp. 209–213], and in [Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, 1983, pp. 420–428]. Further, with more technical effort an exponential gap between deterministic k-round and probabilistic $(k - 1)$-round communication with fixed error probability is obtained. This generalizes the main result of P. Duris, Z. Galil, and G. Schnitger [Inform. and Comput., 73 (1987), pp. 1–22]. In contrast, for arbitrary error probabilities less than ${1 / 2}$ there is no difference between the complexity of one-way and two-way protocols, which extends the results of R. Paturi and J. Simon [J. Comput. System Sci., 33 (1986), pp. 106–123]. Finally, communication with fixed message length and uniform probability distributions is considered, and simulations of arbitrary protocols by such uniform distributions with little overhead are provided.

Boolean circuits in which gates independently make errors with probability (at most) epsilon are considered. It is shown that the critical number crit(f) of a function f yields lower bound Omega (crit(f) log crit (f)) for the noisy circuit size. The lower bound is proved for an even stronger computational model, static Boolean decision trees with erroneous answers. A decision tree is static if the questions it asks do not depend on previous answers. The depth of such a tree provides a lower bound on the number of gates that depend directly on some input and hence on the size of a noisy circuit. Furthermore, it is shown that an Omega (n log n) lower bound holds for almost all Boolean n-input functions with respect to the depth of noisy dynamic decision trees. This bound is the best possible and implies that almost all n-input Boolean functions have noisy decision tree complexity Theta (n log n) in the static as well as in the dynamic case.>

Article Free Access Share on Exact time bounds for computing boolean functions on PRAMs without simultaneous writes Authors: M. Dietzfelbinger Universität-GH-Paderborn, F.R.G. Universität-GH-Paderborn, F.R.G.View Profile , M. Kutylowski University of Wroclaw, Poland University of Wroclaw, PolandView Profile , R. Reischuk Technische Hochschule Darmstadt, F.R.G. Technische Hochschule Darmstadt, F.R.G.View Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 125–135https://doi.org/10.1145/97444.97678Published:01 May 1990Publication History 14citation271DownloadsMetricsTotal Citations14Total Downloads271Last 12 Months10Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper is concerned with the solvability of the problem of processor renaming in unreliable, completely asynchronous distributed systems. Fischer et al. prove in [8] that “nontrivial consensus” cannot be attained in such systems, even when only a single, benign processor failure is possible. In contrast, this paper shows that problems of processor renaming can be solved even in the presence of up tot

Two different kinds of Byzantine Agreement for distributed systems with processor faults are defined and compared. The first is required when coordinated actions may be performed by each participant at different times. This kind is called Simultaneous Byzantine Agreement (SBA). This paper deals with the number of rounds of message exchange required to reach Byzantine Agreement of either kind (BA). If an algorithm allows its participants to reach Byzantine agreement in every execution in which at most t participants are faulty, then the algorithm is said to tolerate t faults. It is well known that any BA algorithm that tolerates t faults (with t < n - 1 where n denotes the total number of processors) must run at least t + 1 rounds in some execution. However, it might be supposed that in executions where the number f of actual faults is small compared to t , the number of rounds could be correspondingly small. A corollary of our first result states that (when t < n - 1) any algorithm for SBA must run t + 1 rounds in some execution where there are no faults. For EBA (with t < n - 1), a lower bound of min( t + 1, f + 2) rounds is proved. Finally, an algorithm for EBA is presented that achieves the lower bound, provided that t is on the order of the square root of the total number of processors.

We compare the communication complexity of discrete functions under different modes of computation, unifying and extending several known models. Protocols can be deterministic, nondeterministic or probabilistic and in the last case the error probability may vary. On the other hand communication can be 1-way, 2-way or as an intermediate stage consist of a fixed number k > 1 of rounds.The following main results are obtained. A square gap between deterministic and nondeterministic communication complexity is shown for a specific function, which is the maximal possible. This improves the results of [MS 82] and [AUY 83]. For probabilistic 1- and 2-way protocols we prove linear lower bounds for functions that satisfy certain independence conditions, extending the results of [Y 79] and [Y 83]. Further, with more technical effort an exponential gap between deterministic k-round and probabilistic (k - 1)-round communication with fixed error probability is obtained. This generalizes the main result of [DGS 84]. On contrast for arbitrary error probabilities less than 1/2 there is no difference between the complexity of 1- and 2-way protocols, extending results of [PS 84]. Finally we consider communication with fixed message length and uniform probability distributions and give simulations of arbitrary protocols by such uniform ones with little overhead.

The paper deals with achievability of fault tolerant goals in a completely asynchronous distributed system. Fischer, Lynch, and Paterson [FLP] proved that in such a system "nontrivial agreement" cannot be achieved even in the (possible) presence of a single "benign" fault. In contrast, we exhibit two pairs of goals that are achievable even in the presence of up to t ≪ n/2 faulty processors, contradicting the widely held assumption that no nontrivial goals are attainable in such a system. The first pair deals with renaming processors so as to reduce the size of the initial name space. When only uniqueness is required of the new names, we present a lower bound of n + 1 on the size of the new name space, and a renaming algorithm which establishes an upper bound of n + t. In case the new names are required also to preserve the original order, a tight bound of 2t(n- t + 1) - 1 is obtained. The second pair of goals deals with the multi-slot critical section problem. We present algorithms for controlled access to a critical section. As for the number of slots required, a tight bound of t + 1 is proved in case the slots are identical. In the case of distinct slots the upper bound is 2t + 1.

The ability of the strongest parallel random access machine model WRAM is investigated. In this model different processors may simultaneously try to write into the same cell of the common memory. It has been shown that a parallel RAM without this option (PRAM), even with arbitrarily many processors, can almost never achieve sublogarithmic time. On the contrary, every function with a small domain like binary values in case of Boolean functions can be computed by a WRAM in constant time. The machine makes fast table look-ups using its simultaneous write ability. The main result of this paper implies that in general this is the “only way” to perform such fast computations and that a domain of small size is necessary. Otherwise simultaneous writes do not give an advantage. Functions with large domains for which any change of one of the n arguments also changes the result are considered, and a logarithmic lower time bound for WRAMs is proved. This bound can be achieved by machines that do not perform simultaneous writes. A simple example of such a function is the sum of n natural numbers.

One of the frequently used models for a synchronous parallel computer is that of a parallel random access machine, where each processor can read from and write into a common random access memory. Different processors may read the same memory location at the same time, but simultaneous writing is disallowed. We show that even if we allow nonuniform algorithms, an arbitrary number of processors, and arbitrary instruction sets, $\Omega (\log n)$ is a lower bound on the time required to compute various simple functions, including sorting n keys and finding the logical “or” of n bits. We also prove a surprising time upper bound of $.72\log _2 n$ steps for these functions, which beats the obvious algorithms requiring $\log _2 n$ steps.If simultaneous writes are allowed, there are simple algorithms to compute these functions in a constant number of steps.

Byzantine Agreement has become increasingly important in establishing distributed properties when errors may exist in the systems. Recent polynomial algorithms for reaching Byzantine Agreement provide us with feasible solutions for obtaining coordination and synchronization in distributed systems. In this paper the amount of information exchange necessary to ensure Byzantine Agreement is studied. This is measured by the total number of messages the participating processors have to send in the worst case. In algorithms that use a signature scheme, the number of signatures appended to messages are also counted. First it is shown that Ω( nt ) is a lower bound for the number of signatures for any algorithm using authentication, where n denotes the number of processors and t the upper bound on the number of faults the algorithm is supposed to handle. For algorithms that reach Byzantine Agreement without using authentication this is even a lower bound for the total number of messages. If n is large compared to t , these bounds match the upper bounds from previously known algorithms. For the number of messages in the authenticated case we prove the lower bound Ω( n + t 2 ). Finally algorithms that achieve this bound are presented.

Probabilistic parallel algorithms are described to sort n keys and to select the k-smallest element among them. For each problem we construct a probabilistic parallel decision tree. The tree for selection finishes with high probability in constant time and the sorting tree in time $O(\log n)$. The same time bound for sorting can also be achieved by a probabilistic parallel machine consisting of n RAMs, each with small private memory, and a common memory of size $O(n)$. These algorithms meet the information theoretic lower bounds.

Lower bounds for sequential and parallel random access machines (RAM's, WRAM's) and distributed systems of RAM's (DRAM's) are proved. We show that, when p processors instead of one are available, the computation of certain functions cannot be speeded up by a factor p but only by a factor 0 (log(p)). For DRAM's with communication graph of degree c a maximal speedup 0 (log(c)) can be achieved for these problems. We apply these results to testing the solvability of linear diophantine equations. This generalizes a lower bond of Yao for parallel computation trees. Improving results of Dobkin/Lipton and Klein/Meyer auf der Heide, we establish large lower bounds for the above problem on RAM's. Finnaly we prove that at least log (n) + 1 steps are necessary for computing the sum of n integers by a WRAM regardless of the number of processors and the solution of write conflicts.

We prove the following lower bounds for on line computation.

Two different notions of Byzantine Agreement - immediate and eventually - are defined depending on whether the agreement involves an action to be performed synchronously or not. The lower bounds for time complexity depend on what kind of agreement has to be achieved. All previous algorithms to reach Byzantine Agreement ensure immediate agreement. We present two algorithms that in many cases reach the second type of agreement faster than previously known algorithms showing that there actually is a difference between the two notions: Eventual Byzantine Agreement can be reached earlier than Immediate.

Byzantine Agreement has become increasingly important in establishing distributed properties when there may exist errors in the systems. Recent polynomial algorithms for reaching Byzantine Agreement provide us with feasible solutions for obtaining coordination and synchronization in distributed systems. In this paper we study the amount of information exchange necessary to ensure Byzantine Agreement. This is measured by the number of messages and the number of signatures appended to messages (in case of authenticated algorithms) the participating processors need to send, in the worse case, in order to reach Byzantine Agreement. The lower bound for the number of signatures in the authenticated case is Ω(nt), where n is the number of participating processors and t is the upper bound on the number of faults. If n is large compared to t, it matches the upper bounds from previously known algorithms. The lower bound for the number of messages is Ω(n+t2). We present an algorithm that achieves this bound and for which the number of phases does not exceed the minimum t+1 by more than a constant factor.

We describe a probabilistic parallel algorithm to sort n keys drawn from some arbitrary total ordered set. This algorithm can be implemented on a parallel computer consisting of n RAMs, each with small private memory, and a common memory of size O(n) such that the average runtime is bounded by O(log n). Hence for this algorithm the product of time and number of processors meets the information theoretic lower bound for sorting.

Every family of graphs G. with n nodes and bounded mdegree can be pebbled with o(n) pebbles m time o(n ~+') for all • > 0 There ts a family of graphs G. such that pebbling G. with O(n/logn) pebbles reqmres more than n(logn)* moves for all k.The N-node jellyfish graph can be pebbled with O((IogN) 2) pebbles and O( N ) moves.

Logarithmically t(n)-time bounded RAMs can be simulated by t(n)/log t(n)-tape bounded Turing machines, t(n)-time bounded multidimensional multitape Turing machines can be simulated by t(n) loglog t(n)/log t(n)-tape bounded Turing machines.

Every alternating t(n) -time bounded multitape Turing machine can be simulated by an alternating t(n) -time bounded 1-tape Turing machine. Every nondeterministic t(n) -time bounded 1-tape Turing machine can be simulated by an alternating O(n+(t(n))1/2) -time bounded 1-tape Turing machine. For well-behaved functions t(n) every nondeterministic t(n) -time bounded 1-tape Turing machine can be simulated by a deterministic ((n log n)1/2 + (t(n))1/2) -tape bounded off-line Turing machine. These results improve or extend results by Chandra-Stockmeyer, Lipton-Tarjan and Paterson.

Every family of graphs Gn with n nodes and bounded in-degree can be pebbled with o(n) pebbles in time o(n 1+c) for all c≫0. There is a family of graphs Gn such that pebbling Gn with O(n/log n) pebbles requires ω(n(log n)k) moves for all k. The n-node jellyfish-graph as defined in (1) can be pebbled with O((log n)2) pebbles and O(n) moves.