2026-08-16T23:22:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14734 2024-03-06T10:54:46Z ddc:004 open_access

Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision Ghosh, Sumanta Gurjar, Rohit Linear Matroid Matroid Intersection Parallel Complexity Pseudo-deterministic NC We study the matroid intersection problem from the parallel complexity perspective. Given two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted decision version where with the two matroids, we are given small weights on the ground set elements and a target weight W, and the question is to decide whether there is a common base of weight at least W. From the perspective of parallel complexity, the relation between the search and the decision versions is not well understood. We make a significant progress on this question by giving a pseudo-deterministic parallel (NC) algorithm for the search version that uses an oracle access to the weighted decision. The notion of pseudo-deterministic NC was recently introduced by Goldwasser and Grossman [Shafi Goldwasser and Ofer Grossman, 2017], which is a relaxation of NC. A pseudo-deterministic NC algorithm for a search problem is a randomized NC algorithm that, for a given input, outputs a fixed solution with high probability. In case the given matroids are linearly representable, our result implies a pseudo-deterministic NC algorithm (without the weighted decision oracle). This resolves an open question posed by Anari and Vazirani [Nima Anari and Vijay V. Vazirani, 2020]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sumanta Ghosh and Rohit Gurjar 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.41 urn:nbn:de:0030-drops-147342 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.41 eng https://creativecommons.org/licenses/by/4.0/legalcode