Speaker: |
Manoj M. Prabhakaran (Indian Institute of Technology Department of Computer Science and Engineering Powai Mumbai 400076) |

Organiser: |
Arkadev Chattopadhyay |

Date: |
Tuesday, 18 Oct 2016, 16:00 to 17:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

The relaxation of IC∞ that yields IC is to change the order of Rényi mutual information used in its definition from ∞ to 1.

The relaxation of IC∞ that yields log prt is to replace protocol transcripts used in the definition of IC∞ with what we term "pseudotranscripts," which omits the interactive nature of a protocol, but only requires that the probability of any transcript given inputs x and y to the two parties, factorizes into two terms which depend on x and y separately.

We also show that if both the above relaxations are simultaneously applied to IC∞, we obtain a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by Kerenidis et al. (FOCS 2012). We obtain a similar (but incomparable) connection between (external) information complexity and relaxed partition complexity as Kerenidis et al., using an arguably more direct proof (this is joint work with Vinod Prabhakaran).