2 papers
cs.LG2026
Approximate Replicability in Learning
Max Hopkins, Russell Impagliazzo, Christopher Ye
Replicability, introduced by (Impagliazzo et al. STOC '22), is the notion that algorithms should remain stable under a resampling of their inputs (given access to shared randomness…
cs.CC2024
The Computational Complexity of Factored Graphs
Shreya Gupta, Boyang Huang, Russell Impagliazzo +2
While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might h…