Suppose n algorithms adaptively choose n pieces of an input (x1,...xn)=X one by one from some predefined distributions, and that Pr[f(X)=1]=p for a (known) Boolean function f. This defines a coin-tossing protocol with coin bias p. Now suppose an adversary A who observes the protocol, as it proceeds, can replace up to k of the inputs. How much can such adversary A increase Pr[f(X)=1] in the two natural settings below. 1.The tampered messages are chosen at random. 2. A can choose the tampered messages at wish. I will survey what is known about the question above, with the focus on (2) while aiming for polynomial-time attacks. I will also briefly mention the connections between the problem above and randomness-tampering attacks on encryption, data poisoning attacks on machine learning algorithms, as well as a new algorithmic approach to measure concentration in product spaces. Based on a sequence of joint works with Omid Etesami (IPM), Ji Gao (UVA), and Saeed Mahloujifar (Princeton) published at TCC'17, ALT'18, ALT'19, ICML'19, SODA'20, TCC'21.
Joining info: https://groups.google.com/g/ipm-math-colloquium