Preprints

  1. Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences
    Samuel McCauley, Benjamin Moseley, Helia Niaparast and Shikha Singh.
    In submission. [arxiv]

    2. Refereed Conference Publications

  2. Incremental Strongly Connected Components with Predictions
    Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh and Nathan Vosburg.
    Scandinavian Symposium on Algorithmic Theory (SWAT 2026)

  3. Incremental Approximate Single-Source Shortest Paths with Predictions
    Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast and Shikha Singh.
    International Colloquium on Automata, Languages and Programming (ICALP 2025) [arxiv]

  4. Unbalanced Random Matching Markets with Partial Preferences
    Aditya Potukuchi and Shikha Singh.
    International Colloquium on Automata, Languages and Programming (ICALP 2025) [arxiv]

  5. Incremental Topological Ordering and Cycle Detection with Predictions
    Samuel McCauley, Benjamin Moseley, Aidin Niaparast and Shikha Singh.
    International Conference on Machine Learning (ICML 2024) [arxiv]

  6. Online List Labeling with Predictions
    Samuel McCauley, Benjamin Moseley, Aidin Niaparast and Shikha Singh.
    Advances in Neural Information Processing Systems (Neurips 2023) [Spotlight Paper]
    [arxiv] [Slides]

  7. Verifiable Crowd Computing: Coping with Bounded Rationality
    Lu Dong, Miguel A. Mosteiro, and Shikha Singh.
    International Joint Conference on Theoretical Computer Science - Frontier of Algorithmic Wisdom (IJTCS-FAW), 2022. [PDF]

  8. Telescoping Filter: A Practical Adaptive Filter
    David Lee, Samuel McCauley, Shikha Singh, and Max Stein.
    European Symposium on Algorithms (ESA), 2021. [arxiv]

  9. Microteaching: Semantics, Definition of a Computer, Running Times, Fractal Trees, Classes as Encapsulation, and P vs NP
    Colleen M. Lewis*, Kathi Fisler, Jenny Hinz, David J. Malan, Joshua E. Paley, Manuel A. Manuel A. Pérez-Quiñones, and Shikha Singh.
    * Non-alphabetical
    Technical Symposium on Computer Science Education (SIGCSE), 2021. [PDF]

  10. A Scheduling Approach to Incremental Maintenance of Datalog Programs
    Shikha Singh*, Sergey Madaminov, Michael Bender, Michael Ferdman, Ryan Johnson,
    * First author (Non-alphabetical)
    Benjamin Moseley, Hung Ngo, Dung Nguyen, Soeren Olesen, Kurt Stirewalt, Geoffrey Washburn.
    International Parallel and Distributed Processing Symposium (IPDPS) (IPDPS), 2020. [PDF]

  11. Timely Reporting of Heavy Hitters using External Memory
    P. Pandey*, S. Singh*, M. A. Bender, J. W. Berry, M. Farach-Colton, R. Johnson, T. Kroeger, C. Phillips.
    * Joint first authors (Non-alphabetical)
    ACM SIGMOD International Conference on Management of Data (SIGMOD), 2020. [arxiv] [Slides]

  12. Non-Cooperative Rational Interactive Proofs
    J. Chen, S. McCauley, and S. Singh
    European Symposium on Algorithms (ESA), 2019. [arXiv] [Slides]

  13. Bloom Filters, Adaptivity, and the Dictionary Problem
    M. A. Bender, M. Farach-Colton, M. Goswami, R. Johnson, S. McCauley, and S. Singh.
    Symposium on Foundations of Computer Science (FOCS) 2018. [arXiv]

  14. Efficient Rational Proofs with Strong Utility-Gap Guarantees.
    J. Chen, S. McCauley, and S. Singh.
    Symposium on Algorithmic Game Theory (SAGT) 2018. [arXiv]

  15. Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach
    E. Angel, K. T. Nguyen, and S. Singh.
    Conference on Combinatorial Optimization and Applications (COCOA) 2017. [PDF]
    Received the Best Paper Runner-Up Award.

  16. Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries.
    M. A. Bender, J. Berry, R. Johnson, T. M. Kroeger, S. McCauley, C. A. Phillips, B. Simon, S. Singh, and D Zage.
    Principles of Database Systems (PODS) 2016. [PDF]

  17. Resource Optimization for Program Committee Members: A Subreview Article.
    M. A. Bender, S. McCauley, B. Simon, S. Singh, and F. Vivien.
    Fun with Algorithms (FUN) 2016. [PDF]

  18. The I/O Complexity of Computing Prime Tables.
    M. A. Bender, R. Chowdhury, A. Conway, M. Farach-Colton, P. Ganapathi, R. Johnson, S. McCauley, B. Simon, and S. Singh.
    Latin American Theoretical Informatics Symposium (LATIN) 2016. [PDF]

  19. Rational Proofs with Multiple Provers.
    J. Chen, S. McCauley, and S. Singh.
    Innovations in Theoretical Computer Science (ITCS) 2016. [arXiv][Slides][Poster]

  20. Run Generation Revisited: What Goes Up May or May Not Come Down.
    M. A. Bender, S. McCauley, A. McGregor, S. Singh, and H. Vu.
    International Symposium on Algorithms and Computation (ISAAC) 2015. [arXiv] [Slides] [Poster]

    21. Refereed Journal Publications

  21. Verifiable Crowd Computing: Coping with Bounded Rationality
    Lu Dong, Miguel A. Mosteiro, and Shikha Singh.
    Theoretical Computer Science (TCS) 2024. [PDF]

  22. Using advanced data structures to enable responsive security monitoring
    J. Vorobyeva*, D. R. Delayo*, M. A. Bender, M. Farach-Colton, P. Pandey, C. A. Phillips, S. Singh, E. D. Thomas, and T. M. Kroeger.
    * Joint first authors (Non-alphabetical)
    Cluster Computing 2022. [Link]

  23. Timely Reporting of Heavy Hitters using External Memory
    S. Singh*, P. Pandey*, M. A. Bender, J. W. Berry, M. Farach-Colton, R. Johnson, T. Kroeger, and C. Phillips.
    * Joint first authors (Non-alphabetical)
    Transactions on Database Systems (TODS) 2021. [Link]

  24. Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach
    E. Angel, K. T. Nguyen, and S. Singh.
    Theoretical Computer Science 2019. [PDF]
    (Special Section on Combinatorial Optimization and Applications Conference)

Back to Home Page