Sample-efficient Replicable Median in Polynomial Time

Replicable algorithm design has emerged as a central notion in algorithmic stability, strengthening both differential privacy and adaptive generalization by requiring that an algorithm, with high probability, produce the same output on independent datasets when run with the same randomness. A central open problem in this area is replicable median estimation, where existing algorithms are either computationally inefficient or require sample complexity exponential in \(\log^* |\chi|\), despite a polynomial information-theoretic lower bound. We resolve this gap by reducing replicable median estimation to the replicable interior point problem, for which we present a polynomial-time algorithm with sample complexity \(\operatorname{poly}(\log^* |\chi|)\). This yields polynomial-time replicable algorithms for median estimation, PAC learning of thresholds, and distribution learning under Kolmogorov distance—addressing open problems of Impagliazzo et al. [STOC’22] in polynomial time and improving prior results of Bun et al. [STOC’23]. Our approach introduces the technique of semi-replicable recursion, which enables recursive algorithms to maintain replicability even when subproblems depend on the data, providing a new framework for efficient replicable algorithm design.