Исправить . Для любого достаточно большого мы хотели бы пометить все подмножества размера точно натуральными числами из . Нам бы хотелось, чтобы эта маркировка удовлетворяла следующему свойству: есть множество целых чисел, stk≥5k≥5k\ge5nnn{1..n}{1..n}\{1..n\}n/kn/kn/k{1...T}{1...T}\{1...T\}SSS Если...
В статье « О двух проблемах теории информации» Эрдёс и Реньи дают нижние оценки минимального количества взвешиваний, которое необходимо сделать, чтобы определить количество фальшивых монет в наборе из монет.NNn Более формально: Поддельные монеты имеют меньший вес, чем правильные монеты; веса и как...
Неравенство Фано может быть изложено во многих формах, и одна особенно полезная из-за (с незначительной модификацией) Одеда Регева : Пусть XXX - случайная величина, и пусть Y= г( Х)Y=g(X)Y = g(X) где г( ⋅ )g(⋅)g(\cdot) - случайный процесс. Предположим, что существует процедура еff которой Y= г( х...
Я хочу начать изучать сетевое кодирование: http://en.wikipedia.org/wiki/Network_coding Знаете ли вы какой-либо хороший опрос (например, из опросов и учебных пособий IEEE) по вышеуказанным предметам. Я нашел несколько университетских курсов в Google, но я хотел бы получить рекомендации от людей,...
Сообщение связано с: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles Насколько далеко Lovasz связан с пропускной способностью регулярных графов с нулевой ошибкой? Есть ли примеры, когда известно, что оценка Ловаша не равна емкости регулярного графа с...
В настоящее время я ищу предмет для диссертации и столкнулся с областью алгоритмической теории информации. Поле кажется мне очень интересным, но, кажется, все поле было сделано за много лет. Итак, мой вопрос: поле «живое» или оно в значительной степени закрыто? Есть ли у него открытые вопросы?...
Пусть - случайная величина, принимающая значения в (для некоторого большого алфавита ), которая имеет очень высокую энтропию - скажем,для сколь угодно малой постоянной . Пусть - событие в опоре такое что , где \ varepsilon - сколь угодно малая...
Скажем, у нас есть функция е:ZN2→ Rf:Z2n→Rf:\mathbb{Z}_2^n \to \mathbb{R} такой, что ∀ x ∈ZN2е( x ) ∈ {12N,22N, ... ,2N2N} ,∀x∈Z2nf(x)∈{12n,22n,…,2n2n},\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\}, а также еff является...
Предположим, Алиса имеет распределение μμ\muнад конечной (но, возможно, очень большой) областью, такой, что энтропия (Шеннона) ограничена сверху произвольно малой постоянной . Алиса получает значение из , а затем просит Боба (который знает ) угадать .μμ\muεε\varepsilonИксxxμμ\muμμ\muИксxx Какова...
Я хотел выяснить, каковы некоторые применения SGT в области теории информации и кодирования и, возможно, коммуникаций. Самое связанное, что приходит на ум, это работа над кодами расширителей. Майкл Сипсер и Даниэль Спилман, «Коды расширителей», IEEE Transactions по теории информации, том 42, № 6,...
Прошу прощения, это немного "мягкий" вопрос. Теория информации не имеет понятия вычислительной сложности. Например, экземпляр SAT или экземпляр SAT плюс бит, указывающий на выполнимость, несут одинаковое количество информации. Есть ли способ формализовать понятие «полиномиально узнаваемый»? Такая...