Showing posts tagged probabilistic method

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