Bounds on tradeoffs between randomness and communication complexity (Q687507)

The authors analyze the amount of randomness used in randomized protocols for computing a binary function \(f\), the input of which being split between two parties. For various models of communication complexity, they prove tight lower bounds depending on the number of bits communicated and the deterministic communication complexity of \(f\). The proof techniques are mainly combinatorial in nature.