Skip to main content
Share Your Experience: Take the 2024 Developer Survey
13 votes

Problems in NC not known to lie in NC2

Disclaimer: I'm not an expert in fast parallel algorithms, hence the probability that I missed more recent results that put the problems I mention in lower levels of the $\mathsf{NC}$ hierarchy is non-...
Geoffroy Couteau's user avatar
10 votes

Deterministic Parallel algorithm for perfect matching in general graphs?

A few years later :) and Perfect Matching is now known to be in Quasi-NC (that is, you need quasi-polynomially many processors). See the paper of Fenner, Gurjar and Thierauf (for bipartite graphs) ...
Jakub Tarnawski's user avatar
10 votes
Accepted

$AC^0$[subexp] vs. NC

No, $\mathrm{AC}^0[2^{n^\delta}]$ is not included in NC; it is not even included in $\mathrm{SIZE}[2^{n^\epsilon}]$ for $\epsilon<\delta$. Indeed, any Boolean function on $n^\delta$ inputs, padded ...
Emil Jeřábek's user avatar
8 votes
Accepted

Qubit gates in google supremacy

Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They ...
Peter Shor 's user avatar
5 votes

Cases of Linear programming known to be in $NC$?

Fixed dimensional linear programming (for any constant dimension $d$) is known to be in $\mathsf{NC}$; in fact, it can be done work-efficiently (in the same amount of work as the fastest sequential ...
xal's user avatar
  • 439
4 votes
Accepted

Rank-robustness of the parallel complexity of linear algebra problems

I think the following procedure computes a basis of the column span of an $n \times n$-matrix of rank at most $\log n$ in $\mathrm{AC}_1$. If you have a matrix of size $n \times 2 \log n$, you can ...
Markus Bläser's user avatar
4 votes

To what extent, computational ability for hard tasks helps in solving easy tasks

By counting you should be able to compute about $2^{2^m \cdot s}$ functions with such circuits of size $s$ so I'd guess $s=2^{n-m}$ should be enough to compute all functions.
Boaz Barak's user avatar
3 votes

Parallel algorithms for reachability in directed planar graphs

See Kao, Ming-Yang; Klein, Philip N. (1993), Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, J. Comput. System Sci. 47 (1993), no. 3, 459–500. ...
David Eppstein's user avatar
2 votes
Accepted

Embarrassingly Parallel: Formal Definition & Citation

There is no formal answer for that question, as the notion of "embarrassingly parallel" is not a formal one; it is an informal and imprecise notion. I understand it to basically mean that if you do ...
D.W.'s user avatar
  • 12.1k
2 votes

Confusion about a formal definition of PRAM consistency

When they define PRAM (page 11 of the arxiv preprint) they actually state that vis is a partial order (in particular, transitive): We define PRAM consistency by requiring the visibility partial ...
Bjørn Kjos-Hanssen's user avatar
1 vote
Accepted

Is modular square roots modulo primes in $NC$?

Square roots modulo $2^n$ can be computed in (uniform) $\mathrm{TC}^0$. More generally, just like in On parallel complexity of modular inverse, given $X$ and $M$ in binary and $b$ in unary such that $...
Emil Jeřábek's user avatar
1 vote

Multiple independent random number streams

It was already mentioned that it is important to use independent streams. Which is not guaranteed if you, e.g., use the naive approach of just seeding each of your PRNG with a different number. ...
mithrawnuruodo's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible