Source author record

Caleb Robelle

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Computational Complexity Distributed, Parallel, and Cluster Computing math.AG math.CO math.NT

Catalog footprint

Research overview

3works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Partially Optimal Edge Fault-Tolerant Spanners

Recent work has established that, for every positive integer $k$ , every $n$ -node graph has a $(2k-1)$ -spanner on $O(f^{1-1/k} n^{1+1/k})$ edges that is resilient to $f$ edge or vertex faults. For vertex faults, this bound is tight. However, the case of edge faults is not as well understood: the best known lower bound for general $k$ is $Ω(f^{\frac12 - \frac{1}{2k}} n^{1+1/k} +fn)$ . Our main result is to nearly close this gap with an improved upper bound, thus separating the cases of edge and vertex faults. For odd $k$ , our new upper bound is $O_k(f^{\frac12 - \frac{1}{2k}} n^{1+1/k} + fn)$ , which is tight up to hidden $poly(k)$ factors. For even $k$ , our new upper bound is $O_k(f^{1/2} n^{1+1/k} +fn)$ , which leaves a gap of $poly(k) f^{1/(2k)}$ . Our proof is an analysis of the fault-tolerant greedy algorithm, which requires exponential time, but we also show that there is a polynomial-time algorithm which creates edge fault tolerant spanners that are larger only by factors of $k$ .

preprint2021arXiv

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

Let $k,p\in \mathbb{N}$ with $p$ prime and let $f\in\mathbb{Z}[x_1,x_2]$ be a bivariate polynomial with degree $d$ and all coefficients of absolute value at most $p^k$ . Suppose also that $f$ is variable separated, i.e., $f=g_1+g_2$ for $g_i\in\mathbb{Z}[x_i]$ . We give the first algorithm, with complexity sub-linear in $p$ , to count the number of roots of $f$ over $\mathbb{Z}$ mod $p^k$ for arbitrary $k$ : Our Las Vegas randomized algorithm works in time $(dk\log p)^{O(1)}\sqrt{p}$ , and admits a quantum version for smooth curves working in time $(d\log p)^{O(1)}k$ . Save for some subtleties concerning non-isolated singularities, our techniques generalize to counting roots of polynomials in $\mathbb{Z}[x_1,\ldots,x_n]$ over $\mathbb{Z}$ mod $p^k$ . Our techniques are a first step toward efficient point counting for varieties over Galois rings (which is relevant to error correcting codes over higher-dimensional varieties), and also imply new speed-ups for computing Igusa zeta functions of curves. The latter zeta functions are fundamental in arithmetic geometry.

preprint2020arXiv

Efficient and Simple Algorithms for Fault Tolerant Spanners

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 algorithm to construct this spanner is not polynomial-time, and the best-known polynomial time algorithm is significantly suboptimal. Designing a polynomial-time algorithm to construct (near-)optimal fault-tolerant spanners was given as an explicit open problem in the two most recent papers on fault-tolerant spanners ([Bodwin, Dinitz, Parter, Vassilevka Williams SODA '18] and [Bodwin, Patel PODC '19]). We give a surprisingly simple algorithm which runs in polynomial time and constructs fault-tolerant spanners that are extremely close to optimal (off by only a linear factor in the stretch) by modifying the greedy algorithm to run in polynomial time. To complement this result, we also give simple distributed constructions in both the LOCAL and CONGEST models.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.