Maciej Li\'skiewicz, Rüdiger Reischuk, Ulrich Wölfel

This paper takes a fresh look at security notions for steganography --

the art of encoding secret messages into unsuspicious covertexts

such that an adversary cannot distinguish the resulting stegotexts from original covertexts.

Stegosystems that fulfill the security notion used so far, however, are quite inefficient.

This ...
more >>>

Ilias Diakonikolas, Daniel Kane, Alistair Stewart

We prove the first {\em Statistical Query lower bounds} for two fundamental high-dimensional learning problems involving Gaussian distributions: (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown mean Gaussian. In particular, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the ... more >>>

Jayadev Acharya, Clement Canonne, Himanshu Tyagi

Independent samples from an unknown probability distribution $\mathbf{p}$ on a domain of size $k$ are distributed across $n$ players, with each player holding one sample. Each player can communicate $\ell$ bits to a central referee in a simultaneous message passing (SMP) model of communication to help the referee infer a ... more >>>