11 citations · 16 across the 14 of their papers we have counts for
4 papers · 1 filter
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…
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
Greg Bodwin, Forest Zhang
In competitive games, it is common to assign each player a real number rating signifying their skill level. A rating system is a procedure by which player ratings are adjusted upwa…
Epic Fail: Emulators can tolerate polynomially many edge faults for free
Greg Bodwin, Michael Dinitz, Yasamin Nazari
A -emulator of a graph is a graph that approximates its pairwise shortest path distances up to multiplicative error. We study fault tolerant -emulators, under the…
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…