An Optimal Parallel Algorithm for Formula Evaluation

DOI10.1137/0221046zbMath0825.68424OpenAlexW2068638452MaRDI QIDQ4018401

Arvind Kumar Gupta, Vijaya Ramachandran, Stephen A. Cook, Samuel R. Buss

Publication date: 16 January 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221046

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Related Items (29)

The NP Search Problems of Frege and Extended Frege Proofs ⋮ A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators ⋮ Speedup of determinism by alternation for multidimensional Turing machines ⋮ Monomials, multilinearity and identity testing in simple read-restricted circuits ⋮ On uniformity within \(NC^ 1\) ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ On log-time alternating Turing machines of alternation depth k ⋮ Complexity of regular functions ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic ⋮ Rudimentary reductions revisited ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ On input read-modes of alternating Turing machines ⋮ Counting paths in VPA is complete for \(\#\mathrm{NC}^1\) ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ Planar and grid graph reachability problems ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ Cost Register Automata for Nested Words ⋮ Nondeterministic \(NC^1\) computation ⋮ Circuits over PP and PL ⋮ Unnamed Item ⋮ The complexity of solitaire ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ Frege proof system and TNC° ⋮ Frege proof system and TNC° ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ Hardness of approximation for knapsack problems ⋮ The complexity of computing maximal word functions

This page was built for publication: An Optimal Parallel Algorithm for Formula Evaluation