[CSDM] [pvsnp-all] Amit Chakrabarti @theory lunch tomorrow

[Mark Braverman]

Location: CS402
Lunch will be served at 11:45. 

TITLE: Certifying Equality with Limited Interaction

ABSTRACT:

The EQUALITY problem---where Alice and Bob must decide if their respective inputs are equal---is usually one's first encounter with communication complexity. Its deterministic and randoemized complexity were settled decades ago, but we find several new things to say by considering two subtle aspects. First, we study the expected communication cost (at a worst-case input) for a protocol that uses limited interaction. Second, we study the information cost of such protocols. We obtain asymptotically optimal rounds-versus-communication and rounds-versus-information tradeoffs for EQUALITY.

As an application of our information cost bounds, we obtain new, and asymptotically optimal, bounded-round randomized lower bounds for OR-EQUALITY and k-DISJOINTNESS (where input sets have size <= k).

Joint work with Joshua Brody (Aarhus) and Ranganath Kondapally (Dartmouth).
_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all