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

TR02-054 | 5th September 2002
Detlef Sieling

Minimization of Decision Trees is Hard to Approximate

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown ... more >>>


TR02-053 | 20th July 2002
Lars Engebretsen, Venkatesan Guruswami

Is Constraint Satisfaction Over Two Variables Always Easy?

By the breakthrough work of HÃ¥stad, several constraint satisfaction
problems are now known to have the following approximation resistance
property: satisfying more clauses than what picking a random
assignment would achieve is NP-hard. This is the case for example for
Max E3-Sat, Max E3-Lin and Max E4-Set Splitting. A notable ... more >>>


TR02-052 | 3rd September 2002
Vince Grolmusz

Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications

Revisions: 1

Elementary symmetric polynomials $S_n^k$ are used as a
benchmark for the bounded-depth arithmetic circuit model of computation.
In this work we prove that $S_n^k$ modulo composite numbers $m=p_1p_2$
can be computed with much fewer multiplications than over any field, if
the coefficients of monomials $x_{i_1}x_{i_2}\cdots x_{i_k}$ ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint