We’re rewarding the question askers & reputations are being recalculated! Read more.
26

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 ($\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$; thanks to SamiD below for pointing out a missing $\mathsf{PP}$ in the paper, which I'd simply repeated ...


26

Cybenko's result is fairly intuitive, as I hope to convey below; what makes things more tricky is he was aiming both for generality, as well as a minimal number of hidden layers. Kolmogorov's result (mentioned by vzn) in fact achieves a stronger guarantee, but is somewhat less relevant to machine learning (in particular, it does not build a standard neural ...


20

As you note, computing $A^m$ can be done in $O(\log m)$ times the number of operations for matrix multiplication on $N \times N$ matrices. The answer to your second question is no, at least for asymptotic complexity -- matrix squaring and matrix multiplication have equivalent time/arithmetic complexity (up to constant factors). Reducing squaring to matrix ...


10

Assuming that the coefficients of $f$ are integers or rationals and that you want integer roots, the simplest approach is to use the integer or rational root theorem. See http://en.wikipedia.org/wiki/Rational_root_theorem As noted by D.W., this might be problematic if the constant coefficient is hard to factor (see also https://math.stackexchange.com/...


7

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))^{n}$. Now it is easy to check if $S = 0$ (can be done even in $TC^0$ -- see this).If $S \neq 0$ then it is bounded away from $0$ by a quantity (because it is an ...


7

Estimating the volume of a convex polytope and the closely related task of sampling from it have applications in private data release. Roughly, the problem you want to solve is: given a collection of numeric valued queries on a database, come up with answers to those questions that are as close as possible to the real answers, while satisfying differential ...


6

If your error norm is the Frobenius distance (that is, $m(X, U) = \|X - U \|_F$, then there is a closed form for your problem. $A = V^+ U$, where $V^+$ is the Moore-Penrose pseudoinverse of $V$ (this is a generalized inverse for non-square matrices).


5

$\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, and trigonometric and cyclometric functions like $\sin x$, $\cos x$, $\arctan x$, are computable in uniform $\tc$ (and therefore in logarithmic space) for ...


4

Do not use a single stream of random numbers generated in one thread (or process) and consumed in other threads (or processes). In general, you must instead use several random number streams for your calculations, one for each thread/process. It is extremely important for these streams to be uncorrelated, in order for the pseudorandom numbers to be effective ...


4

Polyhedra are widely used in program analysis as a means of representing (an overapproximation of) set of all possible states, where a state records the value of each variable in the program. If there are a set of invariants of the program variables, each of which can be represented as a linear inequality on the variables, then conjoining all of these ...


4

Hari Narayanan recentely posted a paper on the arXiv in which he uses estimating the volume of a convex polytope to prove certain results about the Littlewood-Richardson (LR) coefficients. The LR coefficients are certain integers in representation theory that have applications in geometric complexity theory, particle physics, and many other fields (see the ...


4

You can partition your domain for subsequent parallel processing as follows. There are a few possible options. You can try a static geometric decomposition, including recursive bisection, quad or oct-trees and a space-filling curve. Recursive bisection techniques are used to partition a domain (e.g., a finite element grid) into subdomains of approximately ...


3

There is an advanced result, key to machine learning, known as Kolmogorov's theorem [1]; I have never seen an intuitive sketch of why it works. This may have to do with the different cultures that approach it. The applied learning crowd regards Kolmogorov's theorem as an existence theorem that merely indicates that NNs may exist, so at least the structure ...


3

You can (without too much work) find a number $K$ such that if $|x| > K$ then $|a_n x^n| > \sum_{k<n} |a_k x^k|$, and so all roots are inside $(-K,K)$ and the distance between them is smaller than $2K$.


3

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 Slyke A Numerically Stable Form of the Simplex Algorithm, Philip E. Gill and Walter Murray You might also be interested in the revised simplex method. This ...


3

see e.g.: N-Dimensional Volume Estimation of Convex Bodies: Algorithms and Applications by Sharma, Prasanna, Aswal for an example/case study in economic forecasting, ie supply chain management. Our methods can be used to quantify information content and uncertainty, in constraint regions, in a robust optimization framework. We show applications in supply ...


3

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 minimal polynomial $x-\alpha$) and $n=0$, the size of the output is exponential in the size of the input. This bound is of course optimal, as there are a number ...


3

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 expect this post will clarify why. I know of essentially two cases: the input matrix has coefficients that are algebraic numbers (*): then the eigenvalues are also ...


2

heres another angle turned up on some online investigation. the Birkoff polytope $B_n$ has many deep theoretical properties & relates to eg to perfect matchings on graphs, but volume calculations of it are very hard even for low $n$ eg as in this study by Beck and Pixton. a more direct/remarkable TCS connection arises in that a relatively recent paper ...


1

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. However, for Mersenne-Twister there exists a special implementation called Dynamic Creator where it is possible to draw seeds that give some guarantees regarding ...


1

There is the number theoretic transform where all calculations are done using integers which should completely get round any concerns about numerical stability, at the possible expense of some speed (see e.g. https://ccrma.stanford.edu/~jos/st/Number_Theoretic_Transform.html). However this will only work for you if your numbers are rational and can be ...


1

You could give a shot at Ermedahl & Sjodin: Interval analysis of C-variables using Abstract Interpretation.


1

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 matrix sign function, see for example "Fast Linear Algebra is Stable" by Demmel, Dumitriu and Holtz. In that paper, it is shown that the eigenvalue problem can be ...


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