The Dynamic Parallel Complexity of Computational Circuits

DOI10.1137/S0097539795281724MaRDI QIDQ4268813zbMATH OpenOpenAlexFDO

Authors Gary L. Miller, Shang-Hua Teng

Publication date 28 October 1999

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

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

zbMATH Keywords

complexityBoolean circuitsparallel algorithmsalgebraic computationsNC problemsthe circuit value problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 4068238
• scientific article; zbMATH DE number 4085015
• Complexity theory of parallel time and hardware
• scientific article; zbMATH DE number 4213451
• On the complexity of parallelizing sequential circuits using the parallel-prefix method
• A complexity theory of efficient parallel algorithms
• scientific article; zbMATH DE number 4074482
• Complexity measures on systems of parallel algorithms

Cited in

(5)

• Parallel processes with implicit computational capital
• An Optimal Parallel Algorithm for Formula Evaluation
• Upper and lower bounds for recurrent and recursively decomposable parallel processor‐networks
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• On the dynamic initialization of parallel computers

This page was built for publication: The Dynamic Parallel Complexity of Computational Circuits

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