|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
From expanders to hitting distributions and simulation theoremsстатья
Информация о цитировании статьи получена из
Scopus
Дата последнего поиска статьи во внешних источниках: 20 мая 2019 г.
- Автор: Kozachinskiy Alexander
- Сборник: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
- Серия: Leibniz International Proceedings in Informatics (LIPIcs)
- Том: 117
- Год издания: 2018
- Место издания: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
- Первая страница: 4:1
- Последняя страница: 4:15
- DOI: 10.4230/LIPIcs.MFCS.2018.4
- Аннотация: In this paper we explore hitting distributions, a notion that arose recently in the context of deterministic "query-to-communication" simulation theorems. We show that any expander in which any two distinct vertices have at most one common neighbor can be transformed into a gadget possessing good hitting distributions. We demonstrate that this result is applicable to affine plane expanders and to Lubotzky-Phillips-Sarnak construction of Ramanujan graphs . In particular, from affine plane expanders we extract a gadget achieving the best known trade-off between the arity of outer function and the size of gadget. More specifically, when this gadget has k bits on input, it admits a simulation theorem for all outer function of arity roughly 2^(k/2) or less (the same was also known for k-bit Inner Product). In addition we show that, unlike Inner Product, underlying hitting distributions in our new gadget are "polynomial-time listable" in the sense that their supports can be written down in time 2^O(k), i.e. in time polynomial in size of gadget's matrix. We also obtain two results showing that with current technique no better trade-off between the arity of outer function and the size of gadget can be achieved. Namely, we observe that no gadget can have hitting distributions with significantly better parameters than Inner Product or our new affine plane gadget. We also show that Thickness Lemma, a place which causes restrictions on the arity of outer functions in proofs of simulation theorems, is unimprovable. В этой статье мы исследуем протыкающие распределения, понятие, возникшее недавно в контексте лифтинга от сложности деревьев разрешения к коммуникационной сложности. Мы доказываем, что любой экспандер, в котором любые две различные вершины имеют не более одного общего соседа, может быть преобразован в гаджет с хорошими протыкающими распределениями. Мы показываем, что это ограничение применимо к экспандерам на аффинной плоскости, а также к конструкции Люботского, Филлипса и Сарнака графов Рамануджана. В частности, из экспандеров на аффинной плоскости мы извлекаем гаджет, достигающий наилучшего взаимоотношения между арностью внешней функции и размером гаджета. Более точно, имея на входе k битов, этот гаджет допускает лифтинг для всех внешних функций арности примерно 2^{k/2} или меньше (то же самое было известно для гаджета Скалярное Произведение). Кроме того, мы показываем, что в отличие от Скалярного Произведения, протыкающие распределения нашего нового гаджета <<полиномиально выписываемы>>, то есть их носитель может быть выписан за полиномиальное от размера матрицы гаджета время. Мы также получаем два результат, показывающих, что с текущей техникой улучшить взаимоотношение между арностью внешней функции и размером гаджета невозможно. А именно, мы доказываем, что ни у какого гаджета не может быть протыкающих распределений с лучшими параметрами, чем у нашего гаджета, основанного на аффинной плоскости и у Скалярного произведения. Мы также доказываем, что лемма о толщине, место, которое в доказательствах результатов о лифтинге обусловливает ограничение на арность внешней функции, неулучшаема.
- Добавил в систему: Верещагин Николай Константинович