# Tagged Questions

**8**

votes

**1**answer

235 views

+50

### Fast checking that overdetermined polynomial system does not have a solution

As a result of some inductive procedure for each $n$ I have a system of about $n^2$ polynomial equations with $n$ variables with integer coefficients, which can be precisely computed. As the system is ...

**3**

votes

**1**answer

99 views

### Approximate the square root of (1-X) efficiently through (nested) products

Currently, I encountered a problem of approximating the following
series:
$$
(I-X)^{-\frac{1}{2}}=I+\frac{1}{2}X+\frac{1\cdot3}{2\cdot4}X^{2}+\frac{1\cdot3\cdot5}{2\cdot4\cdot6}X^{3}+\ldots
$$
where ...

**1**

vote

**1**answer

195 views

### Does this algorithm terminate in all scenarios?

Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in ...

**3**

votes

**2**answers

1k views

### Computational complexity of calculating the nth root of a real number

Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example:
Jean-Michel Muller, "Elementary Functions: ...

**2**

votes

**2**answers

501 views

### sparsity of QR decomposition

Hi, everyone!
I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and ...

**2**

votes

**1**answer

307 views

### Complexity of computing derivatives

Sorry if this is too simple. This is my first question here.
Suppose $f : R^n \to R$ is a differentiable function. Say that we can compute in $T$ arithmetic operations the value $f(x)$ at any point ...

**11**

votes

**1**answer

339 views

### The complexity of the leading fractional bit of a power of a rational number

On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are ...

**0**

votes

**0**answers

499 views

### How to calculate inner product with some set of (0 or 1,0 or 1,0 or 1, … )vectors in the fastest way ?

Given:
some vector $R=(r_1...r_l)$ - real numbers,
and a set of distinct vectors with $0$ or $1$ coordinates
$$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\\
V_2=(c_{2,1} ... c_{2,l}),\\\
...

**1**

vote

**1**answer

933 views

### Does P≠NP over ℝ imply P≠NP ?

Does P≠NP over ℝ imply P≠NP ?
where ℝ is for Real number algorithms as described by Smale with a suitable formulation of P≠NP over ℝ.
Complexity Theory and Numerical Analysis, Steve Smale, 2000
...

**10**

votes

**2**answers

826 views

### Are there any known quantum algorithms that clearly fall outside a few narrow classes?

I'm trying to refresh myself on quantum algorithms and have been skimming Childs and van Dam's 2008 RMP paper among other things. From my preliminary surfing it looks like the known quantum algorithms ...

**30**

votes

**7**answers

2k views

### What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference?
Long version of the question:
I'm sort of surprised to be asking this, because ...