16
On techniques for proving poly-log circuit-depth lower bounds, all current approaches work under restricted settings.
Like, in the work leading to GCT that you mention, the lower bound applies to a restricted PRAM model without bit operations.
Under another restriction, which is the monotone restriction for monotone boolean functions, there is a Fourier-...
14
First of all, there is a formal definition of "quantum-NC", see QNC on the zoo.
GCD is indeed a good candidate for a problem that could be shown to be in QNC, but it's not known to be in NC. However, finding a QNC algorithm for GCD is still an open problem.
The feeling for which this is believed to be true comes from the fact that the Quantum Fourier ...
14
Following the suggestion of Kaveh, I am putting my comment as an (expanded) answer.
Concerning $Q1$, a word of caution is in order: even logarithmic depth if far from being understood, not speaking about poly-logarithmic. So, in the non-monotone world, the real problem is much less ambitious:
Beating Log-depth Problem: Prove a super-linear(!) lower bound ...
13
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-negligible. If you observe that it is the case, please tell me and I'll update my answer.
The report Parallel Algorithms for Depth-First Search discusses ...
11
The essential difference between quantum computation and parallelism is for the most part the same as between randomized computation (e.g. using coin-flips, or some other form of random number generation) and parallelism.
In randomized computation, depending on the outcome of the coin-flips, you explore one out of many possible computational possibilities. ...
10
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) https://arxiv.org/pdf/1601.06319.pdf and our work with Ola Svensson (for general graphs): https://arxiv.org/pdf/1704.01929
9
This idea, known as Time loop logic has been investigated by Moravec, Deutsch and Aaronson.
8
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 use spatial locality to put the states of local systems into primary memory, and record the whole state in secondary memory. If you can't contain the whole state ...
8
Yes, it is in $\mathsf{NC}^2$:
Mulmuley, K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica 7 (1987), no. 1, 101–104.
The following (earlier) paper shows that solving a system of linear equations reduces to computing the rank, and thus, together with the above result, solving the system (in particular, ...
7
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 tool beeing the TLA+ tool is a program that verifies properties of specifications expressed in temporal logic; googling for "TLA+ dining philosopher" links to ...
5
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 algorithm). The more recent paper by Blelloch et al. shows that the randomized-incremental approach for constant-dimensional LP can actually be parallelized ...
4
Do not use a single stream of random numbers generated in one thread (or process) and consumed in other threads (or processes). In general, you must instead use several random number streams for your calculations, one for each thread/process. It is extremely important for these streams to be uncorrelated, in order for the pseudorandom numbers to be effective ...
4
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 find a basis of its column span in $\mathrm{AC}_0$ by running over all subsets in parallel and checking in parallel whether a nontrivial linear combination ...
4
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 Distributed Computation is Communication Expensive" http://arxiv.org/abs/1304.4636
See also this work for closely related models:
Klauck et al.: "Distributed ...
4
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.
3
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 reductions a multiprocessor is carrying out. So TMs can do a sequential simulation of a parallel computation. Whether this a genuine model of parallel computation ...
3
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.
Their Theorem 10 gives a deterministic CRCW algorithm for $st$-reachability in planar digraphs with $O(n)$ processors and $O(\log^3 n)$ time. Searching Google ...
3
Since you know that you must process each element and tasks are independent, i.e., the algorithm is embarrassingly parallel, in the Dynamic Multithreading model you should simply use a parallel for instead of spawning threads as you do, and let the compiler implement this optimally.
The work (sequential time) is $T_1 = O(nk)$ because you need to process ...
2
Short answer: yes.
Long answer: Using process algebra as a witness to the claimed existential is certainly admissible, but the way the question is phrased might warrant are more direct answer. If TMs are used as mathematical model for sequential computation, we can surely come up with a concurrent version, and show that it is no more powerful than the good ...
2
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 the trivial and obvious thing to parallelize (whatever that may be), it works, and there's no need for sophisticated solutions.
2
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 order to be a superset of session
order:
$$\text{PRAM} \triangleq so \subseteq vis.$$
Thus, the offending arrow in your diagram, from $w(x)0$ to $r(x)0$, is ...
2
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 also has a decent overview
note it has some similarity/resemblance to unix pipes/filters
there is an implementation in Java, JCSP by Welch/Brown & other ...
1
You can refer Roger Wattenhofer's Lecture note on PODC.
Here I mentioned some other courses on distributed algorithms.
1
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.
However, for Mersenne-Twister there exists a special implementation called Dynamic Creator where it is possible to draw seeds that give some guarantees regarding ...
1
$T_\infty$ means you have as many processor as you need (theoretically an infinite number). The strategy to assign each iteration to one processor is base on Divide and Conquer. So, at first, one processor split the number of iterations in two, spawn a new thread with the first half and recursively processes the other half. Then this two processors split ...
1
I understand the proof as follows.
Start with an arbitrary execution of the above algorithm. In this execution each operation on $TS[i]$ and $Val[i]$ has already been linearlized by assuming that these are single-writer multi-reader atomic registers. Therefore, by assumption, the schedule linearizes these low level operations.
The remainder of the proof ...
1
Also Petri nets form a computational model tailored for concurrency. The basic vanilla system is a finite state based model, but there exist more involved models (having "inhibitor arcs" or "coloured nets") that reach Turing power.
Nice part of Petri nets is their graphical nature. Modern application includes the modelling of biological processes (e.g. in ...
Only top voted, non community-wiki answers of a minimum length are eligible
