All reports by Author Peter Dixon:

__
TR22-160
| 31st October 2022
__

Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, N. V. Vinodchandran#### The Geometry of Rounding

__
TR21-043
| 15th March 2021
__

Peter Dixon, A. Pavan, N. V. Vinodchandran#### Promise Problems Meet Pseudodeterminism

Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, N. V. Vinodchandran

Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of $\mathbb{R}^d$ are equivalent, we introduce the following natural partition problem which we call the secluded hypercube partition problem: Given $k\in\mathbb{N}$ (ideally small) and $\epsilon>0$ (ideally large), is there a partition of ... more >>>

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 scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high ... more >>>