Shikha Singh

PhD Candidate
Computer Science Department
Stony Brook University

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 and game-theoretic study of complexity classes and rationality.

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

Travel, News and Exciting Things

  • [May 2017] I am very excited to be elected President of the Graduate Women in Science and Engineering (GWiSE) at Stony Brook University.
  • [March 2017] I received the 2017 John Marburger III Fellowship for Science, Engineering and Mathematics!
  • [Jan 2017] I will be attending SODA 2017 in Barcelona, Spain.
  • [July 2016] Sam McCauley and I got married twice, first in India and then here in New York!
  • [April 2016] I will be attending LATIN 2016 in Ensenada, Mexico.
  • [Mar 2016] I will be attending and giving a talk at the New Challenges in Scheduling Theory workshop in Aussois, France.
  • [Jan 2016] I will be presenting our paper at ITCS 2016 at Cambridge, Massachusetts and will attend SODA 2016 and a workshop on sunlinear algorithms!
  • [Dec 2016] I will be presenting our paper at ISAAC 2015 in Nagoya, Japan, and visiting Tokyo afterwards!
  • [Oct 2015-Feb 2016] As part of the Chateaubriand Fellowship, I will be in Paris as a visiting researcher at the University of Evry Val d'Essonne.
  • [Sep 2015] I will be giving a talk at MASSIVE, co-located with ALGO in Patras, Greece!
  • [Aug-Oct 2015] I will be visiting the Algorithms and Complexity Group at Max-Planck-Institut Saarbrucken Germany!

    Conference Publications

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

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

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

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

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

    Technical Experience

  • Substitute lecturer for several classes in Steven Skiena's CSE 373 (Analysis of Algorithms).
  • Co-teaching CSE540: Graduate Theory of Computation with Jing Chen, Fall 2014.
  • Intern, Xerox Research Center India, Bangalore, Summer 2014.
  • Teaching Assistant, CSE 373: Analysis of Algorithms, Stony Brook University, Spring 2014.
  • Teaching Assistant, CSE 373: Analysis of Algorithms, Stony Brook University, Fall 2013.
  • Intern, Corporate Applications Team, Yahoo! Bangalore, Summer 2012.
  • CV

    You can find my detailed curriculum vitae here.


    I am sociable and like meeting people and travelling. Besides math, I love the work of Tina Fey (writer and actor), Dylan Moran (comedian), Steven Wilson (musician) and Sarah Kay (poet).


  • A theater enthusiast, I have acted in and directed several plays.
  • I enjoy debating and am one of the founders of the IIT Kharagpur Debating Society.
  • I enjoy blogging: theory/work blog- The Theory Blerg, personal blog- The Silver Lining.
  • Favorite Quotations.
  • People find it hard to believe (given my 5 foot stature) but I do play basketball, when I can.
  • A novice guitarist, I hope I have enough patience someday to be good at it.