Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Pseudo-deterministic NC:
TR21-121 | 21st August 2021
Sumanta Ghosh, Rohit Gurjar

Matroid Intersection: A pseudo-deterministic parallel reduction from search to weighted-decision

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 ... more >>>

ISSN 1433-8092 | Imprint