9 votes
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 ...
Stasys's user avatar
  • 6,765
8 votes
Accepted

Implications of a recent negative result to geometric complexity

It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an ...
Joshua Grochow's user avatar
6 votes

Riemann Hypothesis and Complexity Theory

Valiant's classes are defined over some field. They can use arbitrary constants from that field. To draw some conclusion about Boolean complexity classes, one needs to replace these arbitrary ...
Markus Bläser's user avatar
5 votes
Accepted

Complexity of counting integer roots of multivariate polynomials in a polyhedron?

The decision version of this problem is obviously in $\mathsf{NP}$, and Manders & Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer $x \in [...
Joshua Grochow's user avatar
5 votes
Accepted

DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$

One is used to this kind of argument because of what happens in $P$ and $NP$. However, one has to go back to why it is the case in general. If $P \in B$ is $A$-complete under $\prec$-reductions and $B ...
holf's user avatar
  • 2,174
5 votes
Accepted

Is $GCT$ necessarily a negative result program?

It depends a little what you mean exactly by "GCT". If you mean it more generally, the answer is certainly yes. If you mean it more specifically about multiplicity obstructions, this is a ...
Joshua Grochow's user avatar
4 votes
Accepted

Can reciprocal inputs speed up monotone computations?

I believe the answer to the Question 1 is negative. We introduce an auxiliary circuit type: $X_k$-circuits have inputs $x_1, \dots, x_n$ and $1/x_k,\dots,1/x_n$ and have in addition to $+$ and $\...
Vladimir Lysikov's user avatar
3 votes
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 ...
Joshua Grochow's user avatar
3 votes
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 ...
holf's user avatar
  • 2,174
3 votes

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 ...
Joshua Grochow's user avatar
2 votes

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-...
Kaveh's user avatar
  • 21.6k
2 votes
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 ...
Joshua Grochow's user avatar
2 votes

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 ...
Andrew Morgan's user avatar
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 ...
Vladimir Lysikov's user avatar
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 ...
Geoffrey Irving's user avatar
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 = \...
anamay's user avatar
  • 11

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