Marek Karpinski, Yakov Nekrich

This paper presents new results on parallel constructions of the

length-limited prefix-free codes with the minimum redundancy.

We describe an algorithm for the construction of length-limited codes

that works in $O(L)$ time with $n$ processors for $L$ the

maximal codeword length.

We also describe an algorithm for a construction ...
more >>>

Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf

The perfect matching problem is known to

be in P, in randomized NC, and it is hard for NL.

Whether the perfect matching problem is in NC is one of

the most prominent open questions in complexity

theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem

more >>>

Siu Man Chan, Aaron Potechin

We prove tight size bounds on monotone switching networks for the NP-complete problem of

$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for

the P-complete problem of generation. This gives alternative proofs of the separations of m-NC

from m-P and of m-NC$^i$ from ...
more >>>

Ola Svensson, Jakub Tarnawski

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in $O(\log^3 n)$ time on $n^{O(\log^2 n)}$ processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the ... more >>>

Sumanta Ghosh, Rohit Gurjar

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

Rohit Gurjar, Taihei Oki, Roshan Raj

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

Vikraman Arvind, Pushkar Joglekar

We study the \emph{noncommutative rank} problem, $\NCRANK$, of computing the rank of matrices with linear entries in $n$ noncommuting variables and the problem of \emph{noncommutative Rational Identity Testing}, $\RIT$, which is to decide if a given rational formula in $n$ noncommuting variables is zero on its domain of definition.

... more >>>