Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
From MaRDI portal
Publication:4857593
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
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