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

checking polynomial identitiescombinatorial optimizationhierarchieslanguages recognisable by randomised algorithmsmatrix multiplicationperfect matchings in graphspolynomial multiplicationprimality testsrandomly decidable languages

Mathematics Subject Classification ID

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

Cites work

• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• Factoring Polynomials Over Large Finite Fields
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Gaussian elimination is not optimal
• 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?)
• 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

(7)

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

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)