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
I'm happy to say that I think we can answer this question in the affirmative: that is, deciding whether a linear congruence is feasible modulo k is coModkL-complete.
We can actually reduce this problem to the special case of prime powers. One may show that:
Normal Form. The class coModkL consists of langauges L of the form L = Lp1 ∩&...
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
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 ...
6
It depends on how the query is implemented. If we are doing dictionary lookups and we stored the values using cuckoo hashing for example, then each lookup is $O(1)$ time, and doing the lookup in a batch can't possibly improve that run-time. (It takes that long just to list the values).
On the other hand, if we use a tree based data structure, we may be ...
6
$n^2$ processors can compare all ${n \choose 2}$ possibilities in constant depth, so yes it's in NC.
5
Build a "CUDA-SAT solver" and outperform the winners of the annual Sat competitions ! :-)
Edit: I posted the answer quickly ... but - after a Google search - I found that my idea is not so original, see: NVIDIA CUDA Architecture-based Parallel Incomplete SAT Solver ... however I think that a public available project/source code of a CUDA-powered SAT solver ...
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
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.
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
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 ...
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
This isn't really my area, but I think you want to Google for "the polytope model" or "the polyhedral model", and specifically for "affine-by-statement scheduling". The basic idea is that iterations in a loop nested $d$ deep are turned into a $d$-dimensional polytope, and that each iteration is a point within the polytope. You can then look at data ...
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
here are my answers to your questions.
1) In general, you can not come up with efficient schemes for scaling down the number of processor from $n$ to $p < n$. Why ? Because, even without taking into account additional issues such as caches etc, the problem is strictly related to how you map tasks to processors, which is known to be an NP-complete problem....
3
To the best of my knowledge, parallelization of this problem is not done as you suggested, i.e., searching in parallel the whole space to determine extremal points. A much faster parallelization method for multi-variate polynomials (when appropriate) may be based on the use of parallel automatic differentiation, the (parallel) solution of the resulting ...
3
the protein folding problem seems a good candidate; its a hot area of bio-informatics & already highly parallelized via some apps, (folding@home) and there is a large community holding bi-yearly contests & prizes for solutions see eg CASP. good/effective/accurate solutions are quite scientifically and commerically valuable and some are patented. the ...
Only top voted, non community-wiki answers of a minimum length are eligible
