2 citations · 4 across the 10 of their papers we have counts for
12 papers
Incremental Strongly Connected Components with Predictions
Ronald Deng, Samuel McCauley, Aidin Niaparast +5
Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework…
Incremental Approximate Single-Source Shortest Paths with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +2
The algorithms-with-predictions framework has been used extensively to develop online algorithms with improved beyond-worst-case competitive ratios. Recently, there is growing inte…
Incremental Topological Ordering and Cycle Detection with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +1
This paper leverages the framework of algorithms-with-predictions to design data structures for two fundamental dynamic graph problems: incremental topological ordering and cycle d…
Online List Labeling with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +1
A growing line of work shows how learned predictions can be used to break through worst-case barriers to improve the running time of an algorithm. However, incorporating prediction…
Telescoping Filter: A Practical Adaptive Filter
David J. Lee, Samuel McCauley, Shikha Singh +1
Filters are fast, small and approximate set membership data structures. They are often used to filter out expensive accesses to a remote set S for negative queries (that is, a quer…
The Online Event-Detection Problem
Michael A. Bender, Jonathan W. Berry, Martin Farach-Colton +5
Given a stream , a -heavy hitter is an item that occurs at least times in . The problem of finding heavy-hitters has been extensively stu…
Efficient Rational Proofs with Strong Utility-Gap Guarantees
Jing Chen, Samuel McCauley, Shikha Singh
As modern computing moves towards smaller devices and powerful cloud platforms, more and more computation is being delegated to powerful service providers. Interactive proofs are a…
Bloom Filters, Adaptivity, and the Dictionary Problem
Michael A. Bender, Martin Farach-Colton, Mayank Goswami +3
The Bloom filter---or, more generally, an approximate membership query data structure (AMQ)---maintains a compact, probabilistic representation of a set S of keys from a universe U…
Non-Cooperative Rational Interactive Proofs
Jing Chen, Samuel McCauley, Shikha Singh
Interactive-proof games model the scenario where an honest party interacts with powerful but strategic provers, to elicit from them the correct answer to a computational question.…
Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach
Eric Angel, Nguyen Kim Thang, Shikha Singh
In this paper, we study the -forest problem in the model of resource augmentation. In the -forest problem, given an edge-weighted graph , a parameter , and a set o…
Run Generation Revisited: What Goes Up May or May Not Come Down
Michael A. Bender, Samuel McCauley, Andrew McGregor +2
In this paper, we revisit the classic problem of run generation. Run generation is the first phase of external-memory sorting, where the objective is to scan through the data, reor…
Rational Proofs with Multiple Provers
Jing Chen, Samuel McCauley, Shikha Singh
Interactive proofs (IP) model a world where a verifier delegates computation to an untrustworthy prover, verifying the prover's claims before accepting them. IP protocols have appl…