Randomised algorithms

DOI10.1016/0166-218X(83)90023-9MaRDI QIDQ1836980zbMATH OpenOpenAlexFDO

Authors D. J. A. Welsh

Publication date 1983

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(83)90023-9

zbMATH Keywords

combinatorial optimizationmatrix multiplicationhierarchiesprimality testspolynomial multiplicationchecking polynomial identitieslanguages recognisable by randomised algorithmsperfect matchings in graphsrandomly decidable languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 3723860 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 3557236 (Why is no real title available?)
• scientific article; zbMATH DE number 3557240 (Why is no real title available?)
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)
• scientific article; zbMATH DE number 3568040 (Why is no real title available?)
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 3600081 (Why is no real title available?)
• scientific article; zbMATH DE number 3635490 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• Factoring Polynomials Over Large Finite Fields
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Gaussian elimination is not optimal
• New Fast Algorithms for Matrix Operations
• Paths, Trees, and Flowers
• Probabilistic Algorithms in Finite Fields
• Random Graph Isomorphism
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativized questions involving probabilistic algorithms
• The Complexity of Enumeration and Reliability Problems

Cited in

(6)

• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• An analysis of Monte Carlo algorithms for counting problems
• BPP and the polynomial hierarchy
• Combinatorics and connectionism
• A randomised 3-colouring algorithm
• A survey of space complexity

This page was built for publication: Randomised algorithms

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