Jeremy T. FinemanProvost's Distinguished Associate ProfessorWagner Term Chair in Computer Science Department of Computer Science Georgetown University 

Nested ActiveTime Scheduling
by Nairen CAo, Jeremy T. Fineman, Shi Li, Julián Mestre, Katina Russell,
and Seeun William Umboh
Proceedings of the 33rd International Symposium on Algorithms and
Computation (ISAAC)
December, 2022
to appear
Smoothed Analysis of Information Spreading in Dynamic Networks
by Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, and Calvin Newport
Proceedings of the 36th International Symposium on Distributed Computing
October, 2021
to appear
Parallel Shortest Paths with Negative Edge Weights
by Nairen Cao, Jeremy T. Fineman, and Katina Russell
Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
July, 2021
Pages: 177–190
SubLinear Overhead in Static Schedules for FaultTolerant Transmission
December, 2021
Pages: 405–417
Brief Announcement: An Improved Distributed Approximate Single Source
Shortest Paths Algorithm
by Nairen Cao, Jeremy T. Fineman, and Katina Russell
Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC)
July, 2021
Pages: 493–496
Contention Resolution with Message Deadlines
by Kunal Agrawal, Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and
Maxwell Young
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
July, 2020
Pages: 23–35
Optimal Parallel Algorithms in the BinaryForking Model
by Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
July, 2020
Pages: 89–102
Brief Announcement: Improved Work Span Tradeoff for Single Source
Reachability and Approximate Shortest Paths
by Nairen Cao, Jeremy T. Fineman, and Katina Russell
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
July, 2020
Pages: 511–513
Efficient Construction of Directed Hopsets and Parallel Approximate
Shortest Paths
by Nairen Cao, Jeremy T. Fineman, and Katina Russell
Proceedings of the 52nd ACM SIGACT Symposium on Theory of Computing (STOC)
Chicago, IL
June, 2020
Pages: 336–349
Efficient Race Detection with Futures
by Robert Utterback, Kunal Agrawal, Jeremy T. Fineman, and ITing Angelina Lee
Proceedings of the 24th ACM Symposium on Principles and Practice of
Parallel Programming (PPoPP)
Washington, DC
February, 2019
Pages: 340–353
I/OEfficient Algorithms for Topological Sort and Related Problems
by Nairen Cao, Jeremy T. Fineman, Katina Russell, and Eugene Yang
Proceedings of the 30th ACMSIAM Symposium on Discrete Algortihms (SODA)
San Diego, CA
January, 2019
Pages: 2053–2070
Nearly WorkEfficient Parallel Algorithm for Digraph Reachability
by Jeremy T. Fineman
Proceedings of the 50th ACM Symposium on the Theory of Computing (STOC)
Los Angeles, CA
June, 2018
Pages: 457–470
Implicit Decomposition for WriteEfficient Connectivity Algorithms
by Naama BenDavid, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons,
Yan Gu, Charles McGuffey, and Julian Shun
Proceedings of the 32nd IEEE International Parallel and Distributed
Processing Symposium (IPDPS)
Vancouver, Canada
May, 2018
Pages: 711–722
Race Detection and Reachability in Nearly SeriesParallel DAGs
by Kunal Agrawal, Joseph Devietti, Jeremy T. Fineman, ITing Anglina Lee,
Robert Utterback, and Changming Xu
Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA)
New Orleans, LA
January, 2018
Pages: 156–171
The Online House Numbering Problem: MinMax Online List Labeling
by William E. Devanny, Jeremy T. Fineman, Michael T. Goodrich, and Tsvi Kopelowitz
Proceedings of the 25th European Symposium on Algorithms (ESA)
Vienna, Austria
September, 2017
Load Balancing with Bounded Convergence in Dynamic Networks
by Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, and Calvin Newport
Proceedings of the IEEE International Conference on Computer
Communications (INFOCOM)
Atlanta, GA
May. 2017
Pages: 1–9
File Maintenance: When in Doubt, Change the Layout!
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, and
Pablo Montes
Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA)
Barcelona, Spain
January, 2017
Pages: 1503–1522
CrossReferenced Dictionaries and the Limits of Write Optimization
by Peyman Afshani, Michael A. Bender, Martin FarachColton, Jeremy T. Fineman,
Mayank Goswami, and MengTsung Tsai
Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA)
Barcelona, Spain
January, 2017
Pages: 1523–1532
Efficient Algorithms with Asymmetric Read and Write Costs
by Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian
Shun
Proceedings of the 24th European Symposium on Algorithms (ESA)
Aarhus, Denmark
August, 2016
pdf
Contention Resolution on a Fading Channel
by Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, and Calvin Newport
Proceedings of the 35th ACM SIGACTSIGOPS Symposium on Principles of
Distributed Computing (PODC)
Chicago, IL
July, 2016
Pages: 155–164
pdf
Contention Resolution on Multiple Channels with Collision Detection
by Jeremy T. Fineman, Calvin Newport, and Tonghe Wang
Proceedings of the 35th ACM SIGACTSIGOPS Symposium on Principles of
Distributed Computing (PODC)
Chicago, IL
July, 2016
Pages: 175–184
pdf
Parallel Algorithms for Asymmetric ReadWrite Costs
by Naama BenDavid, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons,
Yan Gu, Charles McGuffey, and Julian Shun
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
Asilomar State Beach, CA
July, 2016
Pages: 145–156
pdf
CacheAdaptive Analysis
by Michael A. Bender, Erik D. Demaine, Roozbeh Ebrahimi, Jeremy T. Fineman,
Rob Johnson, Andrea Lincoln, Jayson Lynch, and Samuel McCauely
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
Asilomar State Beach, CA
July, 2016
Pages: 135–144
pdf
Provably Good and Practically Efficient Parallel Race Detection for
ForkJoin Programs
by Robert Utterback, Kunal Agrawal, Jeremy T. Fineman, and ITing Angelina Lee
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
Asilomar State Beach, CA
July, 2016
Pages: 83–94
pdf
How to Scale Exponential Backoff: Constant Throughput, Polylog Access
Attempts, and Robustness
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young
Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA)
Arlington, VA
January, 2016
Pages: 636–654
pdf
Smoothed Analysis of Dynamic Networks
by Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, and Calvin Newport
Proceedings of the 29th International Symposium on Distributed Computing (DISC)
Tokyo, Japan
October, 2015
Pages: 513–527
pdf
Sorting with Asymmetric Read and Write Costs
by Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun
Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
Portland, Oregon
June, 2015
Pages: 1–12
pdf
Scheduling NonUnit Jobs to Minimize Calibrations
by Jeremy T. Fineman and Brendan Sheridan
Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
Portland, Oregon
June, 2015
Pages: 161–170
pdf
CostOblivious Reallocation for Scheduling and Planning
by Michael A. Bender, Martin FarachColton, Sandor P. Fekete, Jeremy
T. Fineman, and Seth Gilbert
Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
Portland, Oregon
June, 2015
Pages: 143–154
pdf
Sequential Random Permutation, List Contraction, and Tree Contraction are
Highly Parallel
by Julian Shun, Yan Gu, Guy E. Blelloch, Jeremy T. Fineman, and Phillip B. Gibbons
Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA)
San Diego, California
January, 2015
Pages: 431–448
pdf
CacheConscious Scheduling of Streaming Pipelines on Parallel Machines with
Private Caches
by Kunal Agrawal, Jeremy T. Fineman, and Jordyn Maglalang
Proceedings of the IEEE International Conference on High Performance
Computing (HiPC)
Goa, India
December, 2014
Pages: 1–12
pdf
CacheOblivious Persistence
by Pooya Davoodi, Jeremy T. Fineman, John Iacono, and Özgür Özkan
Proceedings of the 22nd European Symposium on Algorithms (ESA)
Wrocław, Poland
September, 2014
Pages: 296–308
pdf
Provably Good Scheduling for Parallel Programs that Use Data Structures
through Implicit Batching
by Kunal Agrawal, Jeremy T. Fineman, Kefu Lu, Brendan Sheridan, Jim Sukha, and
Robert Utterback
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
Prague, Czech Republic
June, 2014
Pages: 84–95
pdf
An earlier poster for this work appeared at PPoPP 2014
Experimental Analysis of SpaceBounded Schedulers
by Harsha Vardhan Simhadri, Guy E. Blelloch, Jeremy T. Fineman, Phillip
B. Gibbons, and Aapo Kyrola
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
Prague, Czech Republic
June, 2014
Pages: 30–41
pdf
Brief Announcement: CacheOblivious Scheduling of Streaming
Pipelines
by Kunal Agrawal and Jeremy T. Fineman
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
Prague, Czech Republic
June, 2014
Pages: 79–81
pdf
CostOblivious Storage Reallocation
by Michael A. Bender, Martin FarachColton, Sandor P. Fekete, Jeremy
T. Fineman, and Seth Gilbert
Proceedings of the 33rd ACM SIGMODSIGACTSIGART Symposium on Principles of
Database Systems (PODS)
Snowbird, Utah
June, 2014
Pages: 278–288
pdf
Fair Maximal Independent Sets
by Jeremy T. Fineman, Calvin Newport, Micah Sherr, and Tonghe Wang
Proceedings of the 28th IEEE International Parallel & Distributed
Processing Symposium (IPDPS)
Phoenix, Arizona
May, 2014
Pages: 712–721
pdf
An earlier Brief Announcement for this work appeared at PODC 2013
CacheAdaptive Algorithms
by Michael A. Bender, Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz
Ghasemiesfeh, Rob Johnson, and Samuel McCauley
Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA)
Portland, Oregon
January, 2014
Pages: 958–971
pdf
Reducing Contention Through Priority Updates
by Julian Shun, Guy E. Blelloch, Jeremy T. Fineman, and Phillip
B. Gibbons
Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
Montreal, Canada
July, 2013
Pages: 152–163
pdf
An earlier poster for this work appeared at PPoPP 2013
Reallocation Problems in Scheduling
by Michael A. Bender, Martin FarachColton, Sandor P. Fekete, Jeremy
T. Fineman, and Seth Gilbert
Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
Montreal, Canada
July, 2013
Pages: 271–279
pdf
Greedy Sequential Maximal Independent Set and Matching are Parallel on
Average
by Guy E. Blelloch, Jeremy T. Fineman, and Julian Shun
Proceedings of the TwentyFourth ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)
Pittsburgh, Pennsylvania
June, 2012
Pages: 308–317
pdf
CacheConscious Scheduling of Streaming Applications
by Kunal Agrawal, Jeremy T. Fineman, Jordan Krage, Charles E. Leiserson, and
Sivan Toledo
Proceedings of the TwentyFourth ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)
Pittsburgh, Pennsylvania
June, 2012
Pages: 236–245
pdf
Brief Announcement: The Problem Based Benchmark Suite
by Julian Shun, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Aapo
Kyrola, Harsha Vardhan Simhadri, and Kanat Tangwongsan
Proceedings of the TwentyFourth ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)
Pittsburgh, Pennsylvania
June, 2012
Pages: 68–70
pdf
Internally Deterministic Parallel Algorithms Can Be Fast
by Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Julian
Shun
Proceedings of the 17th ACM Sympoisum on Principles and Practice of
Parallel Programming (PPoPP)
New Orleans, Louisiana
February, 2012
Pages: 181–192
pdf
Race Detectors for Cilk and Cilk++ Programs
by Jeremy T. Fineman and Charles E. Leiserson
a chapter in Encyclopedia of Parallel Computing. David Padua
(Editor), Springer (Publisher), 2011.
Pages: 1706–1719
Scheduling Irregular Parallel Computations on Hierarchical Caches
by Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Harsha
Vardhan Simhadri
Proceedings of the TwentyThird ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA)
San Diego, California
June, 2011
Pages: 355–366
pdf
CacheOblivious Dynamic Dictionaries with Update/Query
Tradeoffs
by Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John
Iacono, Stefan Langerman, and J. Ian Munro
Proceedings of the ACM_SIAM Symposium on Discrete Algorithms
(SODA)
San Francisco, California
January, 2010
Pages: 1448–1456
pdf
Parallel Sparse MatrixVector and MatrixTransposeVector
Multiplication Using Compressed Sparse Blocks
by Aydın Buluç, Jeremy T. Fineman, Matteo Frigo, John
R. Gilbert, and Charles E. Leiserson
Proceedings of the TwentyFirst ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA)
Calgary, Canada
August 11–13, 2009
Pages: 233–244
pdf
A New Approach to Incremental Topological Ordering
by Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert
Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA)
New York, New York
January 4–6, 2009
Pages: 1108–1115
pdf
Improved Approximations for Multiprocessor Scheduling Under
Uncertainty
by Christopher Y. Crutchfield, Zoran Dzunic, Jeremy T. Fineman, David
R. Karger, and Jacob H. Scott
Proceedings of the Twentieth ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA)
Munich, Germany
June 14–16, 2008
Pages: 246–255
pdf
Nested Parallelism in Transactional Memory
by Kunal Agrawal, Jeremy T. Fineman, and Jim Sukha
Proceedings of the 13th ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming (PPoPP)
Salt Lake City, Utah
Pages: 163–174
February 20–23, 2008
pdf
CacheOblivious Streaming BTrees
by Michael A. Bender, Martin FarachColton, Jeremy T. Fineman, Yonatan
Fogel, Bradley Kuszmaul, and Jelani Nelson
Proceedings of the Nineteenth ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA)
San Diego, California
Pages: 81–92
June 9–11, 2007
pdf
The Worst PageReplacement Policy
by Kunal Agrawal, Michael A. Bender, and Jeremy T. Fineman
Proceedings of the Fourth International Conference on Fun With
Algorithms
Castiglioncello (LI), Tuscany, Italy
Pages: 135–145
June 3–5, 2007
pdf
Contention Resolution with Heterogeneous Job Sizes
by Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert
Proceedings of the 14th Annual European Symposium on Algorithms (ESA)
Zürich, Switzerland
Pages: 112–123
September, 2006
pdf
Concurrent CacheOblivious BTrees
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley
C. Kuszmaul
Proceedings of the Seventeenth ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA)
Las Vegas, Nevada
Pages: 228–237
July 17–20, 2005
pdf
OntheFly Maintenance of SeriesParallel Relationships in
ForkJoin Multithreaded Programs
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles
E. Leiserson
Proceedings of the Sixteenth ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA)
Barcelona, Spain
Pages: 133–144
June 27–30, 2004
pdf