Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR96-062 | 3rd December 1996
Sanjeev Khanna, Madhu Sudan, David P. Williamson

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction


In this paper we study the approximability of boolean constraint
satisfaction problems. A problem in this class consists of some
collection of ``constraints'' (i.e., functions
$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set
of constraints applied to specified subsets of $n$ boolean
variables. Schaefer earlier ... more >>>


TR96-061 | 27th November 1996
Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener

Optimal attribute-efficient learning of disjunction, parity, and threshold functions

Decision trees are a very general computation model.
Here the problem is to identify a Boolean function $f$ out of a given
set of Boolean functions $F$ by asking for the value of $f$ at adaptively
chosen inputs.
For classes $F$ consisting of functions which may be obtained from one
more >>>


TR96-060 | 19th November 1996
Bernd Borchert, Frank Stephan

Looking for an Analogue of Rice's Theorem in Complexity Theory

Rice's Theorem says that every nontrivial semantic property
of programs is undecidable. It this spirit we show the following:
Every nontrivial absolute (gap, relative) counting property of circuits
is UP-hard with respect to polynomial-time Turing reductions.

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint