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 1991
I broadcast a talk on this paper, which I will at some point make available here.
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 the known result that the permanent cannot
be expressed as a determinant of the same size by substituting linear forms as a trivial corollary.
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.)
|
