
PreviousNext
We show how one can use non-prime-power, composite moduli for
computing representations of the product of two $n\times n$ matrices
using only $n^{2+o(1)}$ multiplications.
In the simultaneous message model, two parties holding $n$-bit integers
$x,y$ send messages to a third party, the {\it referee}, enabling
him to compute a boolean function $f(x,y)$. Buhrman et al
[BCWW01] proved the remarkable result that, when $f$ is the
equality function, the referee can solve this problem by ...
more >>>
The paper contributes to the systematic study (started by Berman and
Karpinski) of explicit approximability lower bounds for small occurrence optimization
problems. We present parametrized reductions for some packing and
covering problems, including 3-Dimensional Matching, and prove the best
known inapproximability results even for highly restricted versions of ...
more >>>
PreviousNext