Randomised algorithms

DOI10.1016/0166-218X(83)90023-9zbMath0506.68040OpenAlexW4212805448MaRDI QIDQ1836980

Dominic 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 optimizationhierarchiesprimality testsmatrix multiplicationpolynomial multiplicationchecking polynomial identitieslanguages recognisable by randomised algorithmsperfect matchings in graphsrandomly 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)

Related Items

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, BPP and the polynomial hierarchy, Combinatorics and connectionism

Cites Work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Gaussian elimination is not optimal
• The Complexity of Enumeration and Reliability Problems
• New Fast Algorithms for Matrix Operations
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Random Graph Isomorphism
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Probabilistic Algorithms in Finite Fields
• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• Paths, Trees, and Flowers
• Relativized questions involving probabilistic algorithms
• Factoring Polynomials Over Large Finite Fields
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item