The complexity of parallel search
The subject of the paper is the computational complexity of some parallel search algorithms within the framework of independence systems. Evolved from earlier work on parallel algorithms for concrete problems (the determination of a maximal independent set of vertices or a maximum matching in a graph), the research results in a parallel analog of the self-reducibility process, specific for sequential computation. Three types of independence systems are considered: matroids, graphic matroids and partition matroids. Lower and upper bounds on the deterministic and randomized complexity of these problems are derived. These bounds may be used to highlight the processor-time trade-offs that are possible. In the same time, it results that randomized parallel algorithms are much more powerful than deterministic ones, and even the randomized algorithms cannot make effective use of extremely large numbers of processors.
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Algorithmic versus axiomatic definitions of matroids
- Constructing a perfect matching is in random NC
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- On efficient parallel strong orientation
- Probability Inequalities for Sums of Bounded Random Variables
- The tail of the hypergeometric distribution
- Three Versions of a Group Testing Game
- Oracle branching programs and Logspace versus \(P^*\)
- An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
- A predetermined algorithm for detecting a counterfeit coin with a multi-arms balance
- Designing algorithms by expectations
- The probabilistic method yields deterministic parallel algorithms
- A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
- On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
- Parallel searching in generalized Monge arrays
- Probabilistic recurrence relations revisited
- A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
- Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
- Optimal detection of a counterfeit coin with multi-arms balances
- Designing checkers for programs that run in parallel
- Linear matroid intersection is in quasi-NC
- The opacity of backbones
- An adaptive algorithm for maximization of non-submodular function with a matroid constraint
- On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
- Searching for two counterfeit coins with two-arms balance
- Parallel strategies for direct multisearch
- Black-box Complexity of Parallel Search with Distributed Populations
- Lower bounds on black-box reductions of hitting to density estimation
- Some independence results in complexity theory†
- scientific article; zbMATH DE number 176084 (Why is no real title available?)
- scientific article; zbMATH DE number 1163099 (Why is no real title available?)
- scientific article; zbMATH DE number 2068040 (Why is no real title available?)
- scientific article; zbMATH DE number 865205 (Why is no real title available?)
- Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- (Probabilistic) recurrence relations revisited
- Анализ сложности алгоритма параллельного поиска “золотой” коллизии
- Parallel exhaustive search without coordination
- A deterministic parallel reduction from weighted matroid intersection search to decision
- Parallel searching of multidimensional cubes
- Parallelizing scheduling algorithms for resource allocation under V-RAN
- Parallel approximation and exact algorithms for resource scheduling in v-RANs
- A global parallel algorithm for the hypergraph transversal problem
- A complexity theory of efficient parallel algorithms
- On the complexity of monotone dualization and generating minimal hypergraph transversals
This page was built for publication: The complexity of parallel search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106664)