The Parallel Evaluation of General Arithmetic Expressions
From MaRDI portal
Publication:4401551
DOI10.1145/321812.321815zbMath0276.68010DBLPjournals/jacm/Brent74OpenAlexW2130566259WikidataQ56813864 ScholiaQ56813864MaRDI QIDQ4401551
Publication date: 1974
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321812.321815
Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01)
Related Items (only showing first 100 items - show all)
Improved parallel solution of a triangular linear system ⋮ Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ A chained-matrices approach for parallel computation of continued fractions and its applications ⋮ Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs ⋮ On computing accurate singular values and eigenvalues of matrices with acyclic graphs ⋮ Finding least-weight subsequences with fewer processors ⋮ A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators ⋮ Finding small simple cycle separators for 2-connected planar graphs ⋮ An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram ⋮ The delay of circuits whose inputs have specified arrival times ⋮ Optimal edge ranking of trees in polynomial time ⋮ Dynamic expression trees ⋮ Optimal computation of prefix sums on a binary tree of processors ⋮ Finding all periods and initial palindromes of a string in parallel ⋮ Fast parallel graph searching with applications ⋮ Optimal parallel construction of prescribed tournaments ⋮ Communication-efficient parallel algorithms for distributed random-access machines ⋮ Types of depth and formula size ⋮ A parallel bucket sort ⋮ An optimally efficient selection algorithm ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Sweep methods for parallel computational geometry ⋮ Parallel computation of polynomial GCD and some related parallel computations over abstract fields ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Feasible arithmetic computations: Valiant's hypothesis ⋮ Parallel computational geometry ⋮ Parallel local search ⋮ A note on parallel algorithms for optimal h-v drawings of binary trees ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Balancing bounded treewidth circuits ⋮ Size-depth tradeoff in non-monotone Boolean formulae ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ A space efficient algorithm for the monotone planar circuit value problem ⋮ Two parallel algorithms for finding all minimal maximum subsequences ⋮ Scalability and communication in parallel low-complexity lossless compression ⋮ Parameterized random complexity ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Methods and means of parallel processing of information ⋮ On the applicability of Post's lattice ⋮ On treewidth, separators and Yao's garbling ⋮ Sufficient conditions for the existence of spanning colored trees in edge-colored graphs ⋮ Parallel tree pattern matching ⋮ A complexity theory of efficient parallel algorithms ⋮ An optimal parallel algorithm for linear programming in the plane ⋮ Parallel recognition of complement reducible graphs and cotree construction ⋮ Subtree isomorphism is in random NC ⋮ Optimal computation of shortest paths on doubly convex bipartite graphs ⋮ Use of algebraically independent numbers for zero recognition of polynomial terms. ⋮ A unified approach to parallel depth-first traversals of general trees ⋮ Processor-efficient implementation of a maximum flow algorithm ⋮ Planar orientations with low out-degree and compaction of adjacency matrices ⋮ Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks ⋮ Data-movement-intensive problems: Two folk theorems in parallel computation revisited ⋮ Parallel restructuring and evaluation of expressions ⋮ Optimal parallel algorithms for forest and term matching ⋮ A work-time optimal algorithm for computing all string covers ⋮ Parallel detection of all palindromes in a string ⋮ Fast parallel string prefix-matching ⋮ Parallel rectilinear shortest paths with rectangular obstacles ⋮ Parallel solution of Toeplitzlike linear systems ⋮ Engineering parallel string sorting ⋮ A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution ⋮ Symbolic computation of derivations using labelled trees ⋮ Towards optimal simulations of formulas by bounded-width programs ⋮ Parallel recognition of series-parallel graphs ⋮ Counting paths in VPA is complete for \(\#\mathrm{NC}^1\) ⋮ A faster parallel algorithm for a matrix searching problem ⋮ Scheduling \(UET\)-tasks on a star network: complexity and approximation ⋮ Bounds on the parallel evaluation of arithmetic expressions using associativity and commutativity ⋮ On measures of space over real and complex numbers ⋮ The time required to evaluate division-free arithmetic expressions ⋮ The cache complexity of multithreaded cache oblivious algorithms ⋮ Constructing arrangements optimally in parallel ⋮ On limits on the computational power of data-accumulating algorithms ⋮ Parallel computation of the Burrows Wheeler transform in compact space ⋮ Building heaps in parallel ⋮ Optimal parallel quicksort on EREW PRAM ⋮ Algebraic Complexity Classes ⋮ Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Computing Prüfer codes efficiently in parallel ⋮ Circuits over PP and PL ⋮ An \(O(n \log n)\) time algorithm for computing the path-length distance between trees ⋮ Lower bounds on the depth of monotone arithmetic computations ⋮ Improved parallel construction of wavelet trees and rank/select structures ⋮ An algorithm for the Tutte polynomials of graphs of bounded treewidth ⋮ On the rapid computation of various polylogarithmic constants ⋮ OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS ⋮ An optimal parallel connectivity algorithm ⋮ Geometric complexity theory: an introduction for geometers ⋮ Size-depth trade-offs for monotone arithmetic circuits ⋮ On parallel rectilinear obstacle-avoiding paths ⋮ On optimal parallel computations for sequences of brackets ⋮ Parallel solutions to geometric problems in the scan model of computation ⋮ Testing string superprimitivity in parallel ⋮ Size-depth tradeoffs for Boolean formulae ⋮ Resequencing a set of strings based on a target string ⋮ Limitations of sums of bounded read formulas and ABPs
This page was built for publication: The Parallel Evaluation of General Arithmetic Expressions
