10 citations · 10 across the 7 of their papers we have counts for
9 papers
Multiplicative Spanners in Minor-Free Graphs
Greg Bodwin, Gary Hoppenworth, Zihan Tan
In FOCS 2017, Borradaille, Le, and Wulff-Nilsen addressed a long-standing open problem by proving that minor-free graphs have light spanners. Specifically, they proved that every $…
Additive Spanner Lower Bounds with Optimal Inner Graph Structure
Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams +2
We construct -node graphs on which any -size spanner has additive error at least , improving on the previous best lower bound of [Bodwin-Hoppenw…
The Discrepancy of Shortest Paths
Greg Bodwin, Chengyuan Deng, Jie Gao +3
The hereditary discrepancy of a set system is a certain quantitative measure of the pseudorandom properties of the system. Roughly, hereditary discrepancy measures how well one can…
Simple Linear-Size Additive Emulators
Gary Hoppenworth
Given an input graph , an additive emulator is a sparse weighted graph that preserves all distances in with small additive error. A recent line of…
Folklore Sampling is Optimal for Exact Hopsets: Confirming the Barrier
Greg Bodwin, Gary Hoppenworth
For a graph , a -diameter-reducing exact hopset is a small set of additional edges that, when added to , maintains its graph metric but guarantees that all node pairs…
Bridge Girth: A Unifying Notion in Network Design
Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi
A classic 1993 paper by Althőfer et al. proved a tight reduction from spanners, emulators, and distance oracles to the extremal function of high-girth graphs. This paper initia…
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
Greg Bodwin, Gary Hoppenworth
For an input graph , an additive spanner is a sparse subgraph whose shortest paths match those of up to small additive error. We prove two new lower bounds in the area o…
Quantifying Membership Inference Vulnerability via Generalization Gap and Other Model Metrics
Jason W. Bentley, Daniel Gibney, Gary Hoppenworth +1
We demonstrate how a target model's generalization gap leads directly to an effective deterministic black box membership inference attack (MIA). This provides an upper bound on how…
Simple Reductions from Formula-SAT to Pattern Matching on Labeled Graphs and Subtree Isomorphism
Daniel Gibney, Gary Hoppenworth, Sharma V. Thankachan
The CNF formula satisfiability problem (CNF-SAT) has been reduced to many fundamental problems in P to prove tight lower bounds under the Strong Exponential Time Hypothesis (SETH).…