Явная сбалансированная матрица

20

Можно ли построить явное 0 / 1 -матрица с N 1,5 из них таким образом, что каждый N 0,499 × N 0,499 подматрица содержит менее N 0,501 из них?N×N 0/1N1.5N0.499×N0.499N0.501

Или, возможно, для такого свойства можно построить явный ударный набор.

Легко видеть, что случайная матрица обладает этим свойством с вероятностью, экспоненциально близкой к . Кроме того, лемма о расширении смешивания недостаточна для получения этого свойства.1

Я предполагаю, что псевдослучайные генераторы, которые дурачат комбинаторные прямоугольники, могли бы здесь помочь, но они предназначены для равномерного распределения, и мне здесь нужен .B(N2,N0.5)

ilyaraz
источник
5
Это интересный вопрос: мне интересно, хотя мотивация.
Суреш Венкат
@Suresh Это происходит из-за количественной неэкстрагируемости взаимной информации. Если вам интересно, я могу уточнить.
Ильяраз
Я на самом деле. Вы можете написать мне (sureshv@gmail.com), если так будет проще.
Суреш Венкат

Ответы:

11

То, что вы ищете, это однобитный экстрактор для двух независимых источников: функция , такая, что при условии, что X, Y являются случайными переменными с минимальной энтропией 0,499 * log (N), E (X, Y) почти сбалансирован.E:[N]×[N]{0,1}

Это печально сложная проблема. Для параметров, которые вы хотите, я думаю, что это было решено Bourgain. Смотрите здесь: http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf

Дана Мошковиц
источник
1
Бургейн дает смещение для некоторого α > 0 . Я не уверен , что анализ может дать α = 1 / 2 . На твоем месте я бы изучил это и проверил. Вы также можете спросить Ануп Рао, Зеев Двир, Ави Вигдерсон или любого другого человека, который работал над этой проблемой. p=Nαα>0α=1/2
Дана Мошковиц
7
@ilyaraz: Когда вы (или кто-либо другой) узнаете, дает ли конструкция Бургейна желаемую матрицу или нет, пожалуйста, поделитесь (если не возражаете)!
Цуёси Ито
1
это был очень интересный вопрос и ответ. Я буду второй запрос Цуёси.
Суреш Венкат
2
Перечитывая вопрос и ответ (это было некоторое время назад ...), я думаю, что я не заметил, что спрашивающий хотел только N ^ {1.5}, что соответствует извлечению бита, который равен 1 с вероятностью N ^ {-0.5}, а не сбалансированный бит. Тем не менее, я думаю, что ссылка на экстракторы с двумя источниками полезна. Я могу представить, что подобные методы были бы полезны для постановки вопроса.
Дана Мошковиц
1
1) Если экстрактор выдает k почти одинаковых битов, то, в частности, вы можете получить один бит, который равен 1 с вероятностью ~ 1/2 ^ k. 2) Это довольно расточительно, и для меня это звучит как хороший исследовательский вопрос, чтобы найти более эффективный способ генерирования таких битов.
Дана Мошковиц
2

Этот ответ основан на идее Даны в ее ответе выше.

Я думаю, что вы можете построить такую ​​матрицу, используя конденсаторы с двумя источниками с потерями. Зафиксируйте и скажите N = 2 n . Предположим, что имеется явная функция F ( х , у ) , который принимает любые два независимых случайных источников ( X , Y ) , каждый из которых длины п и имеющих мин-энтропии по крайней мере , к = п ( 1 / 2 - δ ) и выводит последовательность из n = n / 2δ=0.001N=2nf(x,y)(X,Y)nk=n(1/2δ)n=n/2Биты , что является -близко к распределению с мин-энтропии по крайней мере , к ' = п ( 1 / 2 - 3 δ ) . Я думаю, что вы можете использовать стандартные вероятностные аргументы, чтобы показать, что случайная функция удовлетворяет этим свойствам (с подавляющей вероятностью), если 2 k > k + log ( 1 / ϵ ) + O ( 1 ) . По вероятностному аргументу должно быть похоже на то, что используется в следующей статье для конденсаторов без потерь и более общих проводников:ϵk=n(1/23δ)2k>k+log(1/ϵ)+O(1)

М. Капальбо, О. Рейнгольд, С. Вадхан, А. Вигдерсон. Проводники случайности и расширение в постоянных степенях за пределы степени 2

В нашем случае мы полагаем , поэтому мы уверены в существовании нужной нам функции. Теперь аргумент усреднения показывает, что существует n -битная строка z такая, что число ( x , y ) с f ( x , y ) = z составляет не менее 2 1,5 n . Предположим, вы знаете такой z и исправляете его (вы можете выбрать любой произвольный zϵ=2knz(x,y)f(x,y)=z21.5nzzесли вы дополнительно знаете, что ваша функция отображает полностью равномерное распределение на распределение, которое является близко к равномерному). Теперь определите элементы вашей матрицы N × N по возможностям ( x , y ) и поместите 1 в положение ( x , y ), если f ( x , y ) = z . По нашему выбору z , эта матрица имеет не менее 2 1,5 nO(2n/2)N×N(x,y)1(x,y)f(x,y)=zz21.5n из них.

Теперь возьмем любую подматрицу и пусть X , Y будут равномерными распределениями по выбранным строкам и столбцам соответственно. По выбору f мы знаем, что f ( X , Y ) является ϵ- близким к наличию минимальной энтропии k . Поэтому, если мы выберем равномерно случайную запись подматрицы, вероятность наличия 1 будет не более 2 - k + ϵ 2 - k + 12k×2kX,Yff(X,Y)ϵk12k+ϵ2k+1, Это означает, что у вас есть не более единиц в подматрице, по желанию.22kk+1=O(2n/2+δ)

Конечно, создание явного с желаемыми параметрами (в частности, почти оптимальной выходной длиной) является очень сложной задачей, и такой функции пока не известно.f

MCH
источник