Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems

DOI10.1137/S0097539793250330MaRDI QIDQ4857593zbMATH OpenOpenAlexFDO

Authors Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan

Publication date 24 January 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793250330

zbMATH Keywords

randomness complexityunique element isolation problem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
• Random restricted matching and lower bounds for combinatorial optimization
• On the uniqueness and numerical approximations for a matching problem
• Rerandomization and optimal matching
• Optimal Random Matchings on Trees and Applications
• scientific article; zbMATH DE number 1033855
• Perfect matchings in random uniform hypergraphs
• Random matching problems on the complete graph
• Perfect matchings in random s‐uniform hypergraphs

Cited in

(19)

• Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems
• On testing for zero polynomials by a set of points with bounded precision.
• Isolation, matching, and counting uniform and nonuniform upper bounds
• A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
• Tropical combinatorial Nullstellensatz and sparse polynomials
• Dual VP classes
• Formalizing randomized matching algorithms
• Recent results on polynomial identity testing
• Is Valiant-Vazirani's isolation probability improvable?
• The consequences of eliminating NP solutions
• Derandomizing isolation lemma for \(K_{3,3}\)-free and \(K_5\)-free bipartite graphs
• Bipartite perfect matching is in quasi-NC
• Bipartite perfect matching in pseudo-deterministic NC
• Derandomizing isolation in space-bounded settings
• scientific article; zbMATH DE number 7758310 (Why is no real title available?)
• A deterministic parallel reduction from weighted matroid intersection search to decision
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Streaming word problems
• Deterministically testing sparse polynomial identities of unbounded degree

This page was built for publication: Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems

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