A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
Formalizes the lower bound for the generalized trace reconstruction problem of recovering a string of probabilities from random traces.
A Sharp Version of Talagrand's Selector Process Conjecture and an Application to Rounding Fractional Covers
Formalizes a sharp version of Talagrand's selector process conjecture and its consequence for rounding fractional covers to integral ones.
Approximation Guarantees of the Median Mechanism in ℝᵈ
Formalizes the dimension-independent approximation ratio of the coordinate-wise median mechanism in ℝᵈ.
Efficiently Learning Mixtures of Two Gaussians
Formalizes that the first six moments of a one-dimensional mixture of two Gaussians suffice to robustly recover its parameters.
Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
Formalizes a counterexample refuting the direct sum conjecture for total functions in deterministic communication complexity.