Generalization in adaptive data analysis and holdout reuse
Cynthia Dwork, Toniann Pitassi, et al.
NeurIPS 2015
We show that randomized communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal randomized lower bounds for the Clique versus Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (Göös, Pitassi, and Watson, FOCS'15). One of our main technical contributions states that information complexity when the cost is measured with respect to only 1-inputs (or only 0-inputs) is essentially equivalent to information complexity with respect to all inputs.
Cynthia Dwork, Toniann Pitassi, et al.
NeurIPS 2015
Cynthia Dwork, Vitaly Feldman, et al.
STOC 2015
T. S. Jayram, Jan Vondrák
APPROX/RANDOM 2014
Chandra Chekuri, T. S. Jayram, et al.
ITCS 2015