Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with parallel complexity:
TR02-029 | 3rd June 2002
Marek Karpinski, Yakov Nekrich

Parallel Construction of Minimum Redundancy Length-Limited Codes

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

TR06-129 | 6th October 2006
Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf

The polynomially bounded perfect matching problem is in NC^2

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

TR12-185 | 29th December 2012
Siu Man Chan, Aaron Potechin

Tight Bounds for Monotone Switching Networks via Fourier Analysis

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

TR17-059 | 6th April 2017
Ola Svensson, Jakub Tarnawski

The Matching Problem in General Graphs is in Quasi-NC

Revisions: 1

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

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

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-084 | 24th April 2024
Vikraman Arvind, Pushkar Joglekar

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

Revisions: 1

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

ISSN 1433-8092 | Imprint