Sanjeev Khanna, Madhu Sudan

In 1978, Schaefer considered a subclass of languages in

NP and proved a ``dichotomy theorem'' for this class. The subclass

considered were problems expressible as ``constraint satisfaction

problems'', and the ``dichotomy theorem'' showed that every language in

this class is either in P, or is NP-hard. This result is in ...
more >>>

Beate Bollig, Ingo Wegener

Many BDD (binary decision diagram) models are motivated

by CAD applications and have led to complexity theoretical

problems and results. Motivated by applications in genetic

programming Krause, Savick\'y, and Wegener (1999) have shown

that for the inner product function IP$_n$ and the direct

storage access function DSA$_n$ ...
more >>>

Piotr Indyk, David P. Woodruff

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