Avi Wigderson have a paper on how to derandomize the matrix-valued Chernoff bound. I would like to know whether there exists a simple version of paper on how to derandomize the real-valued Chernoff bound. Thanks so much!

  • 3
    $\begingroup$ In this answer I essentially sketch a derandomization of a typical application of Chernoff + union bound: cstheory.stackexchange.com/a/19380/4896. See also the Chazelle book referenced there, and Section 3.5. in the multiplicative weights survey satyenkale.com/papers/mw-survey.pdf $\endgroup$ – Sasho Nikolov Oct 15 '13 at 19:56
  • $\begingroup$ What is the reference for Wigderson's paper? I doubt your reference is correct (or full). $\endgroup$ – Dilworth Oct 17 '13 at 7:06
  • $\begingroup$ I think it is correct reference. And now I know how to use it to get the result I want. Thanks! $\endgroup$ – user99828 Nov 17 '13 at 2:40
  • $\begingroup$ Here's another worked example (derandomizing a Chernoff-bound based randomized rounding scheme for multicommodity flow): http://greedyalgs.info/blog/intro/multicommodity-flow-slow/ $\endgroup$ – Neal Young Oct 10 '14 at 22:23

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.