We introduce a new family of *parallel* time-bounded Kolmogorov complexity measures ($KP^t$).
A string $w$ has low $KP^t$ complexity if any individual bit of $w$ can be decompressed from a "short" description using "few" parallel processors within at most $t$ steps.
The definition of $KP^t$ uses Parallel Random Access Machines (PRAMs) instead of Turing Machines.
Consequently, $KP^t$ is closely related to constant-depth circuit complexity.
By varying the PRAM instruction set, we define a variant of $KP^t$ for each standard constant-depth circuit complexity class: $AC^0$, $AC^0[p]$, $ACC^0$, and $TC^0$.
We show that for each variant, the $KP^t$ complexity of a string is polynomially related to the minimum size of a circuit in the corresponding circuit class that computes the indexing function for the string.
This is directly analogous to the close relationship between the time-bounded Kolmogorov complexity $KT$ and circuit size due to Allender et al. (SIAM J. Comp. 2006).
We show that some recently-discovered connections between time-bounded Kolmogorov complexity, learning theory, and cryptography "scale down" to analogous implications for $KP$.
1. If approximating $KP^t$ is easy on average, then functions computed by constant-depth circuits are learnable from random examples over the uniform distribution. On the other hand, if functions computed by constant-depth circuits are learnable from random examples, then $KP^t$ is easy on average to approximate.
2. If approximating $KP^t$ is hard on average, then constant-depth circuits compute secure pseudorandom functions. On the other hand, if constant-depth circuits compute secure pseudorandom functions, then $KP^{t'}$ is hard on average to approximate for some $t' = O(\log n)$.
Complementing these implications, we observe that the natural proofs of lower bounds against constant-depth circuit complexity classes $AC^0$ and $AC^0[p]$ imply approximation algorithms for the corresponding variants of $KP^t$. This approximation guarantee is insufficient to obtain new learning algorithms for $AC^0[p]$, but does show that $KP^t$ is strictly easier to approximate than standard time-bounded Kolmogorov complexity (under cryptographic assumptions).
