
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 cointossing 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 polynomialtime attacks. I will also briefly mention the connections between the problem above and randomnesstampering 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/ipmmathcolloquium

