Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Internal Diffusion-Limited Aggregation: Parallel Algorithms and
  Complexity   The computational complexity of internal diffusion-limited aggregation (DLA)
is examined from both a theoretical and a practical point of view. We show that
for two or more dimensions, the problem of predicting the cluster from a given
set of paths is complete for the complexity class CC, the subset of P
characterized by circuits composed of comparator gates. CC-completeness is
believed to imply that, in the worst case, growing a cluster of size n requires
polynomial time in n even on a parallel computer.
  A parallel relaxation algorithm is presented that uses the fact that clusters
are nearly spherical to guess the cluster from a given set of paths, and then
corrects defects in the guessed cluster through a non-local annihilation
process. The parallel running time of the relaxation algorithm for
two-dimensional internal DLA is studied by simulating it on a serial computer.
The numerical results are compatible with a running time that is either
polylogarithmic in n or a small power of n. Thus the computational resources
needed to grow large clusters are significantly less on average than the
worst-case analysis would suggest.
  For a parallel machine with k processors, we show that random clusters in d
dimensions can be generated in O((n/k + log k) n^{2/d}) steps. This is a
significant speedup over explicit sequential simulation, which takes
O(n^{1+2/d}) time on average.
  Finally, we show that in one dimension internal DLA can be predicted in O(log
n) parallel time, and so is in the complexity class NC.

32
The categories of this paper are: atom-ph
9
The categories of this paper are: nlin
20
The categories of this paper are: acc-phys
8
The categories of this paper are: hep-ex
24
The categories of this paper are: dg-ga
11
The categories of this paper are: hep-lat
28
The categories of this paper are: alg-geom
15
The categories of this paper are: nucl-ex
2
The categories of this paper are: math
33
The categories of this paper are: plasm-ph
29
The categories of this paper are: funct-an
12
The categories of this paper are: nucl-th
3
The categories of this paper are: physics
1
The categories of this paper are: cs
17
The categories of this paper are: q-fin
21
The categories of this paper are: adap-org