Shiva Kintali

PhD Candidate
College of Computing
Georgia Institute of Technology

Contact : Click Here


Links :       Compendium of PPAD-complete Problems       FOCS 2009 pdf files       ICS 2010 pdf files

My Blogs :       My Brain is Open       Graph Theory

Hobbies :       Paintings       Biking

Personal :       Photo Album       twitter.com/kintali

About Me

I am a PhD student in the theory group at College of Computing, Georgia Institute of Technology. My PhD advisor is Prof. Richard J. Lipton I did my B-Tech in CSE from Indian Institute of Technology (IIT) Kharagpur and Masters from USC. My hometown is the city of Visakhapatnam in Andhra Pradesh, India. I worked for five years (in Oracle Inc. and Synopsys Inc.) in the area of Parsing algorithms, Programming languages and Compiler optimizations before starting Masters at USC.

Research Interests

  • Computational Complexity, Circuit Complexity, Communication Complexity, Derandomization, Lower Bounds.
  • I am especially interested in studying the complexity classes related to logspace, LogCFL and PPAD classes.
  • Algorithmic Game Theory, Polyhedral Combinatorics (with focus on complexity issues).
  • Hardness of Approximation, Approximation Algorithms, Graph Theory.
    		•
    Selected Publications   ( full list , DBLP )
    • Shiva Kintali,  Laura J. Poplawski,  Rajmohan Rajaraman,  Ravi Sundaram,  Shang-Hua Teng
      Reducibility Among Fractional Stability Problems    [full version pdf, full version ps, ECCC, arXiv, FOCS version ]
      In Proceedings of 50th FOCS. 2009. Atlanta, Georgia.

    Selected Talks

    • Games, Equilibrium and the complexity class PPAD
      Cowles Foundation for Research in Economics, Yale University, November 12, 2009.
    • The Complexity of Scarf's Lemma and Related Problems
      ACO Student Seminar, Georgia Institute of Technology, March 4, 2009.
    • A Distributed Protocol for Fractional Stable Paths Problem
      DIMACS/DyDAnWorkshop on Secure Internet Routing, Rutgers University, March 24-26, 2008.
    • Approximating Betweenness Centrality
      5th Workshop on Algorithms and Models for the Web-Graph (WAW 2007), San Diego, CA, December 11-12, 2007.

    Professional Activities

  • Reviewed papers for the following journals :
               - Theoretical Computer Science
               - ACM Transactions on Knowledge Discovery from Data
               - ACM Journal on Experimental Algorithmics

  • Reviewed papers for the following conferences :
               - Fifth Workshop on Internet & Network Economics (WINE 2009)
               - Symposium on Discrete Algorithms (SODA 2010)

    • Conferences attended

  • FOCS 2009, October 24-27, 2009, Atlanta, GA.
  • Workshop: Barriers in Computational Complexity, August 25-29 2009, Intractability Center, Printecon, NJ.
  • Impagliazzo's Worlds Workshop, June 3-5 2009, Intractability Center, Printecon, NJ.
  • STOC 2009, May 31 - June 2, 2009, Bethesda, Maryland.
  • DIMACS/DyDAn Workshop: Secure Internet Routing, March 24 - 26, 2008, Rutgers University.
  • DIMACS Workshop: The Boundary between Economic Theory and Computer Science, October 24-26, 2007, Rutgers University.
  • FOCS 2007, October 20-23, 2007, Providence, RI.
    		•