Till innehåll på sidan

Sagnik Mukhopadhyay: Simulation theorems via pseudo-random properties

Tid: Må 2017-09-25 kl 12.00

Plats: Room 4523, Lindstedtsvägen 5, KTH CSC

Medverkande: Sagnik Mukhopadhyay, Theory Group, KTH

Exportera till kalender

PRACTICALITIES

Lunch is served at 12:00 noon (register at this doodle  at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

ABSTRACT

We generalize the deterministic simulation theorem of Raz and McKenzie [RM99] 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 deterministic simulation theorem for these gadgets, where the gadget 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 and Watson [GPW15].

Our result also implies the previous results for the Indexing gadget, with better parameters than was previously known. Moreover, logarithmic-sized gadget implies a quadratic separation in deterministic communication complexity and logarithm of partition number, no matter how high the partition number is with respect to the input size—something which is not achievable by previous results of [GPW15, AKK16].

This talk will mostly consist of showing the sufficiency of the pseudo-random property and, if time permits, an application of Harper's theorem to prove the simulation theorem for gap-Hamming.

[AKK16] Andris Ambainis, Martins Kokainis, and Robin Kothari. Nearly optimal separations between communication (or query) complexity and partitions. In Proceedings of the 31st CCC, 2016.

[GPW15] Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In Proceedings of the 56th FOCS, 2015.

[RM99] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Combinatorica, 19(3):403–435, 1999.