Seth Pettie

activity

20242026

collaborators

5 papers

cs.DS2026

Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size

Yaowei Long, Seth Pettie, Thatchaphol Saranurak

For an undirected graph $G = (V, E)$ and a fault bound $f$ , an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pa…

cs.DS2025

Reviving Thorup's Shortcut Conjecture

Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7

We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…

cs.DS2024

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies

Yaowei Long, Seth Pettie, Thatchaphol Saranurak

We consider the problem of assigning short labels to the vertices and edges of a graph $G$ so that given any query $⟨ s, t, F ⟩$ with $∣ F ∣ \leq f$ , we can determine whether…

cs.DS2024

Universal Perfect Samplers for Incremental Streams

Seth Pettie, Dingyu Wang

If $G : R_{+} \to R_{+}$ , the $G$ -moment of a vector $x \in R_{+}^{n}$ is $G (x) = \sum_{v \in [n]} G (x (v))$ and the $G$ -sampling problem i…

math.CO2024

A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices

Seth Pettie, Gábor Tardos

The theory of forbidden 0-1 matrices generalizes Turan-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in…