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

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},
$...

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

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.
$$
...

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

#### Related Tags

computational-complexity × 1274algorithms × 231

co.combinatorics × 222

graph-theory × 190

nt.number-theory × 138

lo.logic × 115

computer-science × 115

computability-theory × 102

reference-request × 88

np × 75

computational-number-theory × 60

linear-algebra × 58

gr.group-theory × 43

combinatorial-optimization × 39

matrices × 37

polynomials × 33

oc.optimization-and-control × 32

ag.algebraic-geometry × 31

pr.probability × 27

discrete-geometry × 26

prime-numbers × 24

graph-colorings × 23

cryptography × 23

integer-programming × 22

approximation-algorithms × 22