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-...
- 738
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) ...
- 101
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 ...
- 14.8k
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 ...
- 23.5k
7
votes
Is there a mathematical analysis/proof available for correctness of solutions to inter process communication problems?
There has been various brand of work for formalizing such tricky code. The one I know about are (but I'm no expert on the topic):
using "temporal logic" to study distributed systems; one important ...
- 1,882
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 ...
- 429
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 ...
- 2,828
4
votes
Does such model exists?
The model studied in the following work should be a fairly close match with the model that you described (see in particular graph problems "without edge duplication"):
Woodruff & Zhang: "When ...
- 11.3k
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.
- 41
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.
...
- 50.2k
3
votes
Accepted
Is multiprocessing possible on a Turing Machine?
This is a subtle question.
TMs are very much a sequential model of computation. So in some sense, TMs cannot (directly) model multiprocessing. However, TMs can do step-by-step simulations of the ...
- 10.3k
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 ...
- 10.4k
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 ...
- 4,400
2
votes
Is there a mathematical analysis/proof available for correctness of solutions to inter process communication problems?
there is a classic reference/framework increasingly standardized:
C.A.R Hoare, Communicating Sequential Processes
a 1985 book of same title is now available as ebook with open copyright.
wikipedia ...
- 10.8k
1
vote
Modern distributed computing book
You can refer Roger Wattenhofer's Lecture note on PODC.
Here I mentioned some other courses on distributed algorithms.
- 83
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.
...
Only top scored, non community-wiki answers of a minimum length are eligible