Showing posts tagged communication complexity

Testing Equality in Networks

Yesterday, I went to an interesting talk by Klim Efremenko about testing equality in networks. The talk was based on his joint paper with Noga Alon and Benny Sudakov. The basic problem is as follows. Suppose there is a network with \(k\) nodes, and each node \(v\) has an input in the form of an \(n\)-bit string \(M_v \in \{0, 1\}^n\). All of the nodes in the network want to verify that all of their strings are equal, i.e., that \(M_v = M_u\) for all…

Keep reading

Shorter Certificates for Set Disjointness

Suppose two players, Alice and Bob, each hold equal sized subsets of \([n] = {1, 2, \ldots, n}\). A third party, Carole, wishes to convince Alice and Bob that their subsets are disjoint, i.e., their sets have no elements in common. How efficiently can Carole prove to Alice and Bob that their sets are disjoint? To formalize the situation, suppose \(k\) is an integer with \(1 \leq k \leq n\), and let \(A\) and \(B\) be, respectively, Alice and Bob's subsets of \([n]\), both of size \(k\). Carole produces a…

Keep reading

Introduction to Communication Complexity

I just uploaded an essay “Introduction to Communication Complexity” to my website. The essay is a brief introduction to communication complexity, a field which I find fascinating. The essay is self-contained and completely elementary. It should be accessible to anyone who knows what the words “set,” “function,” and “tree” mean.…

Keep reading