Каково смещение случайных многочленов с низкой степенью над GF (2)?

13

У меня есть вопрос, касающийся полиномов и вероятностей низкой степени: какова (асиптотическое поведение) вероятность того, что случайный * полином p по GF (2) со степенью и n переменных имеет .dbias(p)|Prx{0,1}n(p(x)=0)Prx{0,1}n(p(x)=1)|>ϵ

* Когда я пишу случайный многочлен с переменными степени d и n, вы можете думать о каждом одночлене общей степени d выбранном с вероятностью 1/2.

Единственная существенная вещь, которую я знаю, - это вариант Шварца-Циппеля, в котором говорится, что если многочлен непостоянен, то его смещение не превышает 121d . Следовательно, для ϵ=121d probaiblity ровно 1/2(n1)++(nd) , где это вероятность того, что p является постоянная. К сожалению, этот ϵ довольно большой.

Авишай Тал
источник
1
Что такое f в смещении (f)?
Тайсон Уильямс

Ответы:

5

Статья Бен-Элиэзера, Хода и Ловетта "Случайные полиномы низкой степени трудно приблизить" отвечает на ваш вопрос. Они показывают сильные ограничения на корреляцию случайных многочленов степени с многочленами степени не более , анализируя смещение случайных многочленов. См. Их лемму 2: смещение случайного полинома (с точностью до некоторого , линейного по ) не больше , за исключением случая с вероятностью .dd1ddn2Ω(n/d)2Ω((nd))

Дэвид
источник
Привет @ Давид, твой ответ был очень полезным. Я хотел спросить вас кое-что по электронной почте, вы можете отправить мне сообщение?
Авишай Таль
5

Ваш вопрос эквивалентен границам хвостов на распределении весов кодов Рида-Мюллера. Понимание распределения веса кодов Рида-Мюллера является старым и сложным вопросом в теории кодирования, и о нем известно несколько интересных результатов (распределение веса полностью понимается только для и ). В качестве отличной отправной точки см. «Распределение веса и размер декодирования списков кодов Рида-Мюллера» Тали Кауфман, Шахар Ловетт, Эли Порат и ссылки в них.d=1d=2

MCH
источник