6 votes

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 ...
Command Master's user avatar
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}, $...
Oleksandr  Kulkov's user avatar
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 ...
joro's user avatar
  • 24k
1 vote

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. $$ ...
Oleksandr  Kulkov's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible