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?'

Improve this question
$\endgroup$
5
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 13:06
  • $\begingroup$ Here is an example of a problem that seems hard for deterministic algorithms (not an answer to OP's question, but hopefully relevant): Given a satisfiable Boolean formula on $n$ variables, output an assignment that has Hamming distance $n/2 + O(\sqrt n)$ to a satisfying assignment. (This is trivial for a randomized algorithm to do with high probability in poly time.) $\endgroup$
    – Neal Young
    May 14, 2021 at 15:31

5 Answers 5

Reset to default
20
$\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.

Improve this answer
$\endgroup$
5
  • 8
    $\begingroup$ Please don't. The answer is interesting. $\endgroup$
    – Emil Jeřábek
    Mar 24, 2016 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, 2016 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, 2016 at 10:15
  • $\begingroup$ @EmilJeřábek Ok thank you we will leave usul's post as it is here. $\endgroup$
    – user34945
    Mar 24, 2016 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$
    – Turbo
    May 8, 2017 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.

Improve this answer
$\endgroup$
2
  • 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, 2016 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$
    – Turbo
    Sep 4, 2017 at 13:32
13
$\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).

Improve this answer
$\endgroup$
2
  • $\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, 2016 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, 2016 at 1:48
1
$\begingroup$

The Perfect Matching problem was "almost" derandomized in 2016 [1]: there is a deterministic algorithm requiring "only" quaispolynomial resources, namely $n^{\mathcal O(\log n)}$ for the bipartite case and $n^{\mathcal O(\log^2n)}$ for the general case (in 2017 [2]). Although Edmonds gave a polynomial-time algorithm for perfect matching, it is an open question whether there exists an $NC$ algorithm, i.e., a deterministic parallel algorithm using many cores but only $\log^{c}(n)$ time. This result gives an algorithm using only quasipolynomially many cores (or processors, or gates in a uniform circuit).

You can imagine that, after three decades with no improvement in resources over the brute-force parallel algorithm, this result was quite a breakthrough, and has since led to a flurry of new results: the planar case now has a polynomial-time algorithm [4], and shortly thereafter this was extended to graphs of bounded genus. We now know that the decision version is as hard as the search version [5]. There is now a similar derandomization for matroid intersection [3]. For special cases, better results were already known: When a graph contains only a polynomial number of perfect matchings, one of them can be found in polynomial time [6].

The Perfect Matching problem is the special case of the Polynomial Identity Testing where the polynomial is the determinant of a matrix.

[1] Fenner, Stephen, Rohit Gurjar, and Thomas Thierauf. "Bipartite perfect matching is in quasi-NC." Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 2016.

[2] Svensson, Ola, and Jakub Tarnawski. "The matching problem in general graphs is in quasi-NC." 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Ieee, 2017.

[3] Gurjar, Rohit, and Thomas Thierauf. "Linear matroid intersection is in quasi-NC." computational complexity 29.2 (2020): 1-42.

[4] Anari, Nima, and Vijay V. Vazirani. "Planar graph perfect matching is in NC." Journal of the ACM (JACM) 67.4 (2020): 1-34.

[5] Anari, Nima, and Vijay V. Vazirani. "Matching is as easy as the decision problem, in the NC model." arXiv preprint arXiv:1901.10387 (2019).

[6] Agrawal, Manindra, Thanh Minh Hoang, and Thomas Thierauf. "The polynomially bounded perfect matching problem is in NC 2." Annual Symposium on Theoretical Aspects of Computer Science. Springer, Berlin, Heidelberg, 2007.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I’m confused. What do you mean by brute-force exponential algorithm? Isn’t perfect matching in polynomial time by Edmonds’s blossom algorithm? $\endgroup$
    – Emil Jeřábek
    May 14, 2021 at 13:53
  • $\begingroup$ Oh, I seem to have made a mistake. Yes. The "exponential" refers to the amount of work a parallel algorithm must perform. I'll make an edit. Thanks! $\endgroup$
    – Lieuwe Vinkhuijzen
    May 14, 2021 at 13:55
  • $\begingroup$ It should be better now. It has been a while since I read about perfect matchings. Thanks for catching this. $\endgroup$
    – Lieuwe Vinkhuijzen
    May 14, 2021 at 14:01
  • 1
    $\begingroup$ Ah, I see. Thank you for the explanation. $\endgroup$
    – Emil Jeřábek
    May 14, 2021 at 14:02
0
$\begingroup$

Another problem that might be of interest is the Exact Matching Problem: Assume a graph is colored with red and blue edges, find a perfect matching with k red edges. While actually there is a RNC algorithm for this, there is no deterministic algorithm known. However going to Lance's point this problem can actually be reduced to PIT, so may not be as interesting on its own.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The question asks for examples that we do know how to derandomize (at least partially). Your answer seems to be the exact opposite. $\endgroup$
    – Emil Jeřábek
    May 14, 2021 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.