Лемма Бореля-Кантелли и дерандомизация

11

Я читал статью под названием « Случайные оракулы» с возможностью программирования . Последний абзац раздела 2.3 гласит:

[Используя наш новый подход], нет необходимости применять известные классические асимптотические (и равномерные) методы дерандомизации , основанные на лемме Бореля-Кантелли . Насколько нам известно, этот подход является новым в этой статье.

Я взглянул на статью Википедии по лемме Бореля-Кантелли и почти понял идею. Тем не менее, я до сих пор не могу понять, как это связано с дерандомизацией. Кроме того, я не понимаю значения «асимптотики» и «униформы» в вышеупомянутом абзаце.

PS: поиск в Google для Бореля-Кантелли и дерандомизация покажут несколько интересных результатов, но у меня недостаточно опыта, чтобы хорошо их понять.

cc.complexity-theory derandomization pr.probability measure-theory М.С. Дусти
источник
2
Крошечный комментарий: Использование леммы Бореля-Кантелли в теории сложности, по-видимому, связано с теорией ограниченных ресурсов, введенной Латцем , и некоторыми продолжениями здесь , здесь и здесь . Мне также интересен этот вопрос, надеюсь, у нас будут хорошие ответы!
Сянь-Чи Чанг 之 之
@ Сянь-Chih: Спасибо. Я также видел работы Лутца, но они были слишком сложны для меня :( Я надеюсь, что кто-то описывает это в «терминах непрофессионала»;)
MS Dousti
Я предполагаю, что если ваши случайные события представляют собой что-то вроде строки кода, выполненной на шаге и вы можете применить Борел-Кантелли, то ваша программа всегда завершается. t
Рафаэль

Ответы:

3

Я не думаю, что они имеют в виду дерандомизацию в традиционном смысле. Попробуйте взглянуть на применение леммы BC в этой статье, чтобы найти пример того, о чем они говорят: http://www.cs.bu.edu/~reyzin/hash.html .

Они говорят «асимптотически», потому что большинство разделений BB применимы к таким понятиям, как односторонние функции, которые определяются асимптотически. Их результатом является «конкретная» граница, которая применяется ко всем значениям параметров безопасности, а не только к достаточно большим значениям.

Дэвид Кэш
источник