I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties:
1) Solving the problems in $\cal A$ exactly or even approximately is computationally quite hard as a function of the input size $n$. (What I have especially in mind is that it is P-complete, or as hard as solving linear equations, etc. but examples where approximating $\cal A$ is in another CC class are also welcome.)
2) For a fixed $t$ the algorithms in $P_t$ are computationally easy. (Here I am thinking about bounded depth circuits of various kind, maybe also $NC^1$ or $NC$.)
3) The relation between $t$ and $n$ is such that $P_t$ is a practically good algorithm (at least in some interesting regime for the input) for approximating solutions for problems in $\cal A$. Perhaps even coming close to our best available algorithms for approximating algorithm for the class $\cal A$ in some interesting regime.
So another way to put it: Are there practically good algorithms for approximately solving linear equations, computing determinants, linear programming, etc which are asymptotically in a very low computational complexity class - say bounded-depth computation?
The algorithmic question can be a decision problem, an optimization problem, a sampling problem, or a problem of some other kind. (My motivating example came from a sampling problem.)