A. Pavan

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2023

Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma

Jason Vander Woude, Peter Dixon, A. Pavan +2

A partition $P$ of $R^{d}$ is called a $(k, ε)$ -secluded partition if, for every $p \in R^{d}$ , the ball $\overline{B}_{\infty}(\varepsilon,…

cs.CC2010

Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses

Xiaoyang Gu, John M. Hitchcock, A. Pavan

This paper presents the following results on sets that are complete for NP. 1. If there is a problem in NP that requires exponential time at almost all lengths, then every many-one…