The Dynamic Parallel Complexity of Computational Circuits

DOI10.1137/S0097539795281724zbMATH Open0940.68101OpenAlexW2068154147MaRDI QIDQ4268813

Gary Lee 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

complexityparallel algorithmsBoolean circuitsalgebraic computationsNC problemsthe circuit value problem

Mathematics Subject Classification ID

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

Related Items (3)

Upper and lower bounds for recurrent and recursively decomposable parallel processor‐networks ⋮ Parallel Processes with Implicit Computational Capital ⋮ Time-space tradeoffs for computing functions, using connectivity properties of their circuits

Recommendations

• Unnamed Item 👍 👎
• Unnamed Item 👍 👎
• Unnamed Item 👍 👎
• Unnamed Item 👍 👎
• Complexity measures on systems of parallel algorithms 👍 👎
• A complexity theory of efficient parallel algorithms 👍 👎
• Complexity theory of parallel time and hardware 👍 👎
• On the complexity of parallelizing sequential circuits using the parallel-prefix method 👍 👎

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