Shikha Singh

PhD Candidate
Computer Science Department
Stony Brook University
Email: shiksingh@cs.stonybrook.edu

About me

I am a PhD candidate at the Department of Computer Science, Stony Brook University. I am co-advised by Michael Bender and Jing Chen. I am interested in the broad area of theoretical computer science; particularly in algorithms and data structures for computing on big data, algorthmic game theory and complexity theory.

Before this, I pursued an Integrated MSc in Mathematics and Computing at the Indian Institute of Technology Kharagpur (2008 - 2013).

Here is a link to my research and teaching statements.

Travel, News and Exciting Things

  • [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!
  • [Dec 2017] I will be attending the Hawaiian Workshop on Parallel Algorithms and Data Structures at University of Hawaii, Manoa, Honolulu.
  • [Sep 2017] I will be visiting Sandia National Laboratories Albuquerque as part of an ongoing research collaboration between the two institutes.
  • [May 2017] I am very excited to be elected President of the Graduate Women in Science and Engineering (GWISE) at Stony Brook University.
  • [Mar 2017] I received the 2017 John Marburger III Fellowship for Science, Engineering and Mathematics!

    Publications

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

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

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

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

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

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

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

    2. Bloom Filters, Adaptivity, and the Dictionary Problem
      M. A. Bender, M. Farach-Colton, M. Goswami, R. Johnson, S. McCauley, and S. Singh. [arXiv]

    Teaching

  • Regular substitute lecturer for Steven Skiena's CSE 373 (Analysis of Algorithms).
  • Instructor for CSE540: Graduate Theory of Computation for several weeks, Fall 2014.
  • Teaching Assistant, CSE 373: Analysis of Algorithms, Stony Brook University, Fall 2013 and Spring 2014. <\li>
  • Teaching Assistant, CSE 540: Graduate Theory of Computation, Fall 2014.

    • Experience

  • Chateaubriand Fellow, University of Evry Val d’Essonne, France, Oct 2015-Feb 2016.
  • Visiting Researcher, Max-Planck-Institute Saarbrucken, Germany Aug–Oct 2015.
  • Intern, Xerox Research Center India, Bangalore, Summer 2014.
  • Intern, Corporate Applications Team, Yahoo! Bangalore, Summer 2012.

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