SCIENCE@home

Simulation Theorems via Pseudo-random Properties

A. Chattopadhyay,M. Koucký,B. Loff,Sagnik Mukhopadhyay

Published 2017 in Computational Complexity

ABSTRACT

We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403–435, 1999), to any gadget which satisfies a certain hitting property. We prove that inner product and gap-Hamming satisfy this property, and as a corollary, we obtain a deterministic simulation theorem for these gadgets, where the gadget’s input size is logarithmic in the input size of the outer function. This yields the first deterministic simulation theorem with a logarithmic gadget size, answering an open question posed by Göös, Pitassi & Watson (in: Proceedings of the 56th FOCS, 2015). Our result also implies the previous results for the indexing gadget, with better parameters than was previously known. Moreover, a simulation theorem with logarithmic-sized gadget implies a quadratic separation in the deterministic communication complexity and the logarithm of the 1-partition number, no matter how high the 1-partition number is with respect to the input size—something which is not achievable by previous results of Göös, Pitassi & Watson (2015).

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-67 of 67 references · Page 1 of 1

CITED BY

Showing 1-48 of 48 citing papers · Page 1 of 1