An Optimal Parallel Algorithm for Formula Evaluation

DOI10.1137/0221046MaRDI QIDQ4018401zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• The Dynamic Parallel Complexity of Computational Circuits
• scientific article; zbMATH DE number 3958731
• scientific article; zbMATH DE number 4213451
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem

Cited in

(32)

• Planar and grid graph reachability problems
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Cost register automata for nested words
• Frege proof system and TNC°
• On adaptive DLOGTIME and POLYLOGTIME reductions
• The NP search problems of Frege and extended Frege proofs
• Nondeterministic NC^1 computation
• On log-time alternating Turing machines of alternation depth k
• Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)
• On the space and circuit complexity of parameterized problems: classes and completeness
• The complexity of computing maximal word functions
• Rudimentary reductions revisited
• Hardness of approximation for knapsack problems
• Interpolating Arithmetic Read-Once Formulas in Parallel
• An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic
• On uniformity within \(NC^ 1\)
• The complexity of solitaire
• Relationships among $PL$, $\#L$, and the determinant
• scientific article; zbMATH DE number 440476 (Why is no real title available?)
• A generalization of Spira's theorem and circuits with small segregators or separators
• A generalization of Spira's theorem and circuits with small segregators or separators
• Optimal parallel generation of a computation tree form
• Speedup of determinism by alternation for multidimensional Turing machines
• A unified method for placing problems in polylogarithmic depth
• Sparse hard sets for P: Resolution of a conjecture of Hartmanis
• Monomials, multilinearity and identity testing in simple read-restricted circuits
• Circuits over PP and PL
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Frege proof system and TNC°
• Log-space algorithms for paths and matchings in k-trees
• On input read-modes of alternating Turing machines
• Complexity of regular functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4018401)