Questions tagged [dc.parallel-comp]
Theoretical questions in Parallel Computing
94
questions
1
vote
0answers
57 views
Space complexity of global minimum cut
Are there any non-trivial bounds on the space complexity of global minimum cut? The problem is known to be in $\mathsf{RNC}$. Is anything known about containment in either $\mathsf{L}$ or $\mathsf{NL}$...
1
vote
0answers
94 views
Parallel building time of a k-d tree on n points with n processors
Given a point set with $n$ points to build a k-d tree on. We have $n$ processors available. What is the time-optimal building time for the k-d tree?
A straight forward parallelization would be as ...
4
votes
0answers
81 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$?
1
vote
0answers
66 views
Complexity class of approximating perfect match count
We know we can approximate perfect matching count of bipartite and approximate volume of convex bodies in randomized polynomial time.
Is there any evidence these approximations could be in Nick's ...
5
votes
1answer
179 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 ...
1
vote
0answers
636 views
BQNC and Abelian Hidden Subgroup Problem
We know integer factorization is in $BPP^{BQNC}$ from Cleve and Watrous.
Is Abelian Hidden Subgroup Problem also in $BPP^{BQNC}$?
In particular is Discrete Logarithm in $BQNC$ or at least in $BPP^{...
2
votes
0answers
197 views
Primality in $NC$ hierarchy?
AKS primality testing solves whether a given integer is prime in $P$. AKS algorithm is following:
Input: integer n > 1.
Check if $n$ is a perfect power: if $n = a^b$ for integers $a > 1$ and $b &...
1
vote
0answers
95 views
Fixed dimension Integer programming minus LLL in fixed parameter $NC$?
If you remove LLL part then is remaining part of
a. Lenstra algorithm
b. Barvinok algorithm
in $O(f(n)(\log(mL))^c)$ time on $O(g(n)(mL)^c)$ processors with fixed $c>0$ in fixed $n$...
10
votes
0answers
107 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 ...
6
votes
1answer
186 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?
7
votes
1answer
171 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$, ...
2
votes
0answers
89 views
On analogies between parallel complexity and polynomial time hierarchy structure?
Is it known $\mathsf{RNC=NC\iff P=RP}$ or $\mathsf{BPNC=NC\iff P=BPP}$?
Are there any analogies (such as collapse results, problems which suggest analogies such as gcd(in NC) and factoring (in P), ...
14
votes
1answer
392 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 ...
3
votes
1answer
152 views
Does such model exists?
I have a problem on distributed graph, with the following model:
1. There is a Global Graph $G=(V,E)$
2. There are $k$ computers.
3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the graph,...
4
votes
1answer
373 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 ...
11
votes
1answer
233 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, ...
1
vote
1answer
131 views
Is multiprocessing possible on a Turing Machine? [closed]
I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on ...
-2
votes
1answer
192 views
What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?
For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
1
vote
0answers
54 views
NC algorithm for rank of skinny matrix
Suppose I want to find the rank of an $m \times n$ matrix $A$ over $GF(2)$, where $m \ll n$. The algorithms for rank in the literature seem to be focused on the case when $m = n$, giving a time ...
3
votes
0answers
54 views
Limits of parallel computing with local connections?
There are successes with an increasing numbers of individual computational units in GPUs or as processor cores. Given someone made the effort to build a huge array of processors which - however - can ...
3
votes
0answers
136 views
Algorithm (parallel and serial) for Gram-Schmidt
Suppose we are given $m$ vectors $v_1, \dots, v_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the ...
2
votes
0answers
49 views
Lower bounds in PRAM model for evaluation of straight-line code
Miller, Ramachandran and Kaltofen showed that any straight line program can be executed in parallel time O(log n) using M(n) processors where M(n) is the number of processors for multiplying nxn ...
5
votes
2answers
179 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
0answers
145 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 (...
3
votes
1answer
296 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 ...
2
votes
0answers
97 views
Are the sets of executions of data-race free programs equal, when run on causal memory and on sequentially consistent memory respectively?
In the paper "Causal Memory: Definitions, Implementations, and Programming (Distributed Computing [DC] 1995)", the authors present a formal definition of causal memory, an abstraction of distributed ...
3
votes
0answers
47 views
Best complexity bound for parallel matrix-vector product?
I'm looking for the best known complexity (and a bound for the number of processors invoved) to do the calculation of a $(n,n)$ matrix-vector product.
Thank you
3
votes
1answer
141 views
paradox-driven computers?
Has any research been done on paradox-driven computers?
An example of what I mean by "paradox-driven":
Given a computer which can send information back through time, an algorithm to instantly break ...
4
votes
0answers
170 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 ...
0
votes
1answer
1k views
Differences between Quantum Computing and Parallelism [closed]
What are the differences between Quantum Computing and Parallelism?
thanks in advance
3
votes
0answers
2k views
DAG partitioning for parallel computing
Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these ...
2
votes
2answers
128 views
Multiple independent random number streams
Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in parallel.
In other words, one thread will have a full-...
1
vote
1answer
136 views
Calculation of Recursive Spawning
I'm reading the book Introduction to Algorithms (Cormel et al., 2009) on the chapter about multithreaded algorithms, and I'm confused about the following:
We must also account for the overhead of ...
1
vote
2answers
484 views
Task Multithreading analysis for a Divide and Conquer algorithm
Suppose an algorithm that receive an input array of $n$ elements and it performs a task over each element. All tasks are independent and take $O(k)$ each (being $k$ a variable). Since all tasks are ...
1
vote
1answer
144 views
Should the Schedule of ``High-level Operations'' Respect the Linearizability of ``Low-level Operations'' in Proof of Simulation Algorithm?
Backgroud
I am reading Chapter 10 ``Fault-Tolerant Simulations of Read/Write Objects'' of the Book Distributed Computing (by Hagit Attiya & Jennifer Welch). Specifically, in section 10.2.3, it ...
0
votes
0answers
158 views
Multiple k-selection using GPU
What I am trying to achieve is multiple k-selections (different but small datasets) running in parallel on a GPU. Basically, my aim is to select kth smallest element from an array of floats such that ...
14
votes
1answer
697 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 ...
17
votes
2answers
776 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$ ...
1
vote
2answers
183 views
Classic parallel clustering algorithms
I'm starting a research about parallel clustering. I see a ton of articles on this topic, so that I don't know where to start. I'd like to get familiar with classic methods of parallelizing clustering....
1
vote
0answers
208 views
Big-Theta extension of Brent's Theorem?
Is there an extension or translation of Brent's theorem into asymptotics aside from big-$O$?
Brent's Theorem: source
Running time of a parallel algorithm with $p$ processors (say, $f(n,p)$), $W(n)$ ...
10
votes
1answer
231 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 ...
0
votes
0answers
152 views
Sequential Consistency, cannot find a sufficient explanation
I am having a hard time understanding the SC memory model properly.
The sentence "the result of any execution is the same as if the operations of all the processors were executed in some sequential ...
4
votes
0answers
130 views
What are the parts of consistency model playing in hardware, operating system, and programming language?
In multiprocessor programming, consistency model is the key concept to express the correctness of concurrent objects ranging from simple read/write shared variable to concurrent data structures like ...
1
vote
3answers
697 views
Does mathematical model for conccurent computations exist?
Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time?
If yes, how are the concurrent computations ...
6
votes
1answer
131 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 ...
5
votes
0answers
133 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{...
7
votes
2answers
235 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\...
2
votes
1answer
84 views
Lower bounds on batched query search
I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a ...
3
votes
0answers
227 views
$NC^i \subseteq DSPACE[\log^i{n}]$?
The containment $NC^1 \subseteq DSPACE[\log{n}]$ is simple and well-known (assuming a reasonable notion of uniformity for $NC^1$) and follows by:
start with an $O(\log{n})$-depth polynomial sized ...
4
votes
1answer
212 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 "...
