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

DOI10.1137/S0097539793250330zbMath0845.68052OpenAlexW2070432726MaRDI QIDQ4857593

Pankaj Rohatgi, Suresh Chari, 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

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

Related Items (13)

Is Valiant-Vazirani's isolation probability improvable? ⋮ Dual VP classes ⋮ On testing for zero polynomials by a set of points with bounded precision. ⋮ A deterministic parallel reduction from weighted matroid intersection search to decision ⋮ Tropical combinatorial Nullstellensatz and sparse polynomials ⋮ Unnamed Item ⋮ The consequences of eliminating NP solutions ⋮ Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in ⋮ Recent Results on Polynomial Identity Testing ⋮ A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Bipartite Perfect Matching is in Quasi-NC

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