Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Non-Commutative Edmonds' Problem:
TR24-044 | 28th February 2024
Rohit Gurjar, Taihei Oki, Roshan Raj

Fractional Linear Matroid Matching is in quasi-NC

The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm is unknown for linear matroid matching, which generalizes both of these problems. In this work, we propose ... more >>>

TR24-073 | 11th April 2024
Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Trading Determinism for Noncommutativity in Edmonds' Problem

Let $X=X_1\sqcup X_2\sqcup\ldots\sqcup X_k$ be a partitioned set of variables such that the variables in each part $X_i$ are noncommuting but for any $i\neq j$, the variables $x \in X_i$ commute with the variables $x' \in X_j$. Given as input a square matrix $T$ whose entries are linear forms over ... more >>>

ISSN 1433-8092 | Imprint