# 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 ...
• 14.8k
Accepted

• 35.7k
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 ...
• 35.7k
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 ...
• 35.7k

### 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 ...
• 50.2k
Accepted

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

As proved in [1], 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 ...
• 14.8k
Accepted

• 11
1 vote

### Complexity of the inverse modulo a composite number

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

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