DisCoMath Seminar: On the Instance Complexity of Set Intersection

DisCoMath Seminar
On the Instance Complexity of Set Intersection
Dr. Varsha Dani
Department of Computer Science
Rochester Institute of Technology
Register for Zoom Here
Abstract:
Typically, when analyzing algorithmic performance, we focus on worst-case complexity, where the goal is to optimize a time complexity function π(π), defined as the maximum running time over all inputs of length π. In Instance Complexity, however, one seeks a much more fine-grained notion of optimality, where the time complexity function π(π₯) is defined over all input strings, π₯. An algorithm is said to have optimal instance complexity, if, for every possible input, its running time is the best possible for that input. Surprisingly, there are some settings in which it is possible to design nearly optimal algorithms, even with this much more refined notion of optimality.
Motivated by the problem of Join Queries in Distributed Databases, we study the following version of the Set Intersection problem in communication complexity. Each of π players is given a subset of a universe {1,2,β¦,π}. After a communication protocol, every player should know the intersection of all π sets. We give a nearly instance-optimal algorithm for this problem under some fairly natural restrictions to the type of algorithm that is allowed. The key idea comes from the answer to a popular math riddle known as a "rope-burning puzzle".
Joint work with Tom Hayes and Atri Rudra, both at University at Buffalo.
Intended Audience:
All are Welcome!
To request an interpreter, please visit myaccess.rit.edu
Event Snapshot
When and Where
Who
This is an RIT Only Event
Interpreter Requested?
No