Randomized algorithms over finite fields for the exact parity base problem.

DOI10.1006/jcom.1999.0522zbMath1167.68466OpenAlexW1965574700MaRDI QIDQ1578505

Giulia Galbiati, Carlo Viola, Francesco Maffioli

Publication date: 3 September 2000

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.1999.0522

zbMATH Keywords

matroidsrandomized algorithmsexact problems

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Combinatorial aspects of matroids and geometric lattices (05B35) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On distinguishing prime numbers from composite numbers
• Exact arborescences, matchings and cycles
• Matching is as easy as matrix inversion
• On the computation of pfaffians
• On the computational power of pushdown automata
• Approximate formulas for some functions of prime numbers
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Random pseudo-polynomial algorithms for exact matroid problems
• Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
• On prime numbers in an arithmetic progression with a prime-power difference