computational geometry teams

Abstract: We identify explicit closed-form and variational formulae for interpolating the exact values and derivatives through order $s$ of a $C^{s,1}$ function $f:\mathbb{R}^d\to\mathbb{R}$ at $N$ distinct points in $[0,1]^d$. The reconstruction satisfies bounds on its global $C^{s,1}$ seminorm and its Lipschitz constant on $[0,1]^d$ that are independent of the sample size $N$, the latter being the sharp Whitney condition. For $s\ge2$, the reconstruction is real analytic away from the data points and definable in the o-minimal structure $\mathbb{R}_{\exp}$. Our nonlinear extension formula coincides with the formula of McShane (1934) for $s=0$ and with the formulae of Le Gruyer and Phan (2015) and Azagra, Le Gruyer, and Mudarra (2018) for $s=1$, and is new for $s\ge2$. For fixed $d$ and $s\ge2$, our closed-form formula is computable away from the data points by a circuit using only elementary unary and binary real operations, with $\mathcal{O}(N)$ gates and $\mathcal{O}(\log N)$ depth. This yields $\mathcal{O}(N)$ storage and $\mathcal{O}(\log N)$ parallel evaluation time. From the supplied coefficients and weights, the circuit can be compiled with $\mathcal{O}(N)$ one-time work in the exact-real word-RAM model. Thus, in this supplied-data setting, our nonlinear construction improves by a logarithmic factor on the $\mathcal{O}(N\log N)$ initialization bound of Fefferman and Klartag (2009), while retaining linear storage and attaining logarithmic query time through parallel evaluation.

Abstract: Communication complexity studies how much information must be exchanged to solve a problem whose input is split among several parties. The classical setting deals with Boolean inputs split between two parties. We study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. Alice and Bob have inputs $X\in \mathbb{F}^n$ and $Y\in \mathbb{F}^n$, respectively. We consider two kinds of tasks: the polynomial evaluation problem (compute the value of a polynomial $g\in \mathbb{F}[X,Y]$), and the set-recognition problem (decide whether (X,Y) is in $S$, for $S\subseteq \mathbb{F}^{n} \times \mathbb{F}^n$). In both settings, Alice and Bob send evaluations of polynomials depending only on their own inputs. In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or rejection. The protocols may be deterministic or probabilistic. We study: - Upper bounds and reductions: We give non-trivial upper bounds for a range of natural polynomial evaluation and set-recognition problems and prove reductions between different problems, which help organize the landscape of the model. - A lower bound framework and tight lower bounds: Our main technical contribution is a general framework for proving lower bounds for algebraic set-recognition problems. We prove several probabilistic lower bounds for natural problems, giving tight or near-tight characterizations of their algebraic communication. - Applications of the framework: Finally, we give two applications of our framework: proving lower bounds for a class of left-to-right algebraic algorithms (algebraic scanners) and a more general algebraic computational setting inspired by the BSS model.