33
$\begingroup$

I have a very strong base in algebra, namely

  • commutative algebra,
  • homological algebra,
  • field theory,
  • category theory,

and I am currently learning algebraic geometry.

I am a math major with an inclination to switch to theoretical computer science. Keeping the above mentioned fields in mind, which field would be the most appropriate field in theoretical computer science to which to switch? That is, in which field can the theory and mathematical maturity obtained by pursuing the above fields be used to one's advantage?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Is the study of fields considered part of algebra? There are some on math.se who think not. $\endgroup$
    – alancalvitti
    Commented Sep 26, 2014 at 17:01
  • 1
    $\begingroup$ It is offered in many institutes here as second level algebra course and many famous books on algebra like dummit and foote's abstract algebra contains significant material on Filed theory ... $\endgroup$
    – spaceman_spiff
    Commented Sep 28, 2014 at 8:13

12 Answers 12

Reset to default
27
$\begingroup$

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 now, and potentially a lot of low hanging fruit, most notably in porting results from algebraic topology and homological algebra and formalizing the notion of higher inductive types.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So what I think you are trying to say is, HoTT. (And on a more practical level, I would assume PL and FM as fields that can potentially utilize HoTT.) $\endgroup$
    – Max von Hippel
    Commented Apr 21, 2020 at 3:32
25
$\begingroup$

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 combined with algebraic geometry and homological algebra.

Improve this answer
$\endgroup$
15
$\begingroup$

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 the foundations of mathematics.

Improve this answer
$\endgroup$
11
$\begingroup$

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 believe this goes back to work on the Reed-Solomon and Reed-Muller codes, which was then generalized to algebraic geometric codes. See for example, this book chapter on the classical coding theory view of algebraic geometric codes, this brief survey on locally decodable codes, and this famous paper about list-decoding Reed-Solomon and, more generally, algebraic-geometry codes.

Improve this answer
$\endgroup$
7
$\begingroup$

There are some problems in computational learning theory, machine learning and computer vision that can be solved using commutative algebra and algebraic geometry. For instance, convergence of the Belief Propagation algorithm, a message passing algorithm for Bayesian inference, can be formulated in terms of characterizing the affine variety of system of polynomial equations.

Improve this answer
$\endgroup$
6
$\begingroup$

Have you thought about looking at computer algebra? Axiom is a computer algebra system where the type system is modelled after Category Theory (or Universal Algebra, depending on your view). There are two further derivatives of Axiom FriCAS and OpenAxiom.

If you're interested in Category Theory, then the type system may be one thing to look at.

In Axiom, every "item" (e.g. "1", "5*x**2 + 1") is an element of a Domain. A "Domain" is an Axiom object declared to be a member of a particular Category (e.g. Integer, Polynomial(Integer). An Axiom Category is an Axiom object declared to be a member of the distinguished symbol "Category" (e.g. Ring, Polynomial(R,E,V)).

There is an inheritance lattice for the multiple-inheritance amongst Categories. e.g. The Category Monad inherits from SetCategory, Monoid from Monad, Group from Monoid, etc., etc.

There is also a higher-order polymorphism, a bit like Generics in Java.

Several actions within Axiom can be viewed as Functors, but that would be rather a lot to go into here!

If you just wish to use Axiom without worrying about Category Theory, as a typical end user, then a symbolic computation system is exactly the right piece of software for looking into individual algebras.

Improve this answer
$\endgroup$
5
$\begingroup$

Here are a lot of interesting answer, but nobody mentioned that every language $L \subseteq X^{\ast}$ is naturally associated with a monoid structure via the Nerode-Myhill congruence relation.

The following people have used this algebraic view in the case of regular languages: Samuel Eilenberg on Automata Theory, Jean Berstel, Jean-Eric pin, Marcel Schützenberg and Krohn-Rhodes Theory.

Also there is nontrivial algebra involved in the work around the Cerny conjecture, most of it is quite combinatorial. But more recently I have seen more done with linear algebra, ring theory and representation theory, look up to work Benjamin Steinberg and Jorge Almeida.

By the way, you can come along quite good in these areas with Semigroup-, Monoid- and Group theory, but Category theory and Homotopy Theory are not used that much in this area. But maybe interesting to note that S. Eilenberg was one of the founding fathers of Category Theory, despite this was before he was involved into Automata Theory.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It could be also interesting to take a look at tree languages, rather than word languages. The long standing open problem is to characterize the expressive power of First-Order Logic on trees in terms of some algebraic object associated with it (mentioned in "Some Open Problems in Automata and Logic" in ACM SIGLOG News). For further reading I will recommend papers by Mikołaj Bojańczyk and Howard Straubing. $\endgroup$
    – Bartosz Bednarczyk
    Commented Apr 7, 2018 at 14:11
4
$\begingroup$

Brent Yorgey's thesis, while still just a draft, does an amazing job at explaining why your interests are relevant to TCS.

Here is Joyal's talk this past April on related material.

Improve this answer
$\endgroup$
3
  • 12
    $\begingroup$ Not sure what the customs are here, but on Stack Overflow this answer would probably get deleted as link-only answer very soon. Will you please provide a summary of how the link answers the question, not only that it does? Links tend to break over time and without the link, your answer would be almost useless. $\endgroup$
    – Palec
    Commented Sep 23, 2014 at 19:16
  • 1
    $\begingroup$ Don't worry. I wrote myself a reminder to update it with his final draft. $\endgroup$
    – Chad Brewbaker
    Commented Sep 24, 2014 at 20:34
  • 4
    $\begingroup$ @ChadBrewbaker But, still, your answer is essentially just two links. Even if you promise to keep those links current (which is a noble goal and much appreciated, but surely doomed to failure), it's a poor answer. $\endgroup$
    – David Richerby
    Commented Sep 24, 2014 at 20:57
3
$\begingroup$

I don't know if you have considered industry, but the company Ayasdi is doing amazing work applying a lot of homotopy and other applied topological methods within data science. They blend a lot of theory with applications. Basically, to see what they are up to, look at the Stanford Comptop website. (The majority of people came from there).

Improve this answer
$\endgroup$
2
$\begingroup$

In addition to what everybody else said (I guess the biggest application of these branches is indeed in type systems):

  • Lattice theory and partial orders in general are applied quite a bit for analysis of behavior of distributed systems, and for dataflow analysis in compilers.
  • I also saw Galois connections applied to machine learning (in particular text classification: the Galois connection between subsets of left and right vertices of a bipartite document/word graph allowed to dramatically speed up an algorithm).
Improve this answer
$\endgroup$
1
$\begingroup$

The connections between Algebra and Theoretical Computer Science are very strong. Nic Doye already mentioned Computer Algebra, but he didn't explicitly include the theory of rewriting systems, which is an essential part of Computer Algebra, with applications in automatic equation solving and automatic reasoning. String rewriting systems is an important sub-area, with applications in computational group theory. Check the book "String Rewriting Systems", by Ronald Book and Friedrich Otto, for instance.

There is also the connection between graph theory and algebra, which includes for example the well-developed spectral theory of graphs and complex networks, and also the the theory of graph symmetries (Cayley graps, vertex-transitive graphs, and other types of symmetric graphs, which are heavily used as models for interconnection networks in parallel computers). Check the book "Algebraic Graph Theory", by Chris Godsil and Gordon Royle, for an overview of the different topics.

Improve this answer
$\endgroup$
0
$\begingroup$

Check out the situation in computer vision. There are many topics, in particular, of algorithmic type, which the first three areas you list are very useful for.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.