Next
Suppose an untrusted powerful data analyst collected many samples from an unknown distribution, and claims that the distribution satisfies some property. For example, that it is close to uniform, or has large support. Can they provide a convincing proof to this effect? If so, what is the complexity of certifying ... more >>>
Two-way codes use communication in both directions to convey a message from a sender to a receiver over a noisy channel. In a beautiful work, [GKZ22] proved that for binary channels with adversarial erasures, interaction strictly outperforms one-way communication: they constructed a two-way code with erasure resilience approaching 3/5, surpassing ... more >>>
It is well-known that if $\mathrm{P} = \mathrm{NP}$, then the seemingly larger class $\mathrm{PH}$ also collapses to $\mathrm{P}$; hence, we may base the hardness of $\mathrm{NP}$ on that of $\mathrm{PH}$, despite the widespread belief that $\mathrm{PH} \not\subseteq \mathrm{NP}$. Although well established in the decision problem setting, few such “conditional collapse ... more >>>