Alice wishes to communicate with Bob, but the malicious jammer James wishes to stop this communication from occurring. What can she do? In this talk I’ll explore recent discoveries/capacity-characterizations in a variety of settings (the role of causality in James’ jamming, the role of myopicity in his observations, the interplay between these two, and the effect of rate-limited feedback). I’ll focus on one of the simplest non-trivial jamming channels—the case of a binary input channel, in which James may erase a constant fraction of transmissions—even here, interesting phenomena occur. Time permitting, I may also briefly describe generalizations to other jamming channels/scenarios.

In this talk, I will present results from a series of works on the power and limitation of data poisoning attacks (mostly in the so-called targeted setting). I will first discuss how to use tools from cryptographic attacks on collective coin flipping to boost an attack's power. I will then discuss methods to provably bound the power of the attacker and achieve tight bounds.

Based on papers from SODA'20, TCC'21, UAI’21, and NeurIPS’22 (with Omid Etesami, Ji Gao, Saeed Mahloujifar, Amin Karbasi, Steve Hanneke, Idan Mehalel, and Shay Moran).

In function inversion, we are given a function from n bits to n bits, and want to prepare some advice of size S, such that we can efficiently invert any image in time T. Function inversion is a central task in cryptography with profound connections to data structures, communication complexity, and circuit lower bounds. In this talk, I will describe recent progress in obtaining tight time-space bounds for function inversion and its related problems.

Succinct arguments allow a prover to convince a verifier that a given statement is true, using an extremely short proof. A major bottleneck that has been the focus of a large body of work is in reducing the overhead incurred by the prover in order to prove correctness of the computation. In the talk I will describe methods which allow one to prove correctness with nearly optimal asymptotic overhead.