An Optimal Parallel Algorithm for Formula Evaluation

DOI10.1137/0221046zbMATH Open0825.68424OpenAlexW2068638452MaRDI QIDQ4018401FDOQ4018401

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

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

Mathematics Subject Classification ID

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

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
• Hardness of approximation for knapsack problems
• Interpolating Arithmetic Read-Once Formulas in Parallel
• Rudimentary reductions revisited
• Relationships among $PL$, $\#L$, and the determinant
• On uniformity within \(NC^ 1\)
• An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic
• Title not available (Why is that?)
• The complexity of solitaire
• 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
• Monomials, multilinearity and identity testing in simple read-restricted circuits
• Sparse hard sets for P: Resolution of a conjecture of Hartmanis
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Circuits over PP and PL
• Frege proof system and TNC°
• Log-space algorithms for paths and matchings in \(k\)-trees
• Complexity of regular functions
• On input read-modes of alternating Turing machines

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)