Преобразование Байгеля-Таруи из ACC

14

Я читаю приложение о АССЕ нижних границах для NEXP в Arora и Барак вычислительной сложности книги. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Одна из ключевых лемм - это преобразование из цепей в полилинейные полиномы над целыми числами с полилогарифмической степенью и квазиполиномиальными коэффициентами или эквивалентно , класс цепей S Y M + , который является классом глубинных двух цепей с квазиполиномиальным числом логических элементов И на его нижнем уровне с полилогарифмическим разветвлением и симметричным затвором на верхнем уровне.ACC0SYM+

В приложении к учебнику это преобразование состоит из трех этапов, при условии, что набор ворот состоит из ИЛИ, mod , mod 3 и константы 1 . Первым шагом является уменьшение разветвления вентилей OR до полилогарифмического порядка.231

Использование Валиант-Вазирани Isolation лемму, авторы получаем , что дан логический элемент ИЛИ над входов вида вывода R ( х 1 , . . . , Х 2 K ) , если мы выбираем час быть попарно независимы хэш - функция от [ 2 k ] до { 0 , 1 } , то для любого ненулевого x { 0 , 1 } 2 k с вероятностью не менее 1 / (2kOR(x1,...,x2k)h[2k]{0,1}x{0,1}2k будет иметь место, что Σ i : h ( i ) = 1 x i mod  2 .1/(10k)Σi:h(i)=1ximod 2

Не является ли вероятность , по крайней мере 1 / 2 ? Представляется , что 1 / 10 K является слабой нижней гранью.Σi:h(i)=1ximod 21/21/10k

Второй шаг - переход к арифметическим воротам и опускание умножений вниз. На этом этапе мы преобразуем логические схемы с заданной двоичной входной строкой в ​​арифметическую схему с целочисленным входом.

При этом они отмечают , что заменяется на 1 - х 1 х 2х к и М О Д р ( х 1 , . . . , Х к ) заменяется ( Σ я = 1 , . . . , к й я ) р -OR(x1,...,xk)1x1x2xkMODp(x1,...,xk) с использованием маленькой теоремы Ферма.(Σi=1,...,kxi)p1

Почему эта замена дает эквивалентную цепь ?SYM+

echuly
источник
3
Я не понимаю выражения, которое следует «с вероятностью, по крайней мере, 1 / (10k), оно будет содержать это…». Вы пропускаете знак равенства? Кроме того, не могли бы вы привести номер страницы, где появляется это доказательство?
Робин Котари

Ответы:

10

Разве вероятность не меньше 1/2? Кажется, что 1 / ( 10 k ) является слабой нижней границей.Σi:h(i)=1ximod 2=11/(10k)

На самом деле ответ - нет. (Было бы , что имеет место с вероятностью по крайней мере 1 / 2 - е , если мы работали с й -biased хэш семейством, и , действительно , используя ε -biased хэша Функция дает возможность улучшить параметры построения. Но парная независимость не обязательно ε- смещена.)Σi:h(i)=1ximod 2=11/2εεεε

Кажется, они пропустили еще один шаг здесь. Чтобы применить Valiant-Vazirani напрямую, вам также нужно будет случайным образом выбрать диапазон хэш-функции. Вместо того, чтобы выбирать случайные попарно независимые , кажется, вы должны выбрать случайные { 2 , , k + 1 }, а затем выбрать случайные попарно независимые h : [ 2 k ] { 0 , 1 } h:[2k]{0,1}{2,,k+1}h:[2k]{0,1} . (Здесь я намеренно использую высказывание Арора-Барака о Валиант-Вазирани, найденное на стр. 354.) будет числом x i = 1 . Валиант-Вазирани говорит, что если вы выбрали ℓ так , что 2 - 2s 2 - 1 , то вероятность того, что Σ i : h ( i ) = 1 x i = 1 (по целым числам!), Равна по крайней мере 1 / 8 .sxi=122s21Σi:h(i)=1xi=11/8

h:[2k]{0,1}1/(8k)Σi:h(i)=1ximod 2=1OR2k1/8O(klogs){0,1}O(k)O(logs) hash functions in each set.

Why does this replacement give an equivalent SYM+ circuit ?

A SYM of AND (i.e, SYM+) circuit of size K is essentially equivalent to having a multivariate polynomial h:{0,1}n{0,,K} with at most K monomials, a lookup table g:{0,,K}{0,1}, and computing g(h(x1,,xn)). (For instance, a proof can be found in Beigel-Tarui.) The intuition is that each monomial in f is an AND gate, and g is the SYM gate. I say "essentially equivalent" because the multilinear polynomial h could also have negative coefficients for some terms, and negative coefficents are not obviously implementable in SYM of AND. But I claim (and Beigel and Tarui claim) that this is not a problem. Think about it :)

Ryan Williams
источник