Я нашел книгу « Попарная независимость и дерандомизация» по этому вопросу, но она больше ориентирована на исследования, чем на учебники. Я новичок в теме «Дерандомизация», и поэтому я хотел знать, с какой ссылки начать? Я предпочитаю тот, который обсуждает литературу и историю, а также технические...
Насколько мне известно, большинство реализаций генерации псевдослучайных чисел на практике используют такие методы, как регистры обратной связи с линейным сдвигом (LSFR) или эти алгоритмы "Mersenne Twister". Хотя они проходят множество (эвристических) статистических тестов, нет никаких...
Учитывая два дерева AVL и и значение такое что , легко построить новое дерево AVL, содержащее и значения в и за время , где обозначает высоту дерева (до тех пор, пока деревья хранят свою высоту).Т 2 т г ∀ х ∈ T 1 , ∀ у ∈ Т 2 , х < т г < у т т Т 1 Т 2 О ( 1 + | ч ( Т 1 ) - ч ( Т 2 ) | ) ч ( Т...
Каковы некоторые основные примеры успешной дерандомизации или, по крайней мере, прогресса в демонстрации конкретных доказательств достижения цели (а не связи между случайностью и жесткостью)?п= B Pппзнак равноВппP=BPP Единственный пример, который мне приходит в голову, - это тестирование AKS на...
Предположим, что рандомизированный алгоритм использует случайных битов. Наименьшая вероятность ошибки, которую можно ожидать (не имея детерминированного алгоритма с ошибкой 0), составляет 2 - Ω ( r ) . Какие рандомизированные алгоритмы достигают такой минимальной вероятности ошибки?ррr2- Ω ( r...
Существует множество ситуаций, когда рандомизированное «доказательство» намного проще, чем детерминированное доказательство, каноническим примером является проверка полиномиальной идентичности. Вопрос : Существуют ли естественные математические «теоремы», в которых рандомизированное доказательство...
В статье « Рандомизированный анализ ранга-двойственности RANKING для сопоставления двухчастных он- лайн , доказывая, что алгоритм RANKING является -конкурентоспособным, авторы показывают, что двойственное возможно в ожидание (см. лемму 3 на стр. 5). Мой вопрос:( 1 - 1е)(1-1е)\left(1 -...
В хеш-таблицах, которые разрешают коллизии линейным зондированием, для обеспечения ожидаемой производительности необходимо и достаточно, чтобы хеш-функция была из 5-независимого семейства. (Достаточность: «Линейное зондирование с постоянной независимостью», Паг и др. , Необходимость: «О...
Я пересматриваю некоторую криптографическую модель. Чтобы показать его неадекватность, я разработал искусственный протокол, основанный на изоморфизме графа. Это «обычное дело» (еще спорный!) Предположить существование BPP алгоритмов способны генерировать «жесткие экземпляры проблемы Изоморфизма...
В 1978 году Адлеман показал, что BPP⊆P/polyBPP⊆P/poly\mathrm{BPP}\subseteq \mathrm{P/poly} : если булева функция fff из nnn переменных может быть вычислена с помощью вероятностной булевой схемы размера MMM , тогда fff может быть вычислена с помощью детерминированной булевой схемы размера многочлен...
Интересно, что произойдет, если в определении (полиномиальная иерархия, см., Например, здесь ) роль будет заменена на ?PHPHPHNPNPNPRPRPRP Кажется, мы все еще можем построить иерархию, так же, как строится , просто используя везде вместо и вместо . Давайте назовем это рандомизированной...
Достижения в области квантовых вычислений привели к разработке новых классических алгоритмов. Известными недавними примерами являются квантово-вдохновенные алгоритмы для линейной алгебры: Квантово-вдохновленный классический алгоритм для систем рекомендаций Квантово-вдохновленные классические...
Я хотел бы знать ( в связи с этим другой вопрос ) , если нижние оценки были известны следующие задачи тестирования: один получает доступ запроса к последовательности неотрицательных чисел п ≥ ⋯ ≥ 1 и & epsi ; ∈ ( 0 , 1 ) с обещанием, что либо k n k = 1 a k = 1, либо ∑ n k = 1 a k ≤ 1 - ε .aN≥ ⋯...
Я пытаюсь найти распределение по Nnn случайным векторам, скажем, Икс1, … , ХNx1,…,xnx_1,\ldots, x_n , на Кkk мерной единичной сфере (где н > кn>kn > k ), которое минимизирует Максимумя ≠ jV a r ( xTяИксJ)maxi≠jVar(xiTxj)\max_{i\neq j} \mathrm{Var}(x_i^T x_j) при условии ограничения Э [...
Неравенство Фано может быть изложено во многих формах, и одна особенно полезная из-за (с незначительной модификацией) Одеда Регева : Пусть XXX - случайная величина, и пусть Y= г( Х)Y=g(X)Y = g(X) где г( ⋅ )g(⋅)g(\cdot) - случайный процесс. Предположим, что существует процедура еff которой Y= г( х...
Распределенные алгоритмы, которые устойчивы к сбоям, могут быть либо детерминированными, либо вероятностными. Возьмите для примера проблему консенсуса. Paxos является детерминированным в том смысле, что, учитывая допущение, оно всегда работает. В противоположность этому рандомизированный консенсус...
Этот блог рассказывает о создании "извилистых маленьких лабиринтов" с помощью компьютера, перечисляя их. Перечисление может быть выполнено с использованием алгоритма Уилсона для получения UST , но я не помню формулы для того, сколько их там....
BPPBPP\mathsf{BPP} иZPPZPP\mathsf{ZPP} - два основных класса вероятностной сложности. BPPBPP\mathsf{BPP} - это класс языков, определяемых вероятностными алгоритмами Тьюринга за полиномиальное время, где вероятность возврата неправильного ответа ограничена, т. Е. Вероятность ошибки не...
У меня есть 400 шаров, из которых 100 - красные, 40 - желтые, 50 - зеленые, 60 - синие, 70 - фиолетовые, 80 - черные. (шарики одного цвета идентичны) мне нужен эффективный алгоритм перетасовки, чтобы после перетасовки шары были в списке, и Любые 3 последовательных шара не одного цвета. Например, я...
В статье « О двух проблемах теории информации» Эрдёс и Реньи дают нижние оценки минимального количества взвешиваний, которое необходимо сделать, чтобы определить количество фальшивых монет в наборе из монет.NNn Более формально: Поддельные монеты имеют меньший вес, чем правильные монеты; веса и как...