Parallelizing time with polynomial circuits

DOI10.1007/S00224-009-9237-ZMaRDI QIDQ2429726zbMATH OpenOpenAlexFDO

Authors Ryan Williams

Publication date 1 April 2011

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-009-9237-z

zbMATH Keywords

circuit complexityalternationparallel speedup

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Simulation of Parallel Random Access Machines by Circuits
• Parallelism Always Helps
• scientific article; zbMATH DE number 4051005
• Non-uniform depth of polynomial time and space simulations.
• New lower bounds for parallel computation

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3954278 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Alternation
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• Circuit size is nonlinear in depth
• Constant Depth Reducibility
• Non-uniform depth of polynomial time and space simulations.
• Nondeterministic Space is Closed under Complementation
• On Relating Time and Space to Size and Depth
• On Time Versus Space
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• On time versus space III
• On time versus space. II
• On uniform circuit complexity
• Parallelism Always Helps
• Properties that characterize LOGCFL
• Simulation of Parallel Random Access Machines by Circuits
• Speedups of deterministic machines by synchronous parallel machines

Cited in

(1)

• Non-uniform depth of polynomial time and space simulations.

This page was built for publication: Parallelizing time with polynomial circuits

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