A taxonomy of problems with fast parallel algorithms
From MaRDI portal
Publication:3694688
DOI10.1016/S0019-9958(85)80041-3zbMath0575.68045WikidataQ55891722 ScholiaQ55891722MaRDI QIDQ3694688
Publication date: 1985
Published in: Information and Control (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items
Oracle computations in parallel numerical linear algebra, Competitive self-stabilizing \(k\)-clustering, A note on the complexity of deciding bisimilarity of normed unary processes, A theory of strict P-completeness, Space-efficient recognition of sparse self-reducible languages, Implementing an ODE code on distributed memory computers, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Matching is as easy as matrix inversion, On path equivalence of nondeterministic finite automata, Parallelism and the maximal path problem, ALOGTIME and a conjecture of S. A. Cook, A parallel algorithm for the maximal path problem, A parallel algorithm for bisection width in trees, Parallel complexity of logical query programs, A random NC algorithm for depth first search, Expressing uniformity via oracles, Membership testing in commutative transformation semigroups, A parallelizable lexicographically first maximal edge-induced subgraph problem, A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs, On randomized versus deterministic computation, Parallel algorithms for solvable permutation groups, Some subclasses of context-free languages in \(NC^ 1\), On a complexity hierarchy between L and NL, A measure of relativized space which is faithful with respect to depth, On a proposed divide-and-conquer minimal spanning tree algorithm, Subtree isomorphism is NC reducible to bipartite perfect matching, Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs, Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\), The iterated mod problem, Characterization of idempotent transformation monoids, Programs over aperiodic monoids, A new complete language for DSPACE(log n), The parallel complexity of graph canonization under abelian group action, Counting problems and algebraic formal power series in noncommuting variables, Pipelining tree-structured algorithms on SIMD architectures, Parallel complexity of the regular code problem, Parallel models of computation: An introductory survey, A P-complete graph partition problem, Problems complete for \(\oplus L\), A comparison of boundary graph grammars and context-free hypergraph grammars, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, The complexity of short two-person games, An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic, Properties that characterize LOGCFL, Arithmetizing uniform \(NC\), \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems, Circuits for computing the GCD of two polynomials over an algebraic number field, On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields, The complexity of computing the number of strings of given length in context-free languages, Matrix inversion in RNC\(^ 1\), Characterizing parallel hierarchies by reducibilities, A note on the space complexity of some decision problems for finite automata, Oracle branching programs and Logspace versus \(P^*\), Highly parallel computations modulo a number having only small prime factors, Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem, The parallel complexity of finite-state automata problems, Learning in parallel, The expressiveness of a family of finite set languages, On adaptive DLOGTIME and POLYLOGTIME reductions, On quasilinear-time complexity theory, On input read-modes of alternating Turing machines, Using maximal independent sets to solve problems in parallel, Independent sets versus perfect matchings, Knapsack problems for NL, The complexity of circuit value and network stability, Bounded arithmetic for NC, ALogTIME, L and NL, Multiplication, division, and shift instructions in parallel random access machines, The parallel complexity of coarsest set partition problems, On iterated integer product, Parallel algorithms for separation of two sets of points and recognition of digital convex polygons, An NC algorithm for recognizing tree adjoining languages, Methods for proving completeness via logical reductions, \(NC^ 1\): The automata-theoretic viewpoint, Low-complexity aggregation in GraphLog and Datalog, Query languages for hierarchic databases, Tight complexity bounds for term matching problems, A very hard log-space counting class, Extensions to Barrington's M-program model, Unambiguity of circuits, The isomorphism problem for \(k\)-trees is complete for logspace, Reductions to graph isomorphism, Ordered vertex removal and subgraph problems, The lexicographically first topological order problem is NLOG-complete, On the complexity of topological sorting, Approximating linear programming is log-space complete for P, The effective entropies of some extensions of context-free languages, Effective entropies and data compression, Some classes of languages in \(NC^ 1\), Prediction-preserving reducibility, Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets, The computational complexity of pattern formation, Sparse hard sets for P: Resolution of a conjecture of Hartmanis, On deciding trace equivalences for processes, Parallel algorithms for matrix normal forms, Non-uniform automata over groups, Fast parallel constraint satisfaction, Parallel solutions to geometric problems in the scan model of computation, Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space, The complexity of computing maximal word functions, Relativizing small complexity classes and their theories, Equivalence classes and conditional hardness in massively parallel computations, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, Fast parallel constraint satisfaction, On parallelizing a greedy heuristic for finding small dominant sets, On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions, The proof complexity of linear algebra, The complexity of planarity testing, Strict sequential P-completeness, An unambiguous class possessing a complete set, On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, How hard is to compute the edit distance, The Isomorphism Problem for k-Trees Is Complete for Logspace, A note on some languages in uniform \(ACC^ 0\), An algebra and a logic for \(NC^ 1\), Inversion in finite fields using logarithmic depth, On the parallel complexity of linear groups, Boolean circuits versus arithmetic circuits, On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph, On uniformity within \(NC^ 1\), Ranking and formal power series, A note on logspace optimization, Parallel evaluation of arithmetic circuits, A time-space hierarchy between polynomial time and polynomial space, Evaluating Matrix Circuits, The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem, Structure and importance of logspace-MOD class, Parallélisation d'algorithmes avec un nombre fixe de processeurs, A query language for NC, Rational transductions and complexity of counting problems, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, Processing succinct matrices and vectors, Extensions of an idea of McNaughton, Testing membership: Beyond permutation groups, Characterizations of some complexity classes between Θ2p and Δ2p, The complexity of graph connectivity, Parallel complexity of iterated morphisms and the arithmetic of small numbers, The emptiness problem for intersections of regular languages, On languages accepted with simultaneous complexity bounds and their ranking problem, Nondeterministic stack register machines, On the parallel complexity of loops, Minimisation of Multiplicity Tree Automata, RelativizedNC, Rational transductions and complexity of counting problems, A query language for NC (extended abstract), Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU, On log-time alternating Turing machines of alternation depth k, The complexity of the characteristic and the minimal polynomial., Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms., The parallel complexity of elimination ordering procedures, Adaptive logspace reducibility and parallel time, Communication and information complexity, Classifying the computational complexity of problems, Inferring large graphs using \(\ell_1\)-penalized likelihood, The isomorphism problem for planar 3-connected graphs is in unambiguous logspace, Two-way automata and length-preserving homomorphisms, The computational complexity of graph problems with succinct multigraph representation, Relationships among $PL$, $\#L$, and the determinant, Data independence of read, write, and control structures in PRAM computations, A gentle introduction to applications of algorithmic metatheorems for space and circuit classes, Evaluation of circuits over nilpotent and polycyclic groups, The complexity of ranking simple languages, Weak theories of linear algebra, Division in logspace-uniformNC1, String shuffle: circuits and graphs, Unnamed Item, Unnamed Item, On the complexity of some problems on groups input as multiplication tables, Parallel identity testing for skew circuits with big powers and applications, Reductions to Graph Isomorphism, Resilient capacity-aware routing, Sublinear-time reductions for big data computing, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions, The Monotone Circuit Value Problem with Bounded Genus Is in NC, Cost Register Automata for Nested Words, Geometric complexity theory V: Efficient algorithms for Noether normalization, The complexity of the comparator circuit value problem, A theory of strict P-completeness, CONTEXT-FREE GRAMMARS WITH LINKED NONTERMINALS, Reversible space equals deterministic space, The model checking fingerprints of CTL operators, Parallel graph algorithms that are efficients on average, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, On the expressiveness of \textsc{Lara}: a proposal for unifying linear and relational algebra, A MEASURE FOR THE LEXICOGRAPHICALLY FIRST MAXIMAL INDEPENDENT SET PROBLEM AND ITS LIMITS, Threshold Circuits for Iterated Matrix Product and Powering, On the rapid computation of various polylogarithmic constants, The enumerability of P collapses P to NC, String distances and intrusion detection: Bridging the gap between formal languages and computer security, How hard is computing the edit distance?, Computing a context-free grammar-generating series, A model of sequential computation with Pipelined access to memory, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
