The focus of this monograph is the question of quantified
derandomization. Does derandomization of probabilistic algorithms
become easier if we only want to derandomize algorithms that err
with extremely small probability? How small does this probability
need to be in order for the problem's complexity to be affected? In
this comprehensive survey of the topic, the author describes the
body of knowledge accumulated since the question was first raised
in 2014, focusing on the following directions: 1) Hardness vs
"quantified" randomness; 2) Improving on the brute-force algorithm
for quantified derandomization implies breakthrough circuit lower
bounds; 3) Unconditional algorithms for quantified derandomization
of low-depth circuits and formulas; 4) Arithmetic quantified
derandomization; 5) Limitations of certain black-box techniques and
pseudoentropy. Written for researchers, this monograph provides the
readers with a concise overview of all known results, but the
author also shows several results that are either new or are
strengthenings of others. The author also offers a host of concrete
challenges and open questions surrounding quantified
derandomization.
General
Is the information for this product incomplete, wrong or inappropriate?
Let us know about it.
Does this product have an incorrect or missing image?
Send us a new image.
Is this product missing categories?
Add more categories.
Review This Product
No reviews yet - be the first to create one!
Welcome to Loot.co.za!
Sign in / Register |Wishlists & Gift Vouchers |Help | Advanced search
