Sign-Rank Can Increase Under Intersection

Speaker: 

Nikhil Mande

Affiliation: 

Georgetown University
Washington, USA

Time: 

Tuesday, 24 September 2019, 16:15 to 17:15

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

Abstract: The communication class UPP^{cc} is a communication analog of the Turing Machine complexity class PP. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds. For a communication problem f, let "f AND f" denote the function that evaluates f on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem f with UPP^{cc}(f) = O(log n), and UPP^{cc}(f AND f) = Theta(log^2 n). This is the first result showing that UPP communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that UPP^{cc}, the class of problems with polylogarithmic-cost UPP communication protocols, is not closed under intersection.  Based on joint work (ICALP'19) with Mark Bun (Boston University) and Justin Thaler (Georgetown University).