Research by Topics (Selected Publications)

[Author lists ending with (*) are presented alphabetically as is customary in theoretical computer science. For a chronological list of my publications, please refer to my Google Scholar page.] 

Systems Theory

Data Structures:

• Rathish Das and William Kuszmaul (*). “History-Independent Maximal Matchings Can be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees.” Proceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pages 3999-4022, 2026. [PDF].

• Tianchi Mo, Michael A. Bender, Rathish Das, Martín Farach-Colton, and David Tench, “Mitigating false positives in filters: to adapt or to cache?'' ACM Transactions on Database Systems (TODS), 2025. [PDF]. 

• Rathish Das, John Iacono, and Yakov Nekrich (*). “External-memory dictionaries with worst-case update cost.” Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC), Pages 21:1-21:13, 2022. [PDF].

• Michael A. Bender, Rathish Das, Rob Johnson, Martín Farach-Colton, and William Kuszmaul (*). “Flushing without Cascades.” Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pages 650-669, 2020. [PDF]. 

Caching / Paging:

• Michael A. Bender, Rathish Das, Martin Farach-Colton, and Guido Tagliavini (*), “An Associativity Threshold Phenomenon in Set-Associative Caches.” Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages 117-127, 2023. [PDF]. 

• Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato (*). “Online Parallel Paging with Optimal Makespan.” Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages 205-216, 2022. [PDF]. Outstanding paper award winner (Best paper finalist). 

• Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato (*). “Tight Bounds of Parallel Paging and Green Paging.” Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pages 3022-3041, 2021. [PDF], [Video talk]. 

• Rathish Das, Kunal Agrawal, Michael Bender, Jonathan Berry, Benjamin Moseley, and Cynthia Phillips. “How to Manage High-Bandwidth Memory Automatically.'' Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages 187-199, 2020. [PDF].

Resource Scheduling:

• Rathish Das and Hao Sun (*), “Approximation Hardness of Resource Scheduling.” Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages 46-61, 2025. [PDF]. Invited to ACM Transactions on Parallel Computing (TOPC), special issue for SPAA. 

• Rathish Das, Shih-Yu Tsai, Sharmila Duppala, Jayson Lynch, Esther Arkin, Rezaul Chowdhury, Joseph Mitchell, and Steven Skiena, “Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths,'' Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages 359--368, 2019. [PDF].

Parallel Algorithms: 

• Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Mohammad Mahdi Javanmard (*). “Low-Depth Parallel Algorithms for the Binary-Forking Model.” Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages 22-34, 2021. [PDF], [Video talk]. Outstanding paper award winner (Best paper finalist). 

Computational {Sciences, Geometry, Economics}

• Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Yimin Zhu (*). “Speeding up Stencil Computation using Gaussian Approximations.” Proceedings of the SIAM conference on Applied and Computational Discrete Algorithms (ACDA), Pages 276-292, 2025. [PDF].

• Rathish Das, Omrit Filtser, Matya Katz, and Joseph S.B. Mitchell (*), “Robustly Guarding Polygons.” Proceedings of the 40th International Symposium on Computational Geometry (SoCG), Pages 47:1-47:17, 2024. [PDF]. Invited to Journal of Computational Geometry (JoCG), special issue for SoCG. [PDF].

• Zafar Ahmad, Reilly Browne, Rezaul Chowdhury, Rathish Das, Yushen Huang, and Yimin Zhu (*),  “Fast American Option Pricing using Nonlinear Stencils.” Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP), Pages 316-312, 2024. [PDF].

• Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Yimin Zhu (*). “Fast Stencil Computations using Fast Fourier Transforms.” Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages 8-21, 2021. [PDF]. Outstanding paper award winner (Best paper finalist). 

• Esther Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph Mitchell, Valentin Polishchuk, and Csaba D. Toth (*), “Cutting Polygons into Small Pieces with Chords: Laser-Based Localization.'' Proceedings of the 28th Annual European Symposium on Algorithms (ESA-Track A), Pages 7:1-7:23, 2020. [PDF].

Learning Theory

• Gerdus Benade, Rathish Das, and Thomas Lavastida (*), “Offline Local Search for Online Stochastic Bandits.” Proceedings of the ACM SIGMETRICS, 2026. [PDF]

• Gerdus Benade, Rathish Das, and Thomas Lavastida (*), “Brief Announcement: Stochastic Parallel Scheduling with Bandit Feedback.” Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025. [PDF]. 

• Arghya Bhattacharya and Rathish Das (*), ``Machine Learning Advised Ski Rental Problem with a Discount.'' Theoretical Computer Science (TCS). [PDF]