Now showing items 1-6 of 6

    • Improving Known Solutions is Hard 

      Ranjan, Desh; Chari, Suresh; Rohatgi, Pankaj (Cornell University, 1990-11)
      In this paper, we study the complexity of computing better solutions to optimization problems given other solutions. This is done in the context of the counterexample computation model introduced in [KPS90]. Assuming ...
    • Issues in NP-Optimization and Approximation 

      Ranjan, Desh (Cornell University, 1992-08)
      Optimization or finding the best solution for a problem amongst several possible ones is one of the central themes in computing. In particular, NP-optimization (NPO) problems, examples of which include such well-known ...
    • On IP=PSPACE and Theorems with Narrow Proofs 

      Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj (Cornell University, 1990-05)
      Very recently, it was shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible computations. ...
    • Quantifiers and Approximation 

      Panconesi, Alessandro; Ranjan, Desh (Cornell University, 1989-11)
      We investigate the relationship between logical expressibility of NP optimization problems and their approximation properties. First such attempt was made by Papadimitriou and Yannakakis, who defined the class of NPO ...
    • Space Bounded Computations: Review And New Separation Results 

      Hartmanis, Juris; Ranjan, Desh (Cornell University, 1989-05)
      In this paper, we review the key results about space bounded complexity classes, discuss the central open problems and outline the relevant proof techniques. We show that, for a slightly modified Turing machine model, ...
    • Structural Complexity Theory: Recent Surprises 

      Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj (Cornell University, 1990-04)
      This paper reviews the impact of some recent results on the research paradigms in structural complexity theory.