[PDF][PDF] Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
DA Barrington - Proceedings of the eighteenth annual ACM symposium …, 1986 - dl.acm.org
We show that any language recognized by an NC 1 circuit (fan-in 2, depth O (logn)) can be
recognized by a particular type of width 5 polynomial-size branching program. As any …
recognized by a particular type of width 5 polynomial-size branching program. As any …
[PDF][PDF] Computational limitations for small depth circuits
J Håstad - 1986 - dspace.mit.edu
We study the properties of small depth circuits. The main results are establishing lower
bounds on the size of small depth circuits computing functions such as parity and majority …
bounds on the size of small depth circuits computing functions such as parity and majority …
Parallel arithmetic computations: a survey
J von zur Gathen - … Symposium on Mathematical Foundations of Computer …, 1986 - Springer
Parallel arithmetic computations: A survey Page 1 PARALLEL ARITHMETIC COMPUTATIONS:
A SURVEY Joachim yon zur Gathen University of Toronto Abstract A survey of parallel …
A SURVEY Joachim yon zur Gathen University of Toronto Abstract A survey of parallel …
[PDF][PDF] Uniform closure properties of p-computable functions
E Kaltofen - Proceedings of the eighteenth annual ACM symposium …, 1986 - dl.acm.org
Valiant [1] introduced the notion of a family of 19-computable polynomials as those
multivariate polynomials of polynomially-bounded degree and straight-line computation …
multivariate polynomials of polynomially-bounded degree and straight-line computation …
[PDF][PDF] Linear programming with two variables per inequality in poly-log time
GS Lueker, N Megiddo, V Ramachandran - Proceedings of the …, 1986 - dl.acm.org
The parallel time complexity of the linear programming problem with at most two variables
per inequality is discussed. Let n and m denote the number of variables and the number of …
per inequality is discussed. Let n and m denote the number of variables and the number of …