All reports by Author Shiva Kintali:

__
TR12-126
| 23rd September 2012
__

Shiva Kintali, Sinziana Munteanu#### Computing Bounded Path Decompositions in Logspace

__
TR10-158
| 31st October 2010
__

Shiva Kintali#### Realizable Paths and the NL vs L Problem

Revisions: 2

__
TR09-041
| 9th April 2009
__

Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng#### Reducibility Among Fractional Stability Problems

Shiva Kintali, Sinziana Munteanu

We present a logspace algorithm to compute path decompositions of bounded pathwidth graphs, thus settling its complexity. Prior to our work, the best known upper bound to compute such decompositions was linear time. We also show that deciding if the pathwidth of a graph is at most a given constant ... more >>>

Shiva Kintali

A celebrated theorem of Savitch states that NSPACE(S) is contained DSPACE(S^2). In particular, Savitch gave a deterministic algorithm to solve ST-CONNECTIVITY (an NL-complete problem) using O(log^2{n}) space, implying NL is in DSPACE(log^2{n}). While Savitchâ€™s theorem itself has not been improved in the last four decades, studying the space complexity of ... more >>>

Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng

"As has often been the case with NP-completeness proofs, PPAD-completeness proofs will be eventually refined to cover simpler and more realistic looking classes of games. And then researchers will strive to identify even simpler classes." --Papadimitriou (chapter 2 of Algorithmic Game Theory book)

In a landmark paper, Papadimitriou introduced a ... more >>>