Now showing items 1-8 of 8

• #### Improving Known Solutions is Hard ﻿

(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 ...
• #### A Note on Time-Space Bounded Interactive Protocols. ﻿

(Cornell University, 1991-04)
In this paper, we examine the power of time-space bounded interactive protocols with private coins. The class of languages having logspace, polynomial-time bounded private coin protocols is exactly PSPACE. We generalize ...
• #### On IP=PSPACE and Theorems with Narrow Proofs ﻿

(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. ...
• #### On Properties of Random Reductions ﻿

(Cornell University, 1993-09)
Randomness is widely accepted as a powerful computational resource because the most elegant and efficient solutions to several computational problems are randomized. A recurrent theme in the theory of randomized computation ...
• #### Random Reductions in the Boolean Hierarchy are Not Robust. ﻿

(Cornell University, 1990-10)
We investigate random reductions from complete sets in the Boolean Hierarchy to their complements. We show that under the assumption that the Polynomial Hierarchy is infinite, the error probability of such reductions ...
• #### Randomness-Optimal Unique Element Isolation, With Applications to Perfect Matching and Related Problems ﻿

(Cornell University, 1993-06)
In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the RNC algorithm for perfect matching due to Mulmuley, Vazirani and Vazirani[21] and in several ...
• #### Saving Queries With Randomness ﻿

(Cornell University, 1991-12)
In this paper, we provide tight bounds on the success probabilities of randomized reductions between various classes in the Boolean and Bounded Query Hierarchies. The P$^{SAT\Vert[k]}$ $\leq^{P}_{m}$ - complete language ...
• #### Structural Complexity Theory: Recent Surprises ﻿

(Cornell University, 1990-04)
This paper reviews the impact of some recent results on the research paradigms in structural complexity theory.