License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.4
URN: urn:nbn:de:0030-drops-95863
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9586/
Kozachinskiy, Alexander
From Expanders to Hitting Distributions and Simulation Theorems
Abstract
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.
BibTeX - Entry
@InProceedings{kozachinskiy:LIPIcs:2018:9586,
author = {Alexander Kozachinskiy},
title = {{From Expanders to Hitting Distributions and Simulation Theorems}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {4:1--4:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-086-6},
ISSN = {1868-8969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9586},
URN = {urn:nbn:de:0030-drops-95863},
doi = {10.4230/LIPIcs.MFCS.2018.4},
annote = {Keywords: simulation theorems, hitting distributions, expanders}
}
|
Keywords: |
|
simulation theorems, hitting distributions, expanders |
|
Collection: |
|
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
27.08.2018 |
