We introduce the notion of a plain basis for a co-clone in Post's lattice. Such a basis is a set of relations B such that every constraint C over a relation in the co-clone is logically equivalent to a conjunction of equalities and constraints over B and the same variables ... more >>>

We propose matchgate tensors as a natural and proper language
to develop Valiant's new theory of Holographic Algorithms.
We give a treatment of the central theorem in this theory---the Holant
Theorem---in terms of matchgate tensors.
Some generalizations are presented.

more >>>

A private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about the input x other than what can be deduced from f(x). We give the first two-party private approximation of the Euclidean distance ... more >>>