As of May 31, 2023, we have updated our Code of Conduct.

# Tag Info

### Is there a theory that combines category theory/abstract algebra and computational complexity?

[Computational complexity and category theory] seem like such natural pairs. Given the prominence of computational complexity as a research field, if they were such natural bedfellows, maybe somebody ...

### Integer multiplication when one integer is fixed

I am not sure whether this is directly relevant to the question, but the following elementary result might be of interest. Given a fixed natural number $k$, the operation $n \to kn$ can be realized by ...
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 ...
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 ...
Accepted

### Commutative matrix multiplication algorithms

In answer to the "Update": yes, for any $c$, the existence of an $O(n^c)$ non-commutative algorithm for matrix multiplication is equivalent to the existence of an $O(n^c)$ commutative algorithm for ...

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

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