# Tag Info

27

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 ...

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 ...

5

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're looking at a system of Diophantine equations (i.e., polynomials with integer coefficients). The sets defined by such equations are known as algebraic ...

5

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}(f(P_i))>\mathrm{Vol}(P_i)$, so no need to cut into several pieces. Banach-Tarski works because the notion of volume is not well-defined on the pieces. ...

5

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)$.

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 ...

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

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

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

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 variables must be either $\pm1$, ensuring that all solutions are real. Now, for all clause add the equation $x_i+x_j+x_k = -1$, where the clause contains ...

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

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 general until recently.

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