In Preparation

  1. Incremental Approximate Single-Source Shortest Paths with Predictions
    Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast and Shikha Singh. [arxiv]

  2. Unbalanced Random Matching Markets with Partial Preferences
    Aditya Potukuchi and Shikha Singh. [arxiv]

    3. Refereed Conference Publications


  3. 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]

  4. 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]

  5. 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]

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

  7. 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]

  8. 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]

  9. 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]

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

  11. 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]

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

  13. 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.

  14. 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]

  15. 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]

  16. 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]

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

  18. 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]

    19. Refereed Journal Publications

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

  20. 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]

  21. 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]

  22. 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