56 citations · 84 across the 10 of their papers we have counts for
14 papers
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun, Marco Gaboardi, Max Hopkins +5
The notion of replicable algorithms was introduced in Impagliazzo et al. [STOC '22] to describe randomized algorithms that are stable under the resampling of their inputs. More pre…
Reproducibility in Learning
Russell Impagliazzo, Rex Lei, Toniann Pitassi +1
We introduce the notion of a reproducible algorithm in the context of learning. A reproducible learning algorithm is resilient to variations in its samples -- with high probability…
Boosting in the Presence of Massart Noise
Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane +3
We study the problem of boosting the accuracy of a weak learner in the (distribution-independent) PAC model with Massart noise. In the Massart noise model, the label of each exampl…
On the Power and Limitations of Branch and Cut
Noah Fleming, Mika Göös, Russell Impagliazzo +4
The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simul…
Comparing computational entropies below majority (or: When is the dense model theorem false?)
Russell Impagliazzo, Sam McGuire
Computational pseudorandomness studies the extent to which a random variable looks like the uniform distribution according to a class of tests . Computational ent…
Stabbing Planes
Paul Beame, Noah Fleming, Russell Impagliazzo +4
We develop a new semi-algebraic proof system called Stabbing Planes which formalizes modern branch-and-cut algorithms for integer programming and is in the style of DPLL-based mode…