## New answers tagged algorithms

2
votes

Accepted

### Metropolis-Hastings kernel in measure theory

You asked another question that seems somewhat likely to be closed for not being research-level mathematics. I will include my posted answer to that here because that one may get closed.
One does not ...

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

2
votes

### Recover unknown vector through shifted argmax queries

The following argument suggests that the factor $O(n)$ cannot be improved. Suppose for a contradiction that $x\in\{0,1\}^n$ and after queries with $v_1,\dots,v_{n-1}\in\mathbb R^n$ we determined that $...

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

Accepted

### Approximating a fraction with a given denominator

Using continued fraction expansion of the number $M/N$ you can find all best approximations of the first or the second kind. Probably you ask about best approximations of the first kind: a rational ...

3
votes

Accepted

### Can we integrate arbitrary rational functions of Jacobian elliptic functions?

The answer is positive. Rational function of Jacobi elliptic function is elliptic, and for every elliptic function $f$,
$f(z)dz$ is an Abelian differential, and integral of it is an Abelian integral. ...

3
votes

### Approximating a fraction with a given denominator

This can be modelled as two variable integer linear programming, which can be solved in polynomial time. You want to minimize $M r - N k$, subject to $L \leq r \leq (1+\delta)L$ and $M r - N k \geq 0$....

2
votes

### Algorithm for grouping tetrahedra from Voronoi diagram

Chapter 27 of The Handbook of Discrete and Computational Geometry
enumerates the complexity of known Delaunay triangulation algorithms of any dimension (see Table 27.2.1 there).
For 3D Delaunay the ...

1
vote

Accepted

### Implementing the $\pi$ BBP algorithm

Bounding this sum is not hard, it is majorized by a geometric progression.
If you forget about the summands starting from $n + p$ (in your terms this means $s = n + p - 1$)
$$\sum_{k = n + p}^{\infty} ...

Top 50 recent answers are included

#### Related Tags

algorithms × 1541graph-theory × 336

co.combinatorics × 324

computational-complexity × 231

nt.number-theory × 204

linear-algebra × 125

computer-science × 86

reference-request × 85

gr.group-theory × 74

mg.metric-geometry × 72

pr.probability × 67

computational-geometry × 66

combinatorial-optimization × 60

polynomials × 57

computational-number-theory × 56

approximation-algorithms × 56

ag.algebraic-geometry × 53

matrices × 52

na.numerical-analysis × 50

discrete-geometry × 49

oc.optimization-and-control × 43

ac.commutative-algebra × 37

prime-numbers × 37

linear-programming × 36

graph-colorings × 31