# Tag Info

Accepted

### Implications of Riemann Hypothesis variants in TCS

First, I’m not aware of any CS application of Riemann’s hypothesis as such. There are various applications of generalizations of RH. Second, a terminological note: contrary to popular belief, there ...
Accepted

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

### Complexity of the inverse modulo a composite number

Let us call the function which takes $(a,b)$ to $r$ such that $a = bq + r$ with $r < b$ (and all of $a,b,q,r$ nonnegative integers) the Remainder function. This function cannot be computed at all ...

### Sorting using ring operations

This is more a comment than an answer, but the space in the comment box was too short. Or if it's an answer, it's one in the other direction: evidence that linear time is possible. I think you're ...
Accepted

### $NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$

As proved in , Boolean languages computable in $\mathrm P_\mathbb C$ are in $\mathrm{BPP}$. (They state it for $\mathrm P_\mathbb R$ without inequality tests, which amounts to the same thing.) On ...
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 $\... 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 ... 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 ... 3 votes Accepted ### Hitting set of very restricted linear forms There is a tight lower bound of size$\Omega(n/ \log n)$by simple counting argument. Suppose there is a hitting set$H=\{\alpha_{1},\dots,\alpha_{k}\}$of size$k$. We will show that there is always ... 2 votes ### Is there a theory that combines category theory/abstract algebra and computational complexity? This answer about isomorphisms between formal languages combines algebraic results from the theory of codes with notions from category theory to investigate possible notions of equivalence and ... 2 votes ### Lower bounds for Polynomials computing the boolean functions Regarding Question C: Number of monomials is essentially the same thing as circuit size of depth-2 algebraic circuits (unless the polynomial is a product of linear polynomials, in which case one could ... 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-... 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 ... 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 ... 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 ... 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 = \...
If a reverse of a modulo $M$ exists, it means that $\gcd(a,M)=1$, so you can just use the extended Euclidean algorithm to find $x$ and $y$ that satisfy $ax+My=1$. From here $x$ will be the reverse ...