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.)

  • $\begingroup$ Sounds similar to analogues of the complexity class APX and of the idea of a PTAS, but at a "lower" level, e.g. "PTAS is to NP-hard as [your question] is to P-hard". Is that accurate? $\endgroup$
    – usul
    Nov 3 '14 at 19:10
  • $\begingroup$ It is similar but the crucial difference is that I am interested in cases where approximation is also asymptotically hard and that the "approximation scheme" manifests a practical advantage in some regime. We could ask my question where the algorithmic task is NP-hard: there we want a low complexity level approximation scheme which is practically good (compared to other P-algorithms) in some interesting regime of inputs. $\endgroup$
    – Gil Kalai
    Nov 4 '14 at 5:49
  • 1
    $\begingroup$ Recent analysis of the simplex method for linear programming has shown that, though exponential in the worst case, it is actually polylogarithmic(!) if you make small random perturbations of the constraints. Would this fit what you are looking for? See, for example, math.cmu.edu/~af1p/Teaching/ATIRS/Papers/SMOOTH/simplex.pdf $\endgroup$
    – Nick Alger
    Nov 10 '14 at 8:41
  • 2
    $\begingroup$ Here's an optimization example... maybe. MAX-LIN: given a large (inconsistent) system of linear equations over GF(2), find a solution that maximizes the number of equations satisfied. This problem cannot be approximated with a factor larger than 1/2 unless P=NP, hence even approximately solving is very difficult. Nevertheless, it seems a 1/2-approximation (which is apparently the best possible) can be computed in TC0: a random assignment works, so we can choose poly(n) assignments (hard-coded) and evaluate the linear system on each one, outputting the best. Maybe I'm missing your point. $\endgroup$ Nov 15 '14 at 7:17
  • 1
    $\begingroup$ This may or may not be relevant: arxiv.org/abs/1412.2470 shows how to compute the determinant of a bounded tree width matrix in Logspace by crucially using the version of Courcelle's theorem in Elberfeld et al. (eccc.hpi-web.de/report/2010/062). I suspect that this can be made into #NC^1 by giving a strong representation of the bounded tree width matrix and even TC^0 if the matrix is bounded tree depth matrix and using the version of Courcelle's theorem from eccc.hpi-web.de/report/2011/128 $\endgroup$
    – SamiD
    Dec 12 '14 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.