Приближенные словари: различия между версиями

Результаты, полученные в [ ], имеют интересные связи с вопросами теории кодирования и коммуникационной сложности. В рамках теории кодирования результаты работы [2] можно рассматривать как построение локально декодируемых исходных кодов, аналогичных локально декодируемым канальным кодам из [10]. Теоремы 1-4 также можно рассматривать как жесткие границы для следующей задачи коммуникационной сложности, приведенной в [ ]: Алиса получает u 2 f1... ; mg, Боб получает SC jl;:::; mg размера не более n, и Алиса посылает одно сообщение Бобу, после чего Боб объявляет, выполняется ли u 2 S. Более подробную информацию см. в [ ].