JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Cai, Jinyi"
Now showing items 16 of 6

The Boolean Hierarchy: Hardware over NP
Cai, Jinyi; Hemachandra, Lane A. (Cornell University, 198512)In this paper, we study the complexity of sets formed by boolean operations $(\bigcup, \bigcap,$ and complementation) on NP sets. These are the sets accepted by trees of hardware with NP predicates as leaves, and together ... 
The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
Coleman, Thomas F.; Cai, Jinyi (Cornell University, 198410)Numerical optimization algorithms often require the (symmetric) matrix of second derivatives, $\nabla^{2} f (x)$, of some problem function $f: R^{n} \rightarrow R^{1}$. If the Hessian matrix is large and sparse then ... 
Exact Counting is as Easy as Approximate Counting
Cai, Jinyi; Hemachandra, Lane A. (Cornell University, 198606)We show that exact counting and approximate counting are polynomially equivalent. That is $P^{#P} = P^{Approx#P}$, where #$P$ is a function that computes the number of solutions to a given Boolean formula $f$ (denoted ... 
Graph Minimal Uncolorability is $D_{p}$Complete
Cai, Jinyi; Meyer, Gabriele E. (Cornell University, 198506)In their excellent paper, C.H. Papadimitriou and M. Yannakakis [PY] asked whether the minimal3uncolorability problem is, among other Critical Problems, $D_{p}$complete. This paper gives an affirmative answer to the ... 
On Some Most Probable Separations of Complexity Classes
Cai, Jinyi (Cornell University, 198608)This thesis is a study of separations of some complexity classes which take place in almost all relativized worlds. We achieve probability one separations of PSPACE from the Polynomialtime Hierarchy PH. Also we separate ... 
With Probability One, a Random Oracle Separates PSPACE from the PolynomialTime Hierarchy
Cai, Jinyi (Cornell University, 198512)We consider how much error a fixed depth Boolean circuit has to make for computing the parity function. We show that with an exponential bound of the form $exp(n^{\lambda})$ on the size of the circuits, they make ...