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