Now showing items 1-6 of 6

• The Boolean Hierarchy: Hardware over NP ﻿

(Cornell University, 1985-12)
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 ﻿

(Cornell University, 1984-10)
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 ﻿

(Cornell University, 1986-06)
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 ﻿

(Cornell University, 1985-06)
In their excellent paper, C.H. Papadimitriou and M. Yannakakis [PY] asked whether the minimal-3-uncolorability 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 ﻿

(Cornell University, 1986-08)
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 Polynomial-time Hierarchy PH. Also we separate ...
• With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy ﻿

(Cornell University, 1985-12)
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 ...