Caleb Robelle

collaborators

4 papers

cs.DS2021

Partially Optimal Edge Fault-Tolerant Spanners

Greg Bodwin, Michael Dinitz, Caleb Robelle

Recent work has established that, for every positive integer $k$ , every $n$ -node graph has a $(2 k - 1)$ -spanner on $O (f^{1 - 1/ k} n^{1 + 1/ k})$ edges that is resilient to $f$ edge or ver…

math.NT2021

Sub-Linear Point Counting for Variable Separated Curves over Prime Power Rings

Caleb Robelle, J. Maurice Rojas, Yuyu Zhu

Let $k, p \in N$ with $p$ prime and let $f \in Z [x_{1}, x_{2}]$ be a bivariate polynomial with degree $d$ and all coefficients of absolute value at most $p^{k}$ . Suppose als…

cs.DS2020

Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

Greg Bodwin, Michael Dinitz, Caleb Robelle

Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer $k$ , every $n$ -node graph has a $(2 k - 1)$ -spanner on $…

cs.DS2020

Efficient and Simple Algorithms for Fault Tolerant Spanners

Michael Dinitz, Caleb Robelle

It was recently shown that a version of the greedy algorithm gives a construction of fault-tolerant spanners that is size-optimal, at least for vertex faults. However, the algorith…