# Tag Info

### Algebra oriented branch of theoretical computer science

There have been recent developments in dependent type theory which relate type systems to homotopy types. This is now a relatively small field, but there is a lot of exciting work being done right ...
• 13.2k

### Algebra oriented branch of theoretical computer science

Algebraic geometry is used heavily in algebraic complexity theory and in particular in geometric complexity theory. Representation theory is also crucial for the latter, but it's even more useful when ...
• 35.8k
Accepted

### List of number theoretic or algebraic problems in various complexity classes

Algebraic geometry Noether's Normalization Lemma (NNL) for explicit varieties is currently only known to be in $\mathsf{EXPSPACE}$ (like general NNL), but is conjectured to be in $\mathsf{P}$ (and is ...
• 35.8k

### Algebra oriented branch of theoretical computer science

Your knowledge of field theory would be useful in cryptography, while category theory is heavily used in the research on programming languages and typing systems, both of which are closely related to ...
• 10.3k

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

### Complexity of computing the order of a permutation group

The order of permutation groups can be computed in polynomial-time. In fact, I believe even in $\mathsf{NC}$ and also nearly linear Las Vegas time. See, e.g., the book by Seress. For reference, ...
• 35.8k
Accepted

### Are There Highly Symmetric NP- or P-complete Languages?

For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-...
• 35.8k

### Algebra oriented branch of theoretical computer science

Field theory and algrebraic geometry would be useful in topics related to error correcting codes, both in the classical setting as well as in studying locally decodable codes and list decoding. I ...
Accepted

### On the realisation of monoids as syntactic monoids of languages

It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without ...
• 7,653