A unified method for placing problems in polylogarithmic depth

DOI10.4230/LIPICS.FSTTCS.2017.36MaRDI QIDQ5136328zbMATH OpenFDO

Authors A. Krebs, Nutan Limaye, Michael Ludwig

Publication date 25 November 2020

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2017.36

zbMATH Keywords

parallel algorithmspolylogarithmic depthterm evaluation

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• A universal tree balancing theorem
• scientific article; zbMATH DE number 1859215
• Read-once branching programs for tree evaluation problems
• Pebbles and branching programs for tree evaluation
• On parallel evaluation of certain classes of polynomials with an increasing number of variables

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• An Optimal Parallel Algorithm for Formula Evaluation
• Arithmetic circuits: a chasm at depth 3
• Balancing bounded treewidth circuits
• Complexity of Regular Functions
• Constructing small tree grammars and small circuits for formulas
• Cost register automata for nested words
• Counting Euler tours in undirected bounded treewidth graphs
• Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)
• Counting paths in VPA is complete for \#NC\(^{1}\)
• scientific article; zbMATH DE number 1722707 (Why is no real title available?)
• scientific article; zbMATH DE number 440476 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 839542 (Why is no real title available?)
• scientific article; zbMATH DE number 6472651 (Why is no real title available?)
• Log Space Recognition and Translation of Parenthesis Languages
• On the Correlation of Parity and Small-Depth Circuits
• On uniform circuit complexity
• Parity, circuits, and the polynomial-time hierarchy
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Parallel Evaluation of General Arithmetic Expressions
• The Polynomially Bounded Perfect Matching Problem Is in NC 2

Cited in

(1)

• A universal tree balancing theorem

This page was built for publication: A unified method for placing problems in polylogarithmic depth

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