The complexity of parallel search
From MaRDI portal
Publication:1106664
DOI10.1016/0022-0000(88)90027-XzbMath0651.68048OpenAlexW2005390858MaRDI QIDQ1106664
Avi Wigderson, Richard M. Karp, Eli Upfal
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(88)90027-x
computational complexitymatroidsparallel searchindependence systemsrandomized complexitydeterministic complexityprocessor-time trade-offs
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Parallel numerical computation (65Y05) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items
Designing algorithms by expectations, The probabilistic method yields deterministic parallel algorithms, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, Unnamed Item, A global parallel algorithm for the hypergraph transversal problem, An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model, A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity, On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs, Optimal detection of a counterfeit coin with multi-arms balances, Designing checkers for programs that run in parallel, On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory, (Probabilistic) recurrence relations revisited, Probabilistic recurrence relations revisited, A deterministic parallel reduction from weighted matroid intersection search to decision, A complexity theory of efficient parallel algorithms, A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs, Oracle branching programs and Logspace versus \(P^*\), On the complexity of monotone dualization and generating minimal hypergraph transversals, An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3, Linear matroid intersection is in quasi-NC, The opacity of backbones, Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set, A predetermined algorithm for detecting a counterfeit coin with a multi-arms balance, Searching for two counterfeit coins with two-arms balance, An adaptive algorithm for maximization of non-submodular function with a matroid constraint
Cites Work
- Unnamed Item
- Unnamed Item
- On efficient parallel strong orientation
- Constructing a perfect matching is in random NC
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- The tail of the hypergeometric distribution
- Three Versions of a Group Testing Game
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Algorithmic versus axiomatic definitions of matroids
- Probability Inequalities for Sums of Bounded Random Variables
