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))^{...
- 1,364
5
votes
Accepted
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'...
- 5,616
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}...
- 8,923
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)$.
- 136
4
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 ...
- 156
3
votes
Accepted
Computing an approximate root of a two-dimensional monotone function
Yes, it's possible with $O\left(\log^2(1/\epsilon)\right)$ function evaluations.
We write $f = (f_1,f_2)$, so in your notation, e.g. $f_1(x,y) := f(x,y)_1$. By replacing $f_1$ with $(x,y) \mapsto f_1(...
- 321
2
votes
Complexity of Finding the Eigendecomposition of a Matrix
Here is a relatively recent answer that answers this (mostly) in the affirmative:
Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time
Where the ...
- 121
1
vote
Accepted
What infinite sums cannot be approximated in polynomial time?
OP asks (now in the comments) for a real number $s$ such that (among other things), one can prove that, if the first $n$ bits of $s$ can be computed in time poly$(n)$, then P$=$NP.
Perhaps the most ...
- 10.9k
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 ...
- 14k
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:
...
- 1,616
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 ...
- 24.9k
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.
...
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 ...
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 ...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible