MSR Theory Day – Part 3

4:15-4:35 Navin Goyal, MSR-India Title: Algorithms for independent component analysis

Abstract: Independent component analysis is a problem in signal processing. In this problem, we are given linear superposition of independent signals. E.g., we could be receiving data from several sensors but the receiver only gets the sum of these signals. The problem is to recover the original signal from the superposed data. In some situations this turns out to be possible. In this talk I will discuss a provably efficient algorithm for this problem. The algorithm is based on tensor decomposition.

4:40-5:00 Anup Rao, University of Washington Title: Simplified lower bounds for the number-on-forehead complexity of disjointness

Abstract: We show that the deterministic number-on-forehead communication complexity of set disjointness for k parties on a universe of size n is Omega(n/4k). This gives the first lower bound that is linear in n, nearly matching Grolmusz’s upper bound of O(log2 (n) + k2 n/2k). We also simplify Sherstov’s proof showing an Omega(sqrtn/(k2k)) lower bound for the randomized communication complexity of set disjointness. Joint work with Amir Yehudayoff.

Date:
Speakers:
Anup Rao and Navin Goyal
Affiliation:
MSR-India, University of Washington