5 papers
Neighborhood Variants of the KKM Lemma, Lebesgue Covering Theorem, and Sperner's Lemma on the Cube
Jason Vander Woude, Peter Dixon, A. Pavan +2
We establish a "neighborhood" variant of the cubical KKM lemma and the Lebesgue covering theorem and deduce a discretized version which is a "neighborhood" variant of Sperner's lem…
Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma
Jason Vander Woude, Peter Dixon, A. Pavan +2
A partition of is called a -secluded partition if, for every , the ball $\overline{B}_{\infty}(\varepsilon,…
List and Certificate Complexities in Replicable Learning
Peter Dixon, A. Pavan, Jason Vander Woude +1
We investigate replicable learning algorithms. Ideally, we would like to design algorithms that output the same canonical model over multiple runs, even when different runs observe…
Geometry of Rounding
Jason Vander Woude, Peter Dixon, A. Pavan +2
Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of are equivalent, we introduce the followi…
Promise Problems Meet Pseudodeterminism
Peter Dixon, A. Pavan, N. V. Vinodchandran
The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation…