Before revision: History The gap-Hamming problem was originally proposed by Indyk and Woodruff , who initially proved a linear lower bound on the one-way communication complexity of the problem (where Alice is only allowed to receive data from Bob) and conjectured a linear lower bound in the general case.
After revision: in the early 2000'sHistory The gap-Hamming problem was originally proposed by Indyk and Woodruff , who initially proved a linear lower bound on the one-way communication complexity of the problem (where Alice is only allowed to receive data from Bob) and conjectured a linear lower bound in the general case.