Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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))^{...
Nikhil's user avatar
  • 1,364
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)$.
walkerbacker's user avatar
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'...
Shaull's user avatar
  • 5,646
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}...
Denis's user avatar
  • 8,893
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(...
mathworker21's 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 ...
Amaury Pouly's user avatar
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 ...
Alex's user avatar
  • 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 ...
Neal Young's user avatar
  • 10.8k
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 ...
cody's user avatar
  • 13.9k
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: ...
Avi Tal's user avatar
  • 1,606
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 ...
Peter Shor 's 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. ...
mithrawnuruodo's 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 ...
nikhil srivastava's 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 ...
Sébastien Loisel's user avatar

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