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


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


7

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


6

$n^2$ processors can compare all ${n \choose 2}$ possibilities in constant depth, so yes it's in NC.


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

From what i know, The BSP and LogP models are used today for distributed algorithms. Also, since GPU computing, the PRAM as become again popular, however one should include the memory hierarchies in the analysis. You can check the UPMH model (Uniform Parallel memory hierarchy) which complements nicely to PRAM. B. Alpern, L. Carter, E. Feig, and T. Selker. ...


4

They are the same: BPNC = DBPNC. Say a BPNC machine is given as input a DBPNC program to simulate. Execute the program in lock step. First assume that the indices between different steps are distinct, so that we do not need to remember old random bits. At each step, each processor asks for a random bit at a specific index into the shared stream. Compute ...


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

You may be interested to this survey done by a Ph.D. student, which is updated to 2009 and presents classical work on parallel clustering. The survey is full of references you may then read to delve into the gory details.


3

There's been recent work on doing clustering in the MRC model (a formal model for analyzing mapreduce computations). Specifically, you should look at the work by Bahmani et al in VLDB 2012 on k-means$||$ and earlier work by Ene et al in KDD 2011 on the same topic. These papers have some discussion of the general problem of parallelizing $k$-means, which ...


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


3

As already suggested above, process algebra or process calculus is the place to start. Quoting freely from the respective Wikipedia page, History In the first half of the 20th century, various formalisms were proposed to capture the informal concept of a computable function, with μ-recursive functions, Turing Machines and the lambda calculus ...


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


2

There is now a jump function for SFMT (a fast Mersenne Twister implementation). This allows me to initialise 1000 MTs so that there is no cycle overlap. And SFMT should be faster than MTGP. Almost perfect for my purposes.


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


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


1

You can refer Roger Wattenhofer's Lecture note on PODC. Here I mentioned some other courses on distributed algorithms.


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