Shikha Singh

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

About me

I am a third year 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. I also work on 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

  • [April 11-15] I will be attending LATIN 2016 in Ensenada, Mexico.
  • [Mar 29 - Apr 2] I will be attending and giving a talk at the New Challenges in Scheduling Theory workshop in Aussois, France.
  • [January 14-16] I will be presenting our paper at ITCS 2016 at Cambridge, Massachusetts and will attend SODA 2016 and a workshop on sunlinear algorithms before it!
  • [December 8-13] I will be presenting our paper at ISAAC 2015 in Nagoya, Japan, and visiting Tokyo afterwards!
  • [Oct 22, 2015 - Feb 22, 2016] As part of the Chateaubriand Fellowship, I will be in Paris as a visiting researcher at the University of Evry Val d'Essonne.
  • [September 14 - 19, 2015] I will be giving a talk at MASSIVE, co-located with ALGO in Patras, Greece!
  • [August 9 - October 9, 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. To appear.

    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. To appear. .

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

    Work in Progress

  • Improved approximation for k-Median using Primal-Dual.
    S. Singh and N. K. Thang.

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

    Miscellaneous

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

    Interests

  • 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 feet stature) but I do play basketball, when I can.
  • A novice guitarist, I hope I have enough patience someday to be good at it.