Shiva Kintali

PhD Candidate
College of Computing
Georgia Institute of Technology

Contact : Click Here



Some mathematician has said pleasure lies not in discovering truth, but in seeking it.



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

My Blog :       My Brain is Open       twitter.com/kintali

Hobbies :       Paintings       Biking

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
               - Derandomization, Hardness of Approximation, Lower Bounds.
               - Studying space bounded complexity classes such as logspace, NL, LogCFL.
  • Algorithmic Game Theory
               - Computational aspects of games, equilibrium and fixed points.
               - Studying PPAD, PLS complexity classes.
    •            - Understanding the structure and function of social/information networks, Internet.
  • Discrete Mathematics
    •            - Graph theory, combinatorics, combinaorial optimization.
    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.
    • 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.

    Conferences attended

  • Workshop on Pseudo-randomness in Mathematical Structures, June 14-18 2010 Institute for Advanced Study, Princeton University.
  • 6th Graduate Student Combinatorics Conference, April 3-4 2010 Auburn University.
  • Combinatorics, Groups, Algorithms, and Complexity, Conference in honor of Laci Babai's 60th birthday. March 21-25, 2010. The Ohio State University, Columbus, Ohio.
  • 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.
  • WAW & WINE 2007, San Diego, CA, December 11-12, 2007.
  • DIMACS Workshop: The Boundary between Economic Theory and Computer Science, October 24-26, 2007, Rutgers University.
  • FOCS 2007, October 20-23, 2007, Providence, RI.
    		•