Simulation Theorems via Pseudo-random Properties

• Type: Article in International Scientific Journal
• Date: 2019

Authors

Chattopadhyay, A (Author) Other; Koucky, M (Author) Other; Loff, B (Author) FCUP; Mukhopadhyay, S (Author) Other

Journal

Title: Computational Complexity

Vol. 28

Pages: 617-659

ISSN: 1016-3328

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 4 Citations

Other information

Authenticus ID: P-00Q-WVX

DOI: 10.1007/s00037-019-00190-7

Abstract (EN): We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403-435, 1999), to any gadget which satisfies a certainhitting property. We prove that inner product and gap-Hammingsatisfy this property, and as a corollary, we obtain a deterministic simulationtheorem for these gadgets, where the gadget's input size is logarithmicin the input size of the outer function. This yields the firstdeterministic simulation theorem with a logarithmic gadget size, answeringan open question posed by Goos, Pitassi & Watson (in: Proceedingsof the 56th FOCS, 2015). Our result also implies the previous results for the indexing gadget, withbetter parameters than was previously known. Moreover, a simulationtheorem with logarithmic-sized gadget implies a quadratic separationin the deterministic communication complexity and the logarithm ofthe 1-partition number, no matter how high the 1-partition number iswith respect to the input size-something which is not achievable by previous results of Goos, Pitassi & Watson (2015).

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 43