Research Interests

  • Structural Graph theory
               - Treewidth, Minors, Digraph width parameters.
               - Matching, Pfaffians, Graceful labeling.
  • Computational Complexity
               - Derandomization, Space bounded computation.
               - Complexity aspects of games, equilibrium and fixed points.
  • Machine Learning
               - Information retrieval, Natural language processing, Text summarization.
               - Semi-supervised learning, Distributed machine learning, Big Data Analytics.



  • Publications


      ---------- TreeWidth, Minors and Digraph Parameters ----------


    1. Shiva Kintali, Qiuyi Zhang
      Forbidden Directed Minors and Directed Pathwidth    [pdf]
      Preprint.

    2. Shiva Kintali
      Directed Minors IV : Long Disjoint Directed Cycles.   
      Under Preparation.

    3. Shiva Kintali
      Directed Minors III : Directed Linked Decompositions.    [pdf]
      Submitted to a Journal

    4. Shiva Kintali
      Directed Minors II : Orientations of partial k-trees.   
      Under Preparation.

    5. Shiva Kintali
      Directed Minors I   
      Under Preparation.

    6. Shiva Kintali
      Directed Width Parameters and Circumference of Digraphs    [pdf]
      Theoretical Computer Science, Volume 659, 10 January 2017, Pages 83-87 [Journal Version]

    7. Shiva Kintali, Qiuyi Zhang
      Forbidden Directed Minors and Kelly-width    [pdf]
      Theoretical Computer Science, Volume 662, 1 February 2017, Pages 40-47 [Journal Version]

    8. Shiva Kintali, Nishad Kothari, Akash Kumar
      Approximation Algorithms for Directed Width Parameters    [pdf]
      Theoretical Computer Science, Volume 562, 11 January 2015, Pages 365–376 [Journal Version]



    9. -------------------- Complexity --------------------


    10. Shiva Kintali.
      Realizable Paths and the NL vs L Problem    [pdf]
      Preprint

    11. Shiva Kintali,  Laura J. Poplawski,  Rajmohan Rajaraman,  Ravi Sundaram,  Shang-Hua Teng
      Reducibility Among Fractional Stability Problems    [full version pdf, FOCS version, SICOMP Journal Version ]
      Journal version is published in SIAM Journal on Computing. 2013, 42(6), pages 2063–2113
      In Proceedings of 50th FOCS. 2009. Atlanta, Georgia.

    12. Shiva Kintali, Asaf Shapira
      A Note on the Balanced ST-Connectivity    [pdf]
      Preprint

    13. Shiva Kintali.
      SCARF is PPAD-complete    [pdf]
      Manuscript



    14. -------------------- Algorithms --------------------


    15. Shiva Kintali, Sinziana Munteanu
      Computing Bounded Path Decompositions in Logspace    [pdf]
      Preprint

    16. Parinya Chalermsook,  Shiva Kintali,  Richard Lipton,  Danupon Nanongkai
      Graph Pricing Problem on Bounded Tree-width, Bounded Genus and k-partite graphs    [pdf]
      Chicago Journal of Theoretical Computer Science, 2013 (13)

    17. David A. Bader, Shiva Kintali, Kamesh Madduri, Milena Mihail.
      Approximating Betweenness Centrality    [pdf]
      In the Proceedings of Workshop On Algorithms And Models For The Web-Graph (WAW) 2007.

    18. Shiva Kintali.
      A Distributed Protocol for Fractional Stable Paths Problem    [pdf]
      In Proceedings of the DIMACS/DyDAn Workshop on Secure Internet Routing, Rutgers University, March 24-26, 2008
      Georgia Tech, College of Computing Technical Report GT-CS-08-06

    19. Shiva Kintali.
      Betweenness Centrality : Algorithms and Lower Bounds    [pdf]
      Georgia Tech, College of Computing Technical Report GT-CS-09-10



    20. -------------------- Miscellaneous --------------------


    21. Shiva Kintali
      A Generalization of Erdos's Proof of Bertrand-Chebyshev Theorem    [pdf]
      Manuscript

    22. Chun Chen, Jaewook Shin, Shiva Kintali, Jacqueline Chame, Mary Hall
      Model-Guided Empirical Optimization for Multimedia Extension Architectures.
      POHLL 2007 (In association with IPDPS 2007)

    23. Shiva Kintali.
      MxYacc: Parser Generator for Mixed Languages.
      SIGPLAN Notices 41(2): 25-28 (2006)

    24. Shiva Kintali.
      Efficiently Parsing Mixed Languages.
      ANTLR Workshop 2004

    25. Sudeshna Sarkar, Shiva Kintali, Rajib Lochan Saha and Supradeep Barua.
      Conversion of unstructured text to structured hypertext form,
      International Forum cum Conference on Information Technology and Communication at the Dawn of the New Millennium August 1-4, 2000, Bangkok, Thailand, pp 99-109.