Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR17-001 | 6th January 2017
Stephen Cook, Bruce Kapron

A Survey of Classes of Primitive Recursive Functions

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 >>>

TR01-024 | 1st March 2001
Stephen Cook, Antonina Kolokolova

A second-order system for polynomial-time reasoning based on Graedel's theorem

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 >>>

TR00-034 | 5th June 2000
Valentine Kabanets, Charles Rackoff, Stephen Cook

Efficiently Approximable Real-Valued Functions

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 >>>

ISSN 1433-8092 | Imprint