Shikha Singh

Assistant Professor of Computer Science
Computer Science Department
Wellesley College
Email: shikha.singh@wellesley.edu

About me

I am an assistant professor of Computer Science at Wellesley College. My research is in the area of theoretical computer science; particularly in algorithms and data structures for computing on big data, algorithmic game theory and complexity theory.

In June 2018, I obtained my PhD from Stony Brook University where I was co-advised by Michael Bender and Jing Chen.

Travel, News and Exciting Things

  • [July 2018] Our paper on adaptive Bloom filters got accepted to FOCS 2018!
  • [June 2018] I defended my PhD dissertation on The Mechanism Design Approach to Interactive Proofs.
  • [Feb 2018] I will be joining the Computer Science Department at Wellesley College as an Assistant Professor in July 2018!
  • [Feb 2018] Stony Brook CS department did a student focused article on me and my work, check it out!
  • [Dec 2017] Our paper on approximating k-forest received the Best Paper Runner-Up Award at COCOA 2017!

    Publications

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

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

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

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

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

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

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

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

    In Preparation

    1. Rational Proofs with Non-Cooperative Provers
      J. Chen, S. McCauley, and S. Singh. [arXiv]

    Teaching

  • CS235: Languages and Automata, Fall 2018.

    • CV

    You can find my detailed curriculum vitae here.

    Miscellaneous

  • My husband Sam McCauley also does computer science.
  • I love meeting new people, forming new collaborations, and travelling.
  • I love the work of Tina Fey, Samantha Bee, and Sarah Kay.
  • In undergrad, I used to be a theater enthusiast, debator and blogger.
  • In graduate school, I mostly spend my free time reading, writing and doing yoga.
  • Here is a list of my favorite quotes.