Questions tagged [dc.parallel-comp]

Theoretical questions in Parallel Computing

Filter by
Sorted by
Tagged with
0 votes
0 answers
26 views

Linear modular equalities with $0/1$ solution

Let $Ax\equiv b\bmod q$ be a $n\times n$ modular linear system known to have $0/1$ solution where $q$ is a large prime. We can solve in $NC^2$ for general linear systems using determinant and matrix ...
Turbo's user avatar
  • 12.7k
3 votes
1 answer
246 views

Is modular square roots modulo primes in $NC$?

Assume modulus is prime. Is modular square roots then in $NC$? If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it ...
Turbo's user avatar
  • 12.7k
2 votes
0 answers
71 views

Parallel complexity of fixed dimension fixed constraints integer programming

Papadimitriou in https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf shows ILP is fixed parameter tractable in number of constraints and Lenstra in https://people.csail.mit....
Turbo's user avatar
  • 12.7k
0 votes
0 answers
86 views

Boolean vs algebraic circuits difference

Valiant, Skyum, Berkowitz and Rackoff in https://epubs.siam.org/doi/10.1137/0212043 showed that $VP=VNC^2$, namely, that arithmetic circuits can be parallelized. What is the central reason such a ...
Turbo's user avatar
  • 12.7k
0 votes
0 answers
58 views

Polynomial GCD exact complexity in terms of degree and number of variables

https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials states multivariate polynomial GCDs may be defined over $\mathbb F_p[x_1,x_2,\dots,...
Turbo's user avatar
  • 12.7k
5 votes
1 answer
160 views

$AC^0$[subexp] vs. NC

My question is about the possibility of trading size for depth in circuits. Under what conditions is it true (or, plausible) that $AC^0[2^{n^\delta}] \subseteq NC^i$ for some constants $\delta < 1, ...
zfkmz's user avatar
  • 187
1 vote
0 answers
70 views

Some examples of tools to demonstrate problem is in $NC$ [closed]

Unlike the class $P$ or $NP$ the class $NC$ does not have any complete problems. To show a problem is in $NC$ one needs to marshal efforts to directly show the problem is in $NC$ since there are no ...
Turbo's user avatar
  • 12.7k
5 votes
1 answer
146 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 ...
Geoffrey Irving's user avatar
3 votes
1 answer
138 views

Embarrassingly Parallel: Formal Definition & Citation

I've been unable to find a good answer for this question: Formally, what makes a problem embarrassingly parallel? Intuitively, it would seem to me that an embarrassingly parallel problem is one where: ...
Greenstick's user avatar
1 vote
0 answers
233 views

Fast algorithms for evaluating functions with high Kolmogorov complexity

Motivation: I am motivated by a concrete example that occurs in neuroscience, dendritic computation, which may be approximated by functions computable on binary trees [1]. To be more precise, I ...
Aidan Rocke's user avatar
5 votes
1 answer
236 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 ...
VS.'s user avatar
  • 539
1 vote
0 answers
80 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}$...
xal's user avatar
  • 429
1 vote
0 answers
101 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 ...
Skrodde's user avatar
  • 111
5 votes
1 answer
152 views

Problems which will be in $NC$ if 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$?
Turbo's user avatar
  • 12.7k
1 vote
0 answers
72 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 ...
Turbo's user avatar
  • 12.7k
5 votes
1 answer
233 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 ...
hengxin's user avatar
  • 2,329
3 votes
0 answers
1k 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^{...
Turbo's user avatar
  • 12.7k
3 votes
0 answers
261 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 &...
Turbo's user avatar
  • 12.7k
1 vote
0 answers
146 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$ dimension, $m$ ...
Turbo's user avatar
  • 12.7k
10 votes
0 answers
172 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 ...
xal's user avatar
  • 429
6 votes
1 answer
229 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?
Turbo's user avatar
  • 12.7k
7 votes
1 answer
185 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$, ...
Lior Eldar's user avatar
  • 1,224
2 votes
0 answers
104 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), ...
Turbo's user avatar
  • 12.7k
14 votes
1 answer
627 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 ...
xal's user avatar
  • 429
3 votes
1 answer
165 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,...
Guest Y's user avatar
  • 31
5 votes
1 answer
697 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 ...
Anonymous's user avatar
  • 4,001
11 votes
1 answer
277 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, ...
Gil Kalai's user avatar
  • 6,003
1 vote
1 answer
171 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 ...
user2707299's user avatar
-2 votes
1 answer
203 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 ...
gmr's user avatar
  • 121
1 vote
0 answers
58 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 ...
David Harris's user avatar
  • 3,488
3 votes
0 answers
59 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 ...
Gere's user avatar
  • 147
3 votes
0 answers
179 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 ...
David Harris's user avatar
  • 3,488
2 votes
0 answers
51 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 ...
DatabaseGeek's user avatar
5 votes
2 answers
197 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 ...
vin's user avatar
  • 161
5 votes
0 answers
152 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 (...
Super8's user avatar
  • 314
4 votes
1 answer
458 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 ...
David Harris's user avatar
  • 3,488
2 votes
0 answers
105 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 ...
hengxin's user avatar
  • 2,329
3 votes
0 answers
53 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
Dingo13's user avatar
  • 131
4 votes
1 answer
155 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 ...
Kent's user avatar
  • 169
4 votes
0 answers
183 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 ...
Marc Bury's user avatar
  • 1,338
2 votes
1 answer
2k views

Differences between Quantum Computing and Parallelism [closed]

What are the differences between Quantum Computing and Parallelism? thanks in advance
user17629's user avatar
3 votes
0 answers
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 ...
Javad's user avatar
  • 251
2 votes
2 answers
193 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-...
mrei's user avatar
  • 21
1 vote
1 answer
185 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 ...
Mika H.'s user avatar
  • 113
1 vote
2 answers
548 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 ...
ees_cu's user avatar
  • 168
1 vote
1 answer
185 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 ...
hengxin's user avatar
  • 2,329
0 votes
0 answers
210 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 ...
Ishbir's user avatar
  • 1
15 votes
1 answer
855 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 ...
Turbo's user avatar
  • 12.7k
18 votes
2 answers
1k 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$ ...
shen's user avatar
  • 279
1 vote
2 answers
187 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....
pkmiec's user avatar
  • 111