M Agrawal, V Vinay - 2008 49th Annual IEEE Symposium on …, 2008 - ieeexplore.ieee.org
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 …
E Kaltofen, BM Trager - Journal of Symbolic Computation, 1990 - Elsevier
Algorithms are developed that adopt a novel implicit representation for multivariate polynomials and rational functions with rational coefficients, that of black boxes for their …
R Cleve, J Watrous - Proceedings 41st Annual Symposium on …, 2000 - ieeexplore.ieee.org
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 …
SR Buss - Proceedings of the nineteenth annual ACM symposium …, 1987 - dl.acm.org
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 …
RB Boppana, M Sipser - Algorithms and complexity, 1990 - Elsevier
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 …
D Perrin - Formal Models and Semantics, 1990 - Elsevier
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 …
GE Blelloch, JT Fineman, J Shun - … of the twenty-fourth annual ACM …, 2012 - dl.acm.org
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 …