16
$\begingroup$

What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)?

The only example that comes to my mind is AKS deterministic polynomial time primality testing (even for this there was a methodology assuming GRH). So what specific evidence through example do we have for derandomization (again not the hardness or oracle connection)?

Please keep examples to only where time complexity improvement was shown from randomized poly to deterministic poly or something that is very close for specific problems.


Following is more of a comment and I do not know much it will help this query.

Chazelle has a very intriguing statement in http://www.cs.princeton.edu/~chazelle/linernotes.html under 'The Discrepancy Method: Randomness and Complexity (Cambridge University Press, 2000)'.

'It's been an endless source of fascination for me that a deeper understanding of deterministic computation should require the mastery of randomization. I wrote this book to illustrate this powerful connection. From minimum spanning trees to linear programming to Delaunay triangulations, the most efficient algorithms are often derandomizations of probabilistic solutions. The discrepancy method puts the spotlight on one of the most fruitful questions in all of computer science: if you think you need random bits, please tell us why?'

$\endgroup$
  • 2
    $\begingroup$ Lots of algorithms can be derandomized using general techniques like the method of conditional expectations, the method of pessimistic estimators, and using bounded independence sample spaces. In fact, primality testing and polynomial identity testing are so famous because they are rare examples of natural functions that resist standard derandomization techniques. $\endgroup$ – Sasho Nikolov Mar 24 '16 at 5:58
  • 1
    $\begingroup$ @SashoNikolov thank you may be the comment could be expanded as a full answer on some examples. Also is hardness-randomness connection via circuit complexity the only reason people believe $P=BPP$? $\endgroup$ – user34945 Mar 24 '16 at 6:03
  • 1
    $\begingroup$ I think this is a little too basic for an answer. See the chapter on derandomization in Alon-Spencer for details and examples: it covers the three techniques I mentioned. $\endgroup$ – Sasho Nikolov Mar 25 '16 at 1:16
  • $\begingroup$ The interesting thing about the class BPP is that its theoretical definition requires random input bits which can be easily shown, using de-randomization and weak kolomogrov randomness measures, not to exist in finite domains. I don't know how people can live with this inconsistency. I myself don't believe there is an explicit class BPP (it is either NP or P). $\endgroup$ – user42577 Sep 19 '16 at 13:06
19
$\begingroup$

$SL = L$.

$RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace") that $SL = L$, where $S$ stands for "symmetric" and $SL$ is an intermediate class between $RL$ and $L$.

The idea is that you can think of a randomized logspace Turing machine as an polynomial-sized directed graph, where nodes are states of the machine, and an RL algorithm takes a random walk that has good properties. SL corresponds to undirected graphs of this form. Reingold's proof built on work on expander graphs, particularly Reingold, Vadhan, and Wigderson's "zig-zag product", to take any random walk on an undirected graph with good properties and turn it into a psuedorandom walk retaining those properties.

edit this question was posted before the question was explicitly changed to focus exclusively on P vs BPP ... I am leaving it up because it seems to be of interest.

$\endgroup$
  • 8
    $\begingroup$ Please don't. The answer is interesting. $\endgroup$ – Emil Jeřábek Mar 24 '16 at 0:18
  • 1
    $\begingroup$ Hi @Student., I think people coming to the question interested in examples of successful derandomization will be interested in this answer, so I will keep it, without meaning disrespect to your goals (which were only later edited to specify time complexity...) $\endgroup$ – usul Mar 24 '16 at 0:41
  • 2
    $\begingroup$ I should also say that questions and answers on this site are supposed to be formulated so that they are generally useful for future visitors as a form a reference resource, not just to suit the particular goals of the poster. I for one find the question without artificial restrictions to time complexity and BPP much more useful. $\endgroup$ – Emil Jeřábek Mar 24 '16 at 10:15
  • $\begingroup$ @EmilJeřábek Ok thank you we will leave usul's post as it is here. $\endgroup$ – user34945 Mar 24 '16 at 17:20
  • $\begingroup$ @usul 'The idea is that you can think of a randomized logspace Turing machine as an polynomial-sized directed graph'. Is there a suitable intuition that works for NL? I know L is not NL is conjectured but PSPACE=NPSPACE and so space may be different than time. $\endgroup$ – Brout May 8 '17 at 0:33
16
$\begingroup$

There is basically only one interesting problem in BPP not known to be in P: Polynomial Identity Testing, given an algebraic circuit is the polynomial it generates identically zero. Impagliazzo and Kabanets show that PIT in P would imply some circuit lower bounds. So circuit lower bounds are the only reason (but a pretty good one) that we believe P = BPP.

$\endgroup$
  • 4
    $\begingroup$ While I agree with you at a high level, I think that the plethora of randomized algorithms in computational group theory suggest another tightly knit class of interesting derandomization questions, which don't seem to reduce to PIT. While most of these are functions rather than decision problems, some of them can be recast as interesting decision problems in BPP, e.g. cstheory.stackexchange.com/a/11440/129 $\endgroup$ – Joshua Grochow Mar 24 '16 at 19:53
  • $\begingroup$ @JoshuaGrochow Let expected randomized time $O(f(n))$ mean an algorithm on average for all inputs run in $O(f(n))$ time on most advice strings while there are inputs with exponential time on all advice strings (in $BPP$ all inputs have polytime with most advice strings) and so this differs from $BPP$. In number theoretic algorithms like factoring or discrete log $f(n)$ is subexp and all deterministic algorithms are in exp and so there is a subexp randomized speed up. Does $P=BPP$ conjecture get affected if deterministic and expected randomized gap cannot be closed for these algorithms? $\endgroup$ – Brout Sep 4 '17 at 13:32
12
$\begingroup$

Besides polynomial identity testing, one other very important problem known to be in BPP but not in P is approximating the permanent of a non-negative matrix or even the number of perfect matchings in a graph. There is a randomized poly-time algorithm to approximate these numbers within a (1+eps) factor, whereas the best deterministic algorithms achieve only ~ 2^n factor approximations.

While permanent is the main example, there are many approximate counting problems for which there is a huge gap between randomized algorithms (typically based on 'MCMC' methods) and deterministic algoritms.

Another problem in a similar vein is approximating the volume of an explicitly given convex body (say a polyhedron described by a collection of linear inequalities).

$\endgroup$
  • $\begingroup$ One subtlety in P vs BPP, that I wish I could understand better, is the difference between function problems and decision problems. It may be that there are many function problems solvable (in some sense) randomly but not deterministically in polynomial time, yet P=BPP. It seems that your examples probably translate easily to decision problems, is that right? $\endgroup$ – usul Mar 26 '16 at 13:50
  • 1
    $\begingroup$ Decision vs function problems is a little more subtle than in the NP world, but still a lot is known: for example this paper in section 3 gives an example of a "randomized poly time solvable search problem" that is not even decidable. But if the function is one-to-one, then P=BPP implies a "randomized poly time solvable function problem" has a deterministic poly time algorithm (the paper gives many more examples also) $\endgroup$ – Joe Bebel Mar 28 '16 at 1:48

Your Answer

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