All reports by Author Stephen Cook:

__
TR18-184
| 5th November 2018
__

Iddo Tzameret, Stephen Cook#### Uniform, Integral and Feasible Proofs for the Determinant Identities

Revisions: 1

__
TR17-001
| 6th January 2017
__

Stephen Cook, Bruce Kapron#### A Survey of Classes of Primitive Recursive Functions

__
TR01-024
| 1st March 2001
__

Stephen Cook, Antonina Kolokolova#### A second-order system for polynomial-time reasoning based on Graedel's theorem

__
TR00-034
| 5th June 2000
__

Valentine Kabanets, Charles Rackoff, Stephen Cook#### Efficiently Approximable Real-Valued Functions

Iddo Tzameret, Stephen Cook

Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over $GF(2)$ in Hrubes-Tzameret [SICOMP'15]. Specifically, we show that the multiplicativity of the determinant function and the ... more >>>

Stephen Cook, Bruce Kapron

This paper is a transcription of mimeographed course notes titled ``A Survey of Classes of Primitive Recursive Functions", by S.A. Cook, for the University of California Berkeley course Math 290, Sect. 14, January 1967. The notes present a survey of subrecursive function

classes (and classes of relations based on these ...
more >>>

Stephen Cook, Antonina Kolokolova

We introduce a second-order system V_1-Horn of bounded arithmetic

formalizing polynomial-time reasoning, based on Graedel's

second-order Horn characterization of P. Our system has

comprehension over P predicates (defined by Graedel's second-order

Horn formulas), and only finitely many function symbols. Other

systems of polynomial-time reasoning either ...
more >>>

Valentine Kabanets, Charles Rackoff, Stephen Cook

We consider a class, denoted APP, of real-valued functions

f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to

within any epsilon>0, by a probabilistic Turing machine running in

time poly(n,1/epsilon). We argue that APP can be viewed as a

generalization of BPP, and show that APP contains a natural

complete ...
more >>>