Computer Science & Engineering Department
University of Minnesota

200 Union St.SE Minneapolis
MN 55455 USA


6-197 Keller Hall







Carl Sturtivant


Theoretical Physics

1979, 1982

Churchill College, Cambridge University, England

Diploma (MS)

Computer Science


Churchill College, Cambridge University, England


Computer Science


Edinburgh University, Scotland

Here are some publications that I consider my most interesting ones. New papers and commentary here "soon".

Finite Field Arithmetic versus Bit Operations:

[1] Sturtivant & Frandsen, The Computational Efficacy of Finite Field Arithmetic, Theoretical Computer Science 112, 1993. This predates the following paper because of a two year publication delay at another journal prior to submission to TCS.

We give a simple complete polynomial equivalent to the Fermat Quotient (which is efficiently computable with bit operations in any effective representation of a finite field) whos arithmetic complexity determines whether finite field arithmetic is as powerful as bit operations in the most general setting (i.e. when the field characteristic is unbounded and allowed to grow with the input size). We explore arbitrary representations of field elements as bitstrings in which arithmetic is effective, so that our results are independent of representation, and we show that only prime fields need be considered without loss of generality. Finally, we connect the problem of computing this complete polynomial with arithmetic with modular Bernouilli numbers, and using Witt Vectors we show that it is equivalent to simulating modulo p2 arithmetic with modulo p arithmetic along with computing the additive carry in the Witt Vector representation, and we give a simple characterization of the latter.

[2] Boyar, Frandsen & Sturtivant, An Arithmetic Model of Computation Equivalent to Threshold Circuits, Theoretical Computer Science 93, 1992.

We give a computationally tight answer in the affirmative as to the efficacy of finite field arithmetic at characteristic 2. By using tight (constant-depth polynomial-size boolean threshold circuit computable) versions of the definitions in the previous paper, we show that circuits with unbounded fan-in finite field sum and product gates (of constant depth and polynomial size) compute the same class of functions as constant depth polynomial size boolean threshold circuits. The results are again independent of representation of the finite field elements as bitstrings. In 1992 I broadcast a talk on this paper for a general computer science audience, which you can see here in the following formats: mp4 ogg. Warning, this talk does not assume you even know what a finite field is.

Permanent versus Determinant:

This is the algebraic analogue of P versus NP, introduced by Valiant and finally seen by some as the reasonable way to attack this notorious problem. (More here soon.)

[3] Sturtivant, Generalized Symmetries of Polynomials in Algebraic Complexity, 23rd Proceedings of the IEEE conference on Foundations of Computer Science (FOCS), 1982, winner of the Machtey Prize.

[4] Sturtivant, Are There Elimination Algorithms for the Permanent?, Linear and Multilinear Algebra, 33, 1993.

The determinant is efficiently computed by methods that rely upon its linear symmetries (e.g. Gaussian elimination). We show that the Permanent has no non-trivial linear symmetries, and as corollaries there are no elimination algorithms to compute the permanent, and there is no bilinear product (analogue of matrix multiplication) that preserves the permanent. We also show as a trivial corollary the known result that the permanent cannot be expressed as a determinant of the same size by substituting linear forms.

One-Way Functions:

Do one-way functions exist? My working hypothesis is "no" if we consider bijective one-way functions and our model of computation is families of boolean circuits without uniformity constraints.

[5] Sturtivant & Zhang (Zhi-Li), Efficiently Inverting Bijections Given by Straight Line Programs, 30th Proceedings of the IEEE conference on Foundations of Computer Science (FOCS), 1990.

We show that (at polynomially bounded degree) there are no arithmetic one-way bijections. This is the algebraic analogue of my working hypothesis. I would like to prove this result with no degree bound ... more here soon about that project.

Models of Computation:

[6] Frandsen & Sturtivant, What is an Efficient Implementation of the lambda-calculus?, 5th ACM Conference on Functional Programming Languages and Computer Architecture, 1991.

The lambda calculus forms the theoretical basis for functional programming languages. This is perhaps my most misunderstood paper. (More here soon.)