Communication complexity The model

Matrix Mf has entries Mf [x, y] = f (x, y). A submatrix is monochromatic if f is constant on inputs in the submatrix. A deterministic protocol computing f repeatedly partitions Mf into rectangles (submatrices) until every rectangle is monochromatic. Vickrey auction The 2-player Vickrey auction is defined as f: X × Y → Z where X = Y = [2n], Z = [2n+1] and f (x, y) = (x,B), if x ≤ y (y,A) if y < x Lila (CSC 2429 lecture 10) 1 / 1