29 votes
Accepted

Computational complexity of pi

OK, James Lee has pointed me to this 2011 paper by Samir Datta and Rameshwar Pratap, which proves that my language $L$ (encoding the digits of $\pi$) is in the fourth level of the counting hierarchy ($...
user avatar
7 votes
Accepted

Proof for Upper Bound of Sum of Square Roots Problem

Here is a rather sloppy proof sketch. Let $S = \sum_{i=1}^n \delta_i \sqrt{a_i}$ where $\delta_i \in \{\pm 1\}$. This is an algebraic number of degree at most $2^n$ and height at most $H = (max(a_i))^{...
user avatar
  • 1,324
5 votes

Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $O(n^\omega)$, down from $O(n^3)$.
user avatar
5 votes
Accepted

What is the computational complexity of sin and cos for floating point inputs?

$\def\tc{\mathrm{TC}^0}\DeclareMathOperator\len{len}$Since there were no other takers, let me expand the comments above. The fundamental fact here is that approximations of basic arithmetic operations,...
user avatar
5 votes

Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy

If the coefficients are roots of rational numbers, then they are in particular algebraic numbers. This means that you can encode the coefficients as additional polynomial constraints. So overall, you'...
user avatar
  • 5,246
5 votes

Can the Banach-Tarski paradox be "realized" by floating-point round-off?

This seems to have little to do with Banach-Tarski. In your setting, f is simply not an isometry due to floating-point errors, and in particular there must be a single piece $i$ such that $\mathrm{Vol}...
user avatar
  • 7,643
3 votes

Numerical stability of Simplex method

Yes, there is research on this issue. The Simplex Method is Not Always Well Behaved, Wlodzimierz Ogryczak retroLP, An Implementation of the Standard Simplex Method, Gavriel Yarmish and Richard Van ...
user avatar
  • 131
3 votes

The exponential function over algebraic numbers

As written, the problem requires time $2^{\Omega(m)}$, where $m$ is the length of input (you unfortunately used $n$ for something else). Indeed, if e.g. $\alpha$ is a positive integer (given by its ...
user avatar
3 votes
Accepted

What is the time complexity of increasing the precision of finding matrix eigenvalues?

I do not have a complete answer to your question but here are some thoughts and references. First of all, it is crucial to specify the model of computation and the representation of the input, I ...
user avatar
1 vote

Can finite difference methods approximate the space/time complexity of given programs?

This is exactly the approach taken in certain forms of modern inference of complexity bounds! From Jan Hoffmann's excellent thesis: In a nutshell, our approach is as follows. We start from an as yet ...
user avatar
  • 13.1k
1 vote

Can finite difference methods approximate the space/time complexity of given programs?

This is not exactly "finite difference", but when dealing with recurrences, the discrete version of "differential equations" often comes handy. This video might be very helpful: ...
user avatar
  • 1,456
1 vote

Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy

The problem is NP-hard. If you have $P$ polynomials, you can use them to encode 1-in-3 SAT. Take an instance of 1-in-3 SAT. First, take the equations $x_i^2 = 1$ for each variable. This means all the ...
user avatar
1 vote

Multiple independent random number streams

It was already mentioned that it is important to use independent streams. Which is not guaranteed if you, e.g., use the naive approach of just seeding each of your PRNG with a different number. ...
user avatar
1 vote

Complexity of Finding the Eigendecomposition of a Matrix

See the intro of https://arxiv.org/abs/1912.08805 for a discussion of the literature around this problem. In short: O(n^3) has been known for symmetric matrices since the 60's, but was not known in ...
user avatar
1 vote

Complexity of Finding the Eigendecomposition of a Matrix

This is an old question but some important literature seems to have been missed. There are algorithms for which we have stronger theoretical support. For example, there are iterations based on the ...
user avatar

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