Amplification and Derandomization without Slowdown
Amplification and Derandomization without Slowdown
复制标题
DOI：
10.1109/focs.2016.87
复制
发表时间：
2015-09
期刊：
影响因子：
--
通讯作者：
O. Grossman;Dana Moshkovitz
中科院分区：
文献类型：
--
作者：
O. Grossman;Dana Moshkovitz
我们提出了降低随机算法的错误概率和将随机算法转换为确定性（非均匀）算法的技术。与大多数涉及重复随机算法的现有技术不同，我们的技术产生的算法具有与原始随机算法相似的运行时间。放大技术涉及到某随机多臂强盗问题。非随机化技术——这是这项工作的主要贡献——指出了非随机化与草图/稀疏化之间的有趣联系。我们通过展示近似自由博弈（密集二部图上的约束满足问题）的算法来演示该技术。
We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (nonuniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms. The amplification technique is related to a certain stochastic multi-armed bandit problem. The derandomization technique - which is the main contribution of this work - points to an intriguing connection between derandomization and sketching/sparsification. We demonstrate the techniques by showing algorithms for approximating free games (constraint satisfaction problems on dense bipartite graphs).