# Tag Info

Accepted

### VC dimension of polynomials over tropical semirings?

I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can ...
• 6,765
Accepted

• 37.4k
Accepted

Accepted

### In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$

You do not cite the part of the survey that is actually relevant for getting the $s/3$ lower bound: Starting from the root, walk down to the leaves by always taking the child with a larger sub-tree ...
• 2,174
Accepted

### Questions about P vs NP and geometric complexity theory

The short answer is no these are not known, though they are certainly not out of the question. There are no direct implications known to P vs NP, and we do not even have a conjecture (let alone ...
• 37.4k

### IPS upper bound for subset sum axiom

First, Kaveh is correct that the verification for IPS is randomized, so all it would show is $\mathsf{NP} \subseteq \mathsf{coAM}$ (not $\mathsf{NP} = \mathsf{coNP}$). However, this alone would still ...
• 37.4k

### IPS upper bound for subset sum axiom

I think what you are missing is probably the complexity of the proof verification algorithm for IPS. It is generally true that if we have a Cook-Reckhow proof system and have short proofs for a coNP-...
• 21.7k
Accepted

### What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$

As already pointed out by Emil Jeřábek in the comments, this is Hilbert's Tenth Problem over the rationals, whose computability is a notorious open question. In this case, note that the Boolean ...
• 37.4k

### Decomposing outer product or general rank factorization over $\Bbb F_q$

There might be faster algorithms, but it is easy to compute such a factorization (for any $r$) from the reduced row-echelon form of $M$: set $M_2$ to be the RREF with zero rows removed, and $M_1$ to ...
• 1,429
1 vote

### Arithmetic Circuit Hierarchy?

This question has a somewhat trivial answer because the polynomial $x^{2^s}$ requires $s$ multiplications, so you can just take $h = x_1^{2^{f(n)}}$. This is one of the reasons why in algebraic ...
1 vote
Accepted

### Complexity of matrix diagonalization

Reducing to a tridiagonal matrix takes $O(n^3)$ independent of $\epsilon$. I believe the fastest algorithm after that is divide and conquer, which I believe is $O(n^2 \log(1/\epsilon))$, for a total ...
• 3,263
1 vote

### VNP is closed under taking coefficients using Valiant's criterion

Here is a related statement which can be proven "algebraically" (as opposed to going to the boolean world of #P/poly). Suppose $f(x_1,\ldots,x_n,y_1,\ldots,y_m) \in \text{VNP}$ for \$m = \...
• 11

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