6
votes
Accepted
Can addition and muliplication be simultaneously easy?
If you allow $|f(n)| = \Omega(|n|)$, then you can have $f(n) = 0^{|n|^2} n$ (this is string concatenation). It's easy to see that both multiplication and addition are linear in the size of their input ...
- 1,555
2
votes
Efficiently computing $\sum_k x^{k^2}$ modulo $p$
Not exactly an answer, but should provide a strong hint on where to look.
This is closely related to Gauss quadratic sums, expressions of the form
$$
g(a;p) = \sum\limits_{k=0}^{p-1} \omega_p^{ak^2},
$...
- 1,111
2
votes
NP-hardness of vertex cover for 3-chromatic graphs
Yes, it is NP-hard via reduction to Independent Set in cubic (3-regular) graphs.
Cubic graphs different from $K_4$ are 3-colorable in polynomial time via Brooks' theorem and IS remains NP-hard for ...
- 24k
1
vote
Accepted
Slicing bivariate exponential generating functions on x and y
Assuming $D(0) = 0$, we can restate the problem as $F(x, y) = A(x)^y$ for $A(x) = e^{D(x)}$.
It means that we can find $G_n(k)$ for any number $k$ as
$$
G_n(k) = \left[\frac{x^n}{n!}\right] A(x)^k.
$$
...
- 1,111
Only top scored, non community-wiki answers of a minimum length are eligible