This paper considers the question of identifying the parameters governing the behavior of
fundamental global network problems. Many papers on distributed network algorithms …

We show that proving exponential lower bounds on depth four arithmetic circuits imply
exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for …

Algorithms are developed that adopt a novel implicit representation for multivariate
polynomials and rational functions with rational coefficients, that of black boxes for their …

We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We
give an upper bound of O (log n+ log log (1//spl epsiv/)) on the circuit depth for computing an …

The Boolean formula value problem is to determine the truth value of a variable-free
Boolean formula, or equivalently, to recognize the true Boolean sentences. N. Lynch [ll] gave …

This paper deals with the evaluation of acyclic Boolean conjunctive queries in relational
databases. By well-known results of Yannakakis [1981], this problem is solvable in …

Publisher Summary This chapter discusses the complexity of finite functions. A deterministic
Turing machine consists of a finite control and a finite collection of tapes each with a head …

The second part of this Handbook presents a choice of material on the theory of automata
and rewriting systems, the foundations of modern programming languages, logics for …

Publisher Summary This chapter presents the field of finite automata, which is a branch of
mathematics connected with the algebraic theory of semigroups and associative algebras …

The greedy sequential algorithm for maximal independent set (MIS) loops over the vertices
in an arbitrary order adding a vertex to the resulting set if and only if no previous neighboring …