Questions tagged [dc.parallel-comp]
Theoretical questions in Parallel Computing
99
questions
30
votes
10answers
1k views
Current parallel models for computation
The 1980's gave rise to both the PRAM and the BSP models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s.
Are these areas still active in terms of ...
24
votes
2answers
548 views
Parallel Dynamic Search
Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?
More generally, what's the best we can do ...
21
votes
2answers
929 views
What is the big version of NC?
$\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$...
20
votes
5answers
2k views
Deterministic Parallel algorithm for perfect matching in general graphs?
In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. ...
20
votes
3answers
1k views
Survey on algorithms/complexity of linear algebra
I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with ...
20
votes
6answers
1k views
Parallel pseudorandom number generators
This question is primarily related to a practical software-engineering problem, but I would be curious to hear if theoreticians could provide more insight in it.
Put simply, I have a Monte Carlo ...
19
votes
1answer
833 views
Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?
I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically:
Problem. For a given system of $m$ linear ...
17
votes
2answers
894 views
Status on circuit lower bounds for polylog-bounded depth circuits
Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ ...
14
votes
3answers
927 views
Parallel algorithms for directed st-connectivity
Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors. What is the best known parallel algorithm for directed st-...
14
votes
1answer
794 views
Is there a quantum NC algorithm for computing GCD?
From the comments on one of my questions on MathOverflow
I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer ...
14
votes
1answer
515 views
Problems in NC not known to lie in NC2
Are there interesting problems that are in $\mathsf{NC}$ but not known to be in $\mathsf{NC^{2}}$? In the paper 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook mentions that MIS was known ...
14
votes
0answers
321 views
Linear PRAM vs Arithmetic Linear PRAM
A linear PRAM model is a PRAM model without bit operations and at least one operand of the $\times$ instruction is a constant. If in addition we require that the running time does not depend on the ...
13
votes
2answers
439 views
When a process spawns another process
My background is in complexity theory/logic (where there is just one process most of the time), and in distributed computing (where there are $n$ processes, and one or more might fail over time). ...
13
votes
1answer
474 views
Parallel algorithms for reachability in directed planar graphs
Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors.
What is the best known parallel algorithm for st-connectivity ...
11
votes
3answers
570 views
Is the MapReduce framework a type of BSP?
Is it accurate to call the mapReduce framework a type of bulk synchronous parallel programming framework with no local memory retention within processors between synchronizations? If not, what ...
11
votes
1answer
267 views
To what extent, computational ability for hard tasks helps in solving easy tasks
In short, the question is: to what extent, computational ability for hard tasks really helps you in solving easy tasks. (There could be various ways to make this question interesting and non-trivial, ...
10
votes
3answers
474 views
Which algorithms can be expressed using a total functional language with data parallel operators?
Imagine a functional programming language whose only data types are numerical scalars and arbitrary nestings of arrays. The language lacks any means of unbounded iteration, so the following are ...
10
votes
3answers
341 views
Introductory notes on parallelization, in particular patterns of problems and algorithms
I am looking for online available Lecture notes or other resources that give a good introduction into parallel programming, just like parallel analog of basic classes in computer science.
My focus is ...
10
votes
1answer
354 views
What machine learning classifiers are the most parallelizeable?
What machine learning classifiers are the most parallelizeable? If you had a difficult classification problem, limited time, but a decent LAN of computers to work with, what classifiers would you try?
...
10
votes
1answer
2k views
A practical multi-word compare-and-swap operation
In the paper with the same title as that of this question, the authors describe how to build a nonblocking linearizable multi-word CAS operation using only a single-word CAS. They first introduce the ...
10
votes
1answer
254 views
Is deterministic pseudorandomness possibly stronger than randomness in parallel?
Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a ...
10
votes
0answers
120 views
Problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$
Do we know of any problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$?
Context: based on Josh's answer to this question, it could be possible that all ...
9
votes
6answers
571 views
Reducing complexity with parallelism
Is it possible (slash can you provide an example) to reduce computational complexity of a problem by using a parallel algorithm which does not require a number of processors relative to the input size?...
9
votes
3answers
6k views
Difference between Strict Consistency and Sequential Consistency
I understand strict and sequential consistency independently fairly well.
Strict C basically enforces the actual order in which the instructions ran on the global clock.
Sequential Consistency ...
8
votes
2answers
483 views
Dijkstra parallelization
I'd like to know what is the best method to parallelize the Dijkstra algorithm.
Thanks.
7
votes
1answer
309 views
Parallel algorithms to color interval graphs
Several NP-hard graph problems get easy if we consider interval graphs. There is a greedy algorithm to color optimally an interval graph. Just sort the intervals according their left endpoints and ...
7
votes
2answers
239 views
Are there [good/optimal] parallel comparison sorts?
Comparing each pair of elements and sorting according to
[[number less than] minus [number greater than]] is a parallel comparison
sorting algorithm with a depth of $1$ comparison and $O\left(n^2\...
7
votes
1answer
178 views
Rank-robustness of the parallel complexity of linear algebra problems
It is known that most computational problems related to linear algebra
can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals
or a finite field, we can compute the rank of $A$, ...
7
votes
0answers
132 views
Reference request: reducing rank computations to characteristic polynomials over arbitrary rings
Question. I'm looking into certain algorithms for linear algebra which lie in NC2. Does anyone know of alternative references for the proof of the proposition just below, relating rank of matrices ...
7
votes
0answers
123 views
Deterministic Parallel Algorithm for ILP with small number of variables and small coefficients
Given a set of $n$ linear inequalities in $d$ variables where the coefficients are integers of size bounded by $O(\log{n})$ is there a known deterministic parallel algorithm that runs in time $(d\log{...
6
votes
3answers
291 views
Best algorithm for calculating lists of neighbours
Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted ...
6
votes
2answers
526 views
What algorithm on a PRAM computes the connected components of a graph with least time complexity?
The fastest method to compute the connected components of an undirected graph on a PRAM I have found is O(log n loglog n) in the 1993 paper Finding connected components in O(log n loglog n) time on ...
6
votes
1answer
134 views
Can we do joins in NC?
Suppose we want to join two relations on a predicate. Is this in NC?
I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open ...
6
votes
1answer
512 views
Parallel solution of recurrence equation
One of the most well known parallel algorithms for the solution of recurrence equations is the one proposed by Kogge and Stone (it can be found here). They proved that all recurrence equations of the ...
6
votes
1answer
217 views
Cases of Linear programming known to be in $NC$?
Linear programming is $P$-complete.
However are there special situations where we know an $NC$ algorithm?
5
votes
2answers
188 views
Is there a mathematical analysis/proof available for correctness of solutions to inter process communication problems?
I've been going over some material related to IPC recently from Tanenbaum's "Modern Operating Systems" and revisited semaphore after many years. There is a lot of code and pseudo code based ...
5
votes
1answer
229 views
Qubit gates in google supremacy
The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
5
votes
1answer
343 views
Definition of a hereditary relation
Sassone, V., Nielsen, M. and Winskel, G. (1996) Models for Concurrency: Towards a Classification. Theoretical Computer Science, 170 (1-2). pp. 297-348., p. 307:
Given a tree $S$, define … $\#$ is ...
5
votes
1answer
204 views
Confusion about a formal definition of PRAM consistency
I am reading the paper "Consistency in Non-Transactional Distributed Storage Systems" by Paolo Viotti and Marko Vukolić. The authors provide a comprehensive survey of various consistency semantics ...
5
votes
0answers
147 views
Evidence of non P-hard problems that require polynomial space?
It is admitted that a $\mathsf{P}$-complete problem requires polynomial space and thus cannot be efficiently parallelized. One purpose of these problems is that they can be used to 'defeat' an (...
5
votes
0answers
135 views
What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?
The $\mathsf{P}$-complete problems can be considered "inherently sequential". $\mathsf{P}$-completeness may be defined using either $\mathsf{NC}$ reductions or $\mathsf{L}$ reductions.
Since $\mathsf{...
5
votes
0answers
253 views
When designing an explicitly parallel language, what built in functions should be parallelized? [closed]
As stated by the title. Some examples that I would include would be map and conditionals. What other functions should be built in already parallel for users to expand on it?
5
votes
1answer
127 views
Is black box parallel quantum speedup ever nontrivial?
Grover's algorithm is not parallelizable, in that $p$ quantum processors searching over $n$ elements can't do better than $O(\sqrt{n/p})$ queries.
Are there any oracle problems where quantum ...
4
votes
1answer
391 views
Parallel (NC) replacements for Gaussian elimination?
Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine
its rank, and
a basis for its null-space.
These can be computed easily ...
4
votes
5answers
409 views
Advantages and specific applications of massively parallel programming thesis idea
I'm nearly graduated in computer science engineering and my thesis should discuss the massively parallel computational model of CUDA and its advantages/applications.
I'm searching for an application ...
4
votes
1answer
332 views
Parallel sorting: introduction and state of research
there seem to exist papers on parallel sorting, but I have not found a good introduction into this topic.
So, do you know a good summary or introduction into parallel sorting algorithms? In ...
4
votes
1answer
213 views
Is conversion of PRAM to parameter number of processors trivial
In section 2 of chapter 4 of Kumar the idea of scaling down is discussed.
It is mentioned that the naive method (emulating by assignment) can scale the complexity of the problem more then just "...
4
votes
1answer
530 views
Modern distributed computing book
Lynch's Distributed Algorithms book is a classic but it is from 1996 and rather out of date. Are there any recent distributed computing books that can be used as textbooks for a graduate distributed ...
4
votes
0answers
87 views
Fixed dimension Linear Integer Programming in $NC$
We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
4
votes
0answers
178 views
Randomized Parallel Algorithm for Maximal Independent Set
There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized ...