5 ms·

Besides crypto. What applications does Abstract Algebra have in CS?

dkarapetyan 10y ago
Monoids, groups, rings, fields, etc. are all very relevant to cryptography. In general algebraic constructions come up more often than you might think. The idea of a homomorphism though not specific to algebra is prevalent in almost any formal domain. Compilers by and large can be considered homomorphisms that preserve certain semantic properties which if you dig deep enough can be expressed as algebraic structures: http://www.logicmatters.net/resources/pdfs/Galois.pdf http://www.logicmatters.net/resources/pdfs/Galois.pdf. Developing an intuition for all those things is best accomplished by studying abstract algebra.
- dualogy 10y ago
  Thanks for the link, the whole site (logicmatters.net) seems awesome, aka for me worth bookmarking for future study!
  - Smaug123 10y ago
    Smith is a great expositor. I had the joy of participating in a category theory reading group with him; he really knows his stuff. It's refreshing to be taught by a mathematician/philosopher rather than simply a mathematician.
- jinfiesto 10y ago
  Monoids aren't just relevant to cryptography. Any structure with an associative "+" operator forms a monoid (technically semi-group, but whatevs.) Lists are a prime example.
Bahamut 10y ago
Category theory is considered a field that is associated with algebraic skillsets. Edit: Crypography is specifically associated with algebraic number theory. Abstract algebra is also used in algebraic geometry, which also comes into play with facial recognition software, and maybe with fingerprinting as well.
- hackernewsacct 10y ago
  Every reply to my parent question has been excellent. What beginner resources do you recommend for learning category theory and its applications to programming?
  - mathgenius 10y ago
    I'm not sure there is any good resources for CT applied to CS. But anyway, check this out: http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of-algebraic-data-types-part-iii/ http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of... There's alot of category theory implicit in these ideas. You can learn the abstract approach later on, after you have seen a bunch of examples.
  - tomku 10y ago
    https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ https://bartoszmilewski.com/2014/10/28/category-theory-for-p...
  - ooqr 10y ago
    I'd suggest learning it via Haskell or maybe Scala if you've found programming helps your understanding of mathematics as I have. Learning via doing, internalizing by example, then diving deeper into the then-easier theory is how I like to go about things.
  - deleted 10y ago
    [deleted]
  - posterboy 10y ago
    the book in the article you are posting under, perhaps. just a hunch :)
AnimalMuppet 10y ago
Integer arithmetic in hardware (and many languages) is a ring. If I understand correctly, groups are the basis of some error correction codes. Monads are used for many things in functional programming.
- umanwizard 10y ago
  Do you mean to say a finite ring? "Pure" integer arithmetic in math (without any notion of overflow or wrapping) is a ring also, so I'm not sure what distinction you're making by saying "in hardware".
  - AnimalMuppet 10y ago
    Yes, a finite ring. There are languages that overflow from hardware integers into some kind of BigNum automatically. Those languages are not finite rings. (Well, OK, they're finite in the sense that eventually the memory space will be exhausted...)
    - umanwizard 10y ago
      yep, but they're still rings :)
Ixiaus 10y ago
It has a lot of application in functional programming languages, thinking of my programs algebraically has had a meaningful effect on what feels like "clearer expression of thought" in my code.
swordswinger12 10y ago
Most of the modern theory of error-correcting codes has its roots in abstract algebra. It's also important in theory - Babai's recent celebrated quasipolynomial algorithm for graph isomorphism relies on group theory. Most of the recent results in cryptographic obfuscation also rely on group theory because they encode circuits as permutation matrices using Barrington's theorem.
adenadel 10y ago
Some of the applications mentioned in this book are: -cryptography -algebraic coding theory -Burnside's lemma -molecular symmetry -design of software for parallel processors -lattices and Boolean algebras applied to logic, circuit theory, and probability -Galois theory
catnaroek 10y ago
As Stepanov said: “[Generic] algorithms are defined on algebraic structures”. He even gives an example: “I realized that a parallel reduction algorithm is associated with a semigroup structure type”. If you care about algorithms being maximally reusable (as in “just reuse”, rather than “tweak and reuse”), you definitely want to adopt an abstract-algebraic mindset. Source: http://www.stlport.org/resources/StepanovUSA.html http://www.stlport.org/resources/StepanovUSA.html
Drup 10y ago
I would tend to say: It's the basis of everything. Here are some examples that were not given in other comments: - Graph theory is pretty algebra-heavy, and graphs are everywhere. - Static analysis, in particular abstract interpretation, relies heavily on vector spaces and various algebraic structures. - All the "highly functional" structures (you know, monads and the like) are an off-shot branch of algebra. - Patch theory (git, darcs and other versioning systems that rely on patches). You get nice stuff if you use algebraic properties (such as having your patch commutes and things like that).
- jinfiesto 10y ago
  To extend the "functional structures" comment, monoids are literally everywhere in software.
cpsempek 10y ago
I don't know about very specific applications, but I think the field itself and is very complimentary to CS, especially when considering finite or discrete structures. As it's name suggests, abstract algebra abstracts "nice" properties of, e.g., integers and formalizes them in a very concise and general manner. Modern abstract algebra is deeply tied to category theory, and so now these "nice" properties get abstracted even further out to maps between objects, and as maps between categories (i.e., functors). As such abstract algebra is tied to functional programming on some level (I know nothing about this connection though). Linear algebra is a subfield of abstract algebra, and lots of general theorems about what classes of matrices are diagonalizable, or what their eigenvalues look like, etc. are within the purview of abstract algebra. These types of results are relevant to many algorithms, e.g., page rank. Aside from that, I think abstract algebra is quite a beautiful field in its own right. Two books I would recommend are Artin's Abstract Algebra (as an intro) and Lang's Algebra (more advanced, good bridge into the category theory perspective).
- semigroupoid 10y ago
  I second the recommendation for Artin's Algebra. I'd also recommend Paolo Aluffi's Algebra: Chapter 0, which is a nice alternative to Lang and also uses category theory right from the beginning and doesn't require many prerequisites. [0] https://www.amazon.com/Algebra-Chapter-Graduate-Studies-Mathematics/dp/0821847813/ https://www.amazon.com/Algebra-Chapter-Graduate-Studies-Math...
axlprose 10y ago
One way to view it, is that all other fields with the word "algebra" in them, are applications of Abstract Algebra. That includes Linear Algebra, Relational Algebra, and Boolean Algebra, which you might already be familiar with and know their relevance to CS.
imh 10y ago
Followup question: Are there good applied books that cover examples in broader fields than just crypto and coding theory?
platform 10y ago
abstract algebra is foundation for a) arithmetic as applied to 'Classes'. Eg overloading arithmetic operators that work on custom classes -- is, in a way, what abstract algebra does . b) Interval arithmetic. For example alen algebra applied to arithmetic of time intervals c) relational database theory as relates to various ways to construct functions on relations. d) type theory (see https://homotopytypetheory.org/book/ https://homotopytypetheory.org/book/ ) e) combinatorics and linear programming (basically being able to express recursive and generative constructs, and reason about them).
- Smaug123 10y ago
  Though note that HoTT is not the only approach to type theory; there are many others.
chas 10y ago
I think that Abstract Algebra has the same relationship with CS as Linear Algebra has with the theory of most engineering disciplines. That is to say that in computer science, Abstract Algebra is the natural setting to define and decompose problems and design their solutions. For a specific example, CRDTs are a fundamentally algebraic approach to problem solving in computer science. They were discussed recently on HN here. [0] If you want to go further down that rabbit hole, Joseph Goguen spent a large portion of his career working on applications of Abstract Algebra to computer science. He produced a category-theory-focused introduction here. [1] [0] https://news.ycombinator.com/item?id=13803843 https://news.ycombinator.com/item?id=13803843 [1] https://www.cs.ox.ac.uk/files/3395/PRG72.pdf https://www.cs.ox.ac.uk/files/3395/PRG72.pdf
tptacek 10y ago
Crypto is probably a better way to learn abstract algebra than the other way around, for whatever that's worth. You don't need more than a surface level understanding of abstract algebra to do fairly serious crypto work, but a lot of abstract algebra made more sense to me after a few years of crypto.
madhadron 10y ago
Off the topic of my head, pretty much everything to know about consistency in distributed systems boils down to semilattices.
EdwardCoffin 10y ago
Guy Steele [1] sometimes mentions it. He gave an interesting Google Tech Talk called Four Solutions to a Trivial Problem [2], and at 1:59 [3] he said: Also, algebraic properties are important. I've got a background in applied algebra, and I think that has informed my programming. And I think that making programmers aware of algebraic properties of their code, and communicating some of those properties to the compiler, may be worthwhile. The language Fortress [4], which he was one of the language designers of, allowed one to explicitly provide the compiler with such information - you could say that a certain operation was distributive or associative for instance, and the compiler could then do some refactorings and optimizations taking this knowledge into account. [1] https://en.wikipedia.org/wiki/Guy_L._Steele_Jr https://en.wikipedia.org/wiki/Guy_L._Steele_Jr. [2] https://youtu.be/ftcIcn8AmSY https://youtu.be/ftcIcn8AmSY [3] https://youtu.be/ftcIcn8AmSY?t=1m59s https://youtu.be/ftcIcn8AmSY?t=1m59s [4] https://en.wikipedia.org/wiki/Fortress_(programming_language) https://en.wikipedia.org/wiki/Fortress_(programming_language...
- FullyFunctional 10y ago
  GHC Haskell (not standard Haskell) supports this and it's heavily used. Look for "Rewrite rules".

Monoids, groups, rings, fields, etc. are all very relevant to cryptography. In general algebraic constructions come up more often than you might think. The idea of a homomorphism though not specific to algebra is prevalent in almost any formal domain. Compilers by and large can be considered homomorphisms that preserve certain semantic properties which if you dig deep enough can be expressed as algebraic structures: http://www.logicmatters.net/resources/pdfs/Galois.pdf http://www.logicmatters.net/resources/pdfs/Galois.pdf. Developing an intuition for all those things is best accomplished by studying abstract algebra.

dualogy 10y ago
Thanks for the link, the whole site (logicmatters.net) seems awesome, aka for me worth bookmarking for future study!
- Smaug123 10y ago
  Smith is a great expositor. I had the joy of participating in a category theory reading group with him; he really knows his stuff. It's refreshing to be taught by a mathematician/philosopher rather than simply a mathematician.
jinfiesto 10y ago
Monoids aren't just relevant to cryptography. Any structure with an associative "+" operator forms a monoid (technically semi-group, but whatevs.) Lists are a prime example.

Bahamut 10y ago

Category theory is considered a field that is associated with algebraic skillsets. Edit: Crypography is specifically associated with algebraic number theory. Abstract algebra is also used in algebraic geometry, which also comes into play with facial recognition software, and maybe with fingerprinting as well.

hackernewsacct 10y ago
Every reply to my parent question has been excellent. What beginner resources do you recommend for learning category theory and its applications to programming?
- mathgenius 10y ago
  I'm not sure there is any good resources for CT applied to CS. But anyway, check this out: http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of-algebraic-data-types-part-iii/ http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of... There's alot of category theory implicit in these ideas. You can learn the abstract approach later on, after you have seen a bunch of examples.
- tomku 10y ago
  https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ https://bartoszmilewski.com/2014/10/28/category-theory-for-p...
- ooqr 10y ago
  I'd suggest learning it via Haskell or maybe Scala if you've found programming helps your understanding of mathematics as I have. Learning via doing, internalizing by example, then diving deeper into the then-easier theory is how I like to go about things.
- deleted 10y ago
  [deleted]
- posterboy 10y ago
  the book in the article you are posting under, perhaps. just a hunch :)

AnimalMuppet 10y ago

Integer arithmetic in hardware (and many languages) is a ring. If I understand correctly, groups are the basis of some error correction codes. Monads are used for many things in functional programming.

umanwizard 10y ago
Do you mean to say a finite ring? "Pure" integer arithmetic in math (without any notion of overflow or wrapping) is a ring also, so I'm not sure what distinction you're making by saying "in hardware".
- AnimalMuppet 10y ago
  Yes, a finite ring. There are languages that overflow from hardware integers into some kind of BigNum automatically. Those languages are not finite rings. (Well, OK, they're finite in the sense that eventually the memory space will be exhausted...)
  - umanwizard 10y ago
    yep, but they're still rings :)

Ixiaus 10y ago

It has a lot of application in functional programming languages, thinking of my programs algebraically has had a meaningful effect on what feels like "clearer expression of thought" in my code.

swordswinger12 10y ago

Most of the modern theory of error-correcting codes has its roots in abstract algebra. It's also important in theory - Babai's recent celebrated quasipolynomial algorithm for graph isomorphism relies on group theory. Most of the recent results in cryptographic obfuscation also rely on group theory because they encode circuits as permutation matrices using Barrington's theorem.

adenadel 10y ago

Some of the applications mentioned in this book are: -cryptography -algebraic coding theory -Burnside's lemma -molecular symmetry -design of software for parallel processors -lattices and Boolean algebras applied to logic, circuit theory, and probability -Galois theory

catnaroek 10y ago

As Stepanov said: “[Generic] algorithms are defined on algebraic structures”. He even gives an example: “I realized that a parallel reduction algorithm is associated with a semigroup structure type”. If you care about algorithms being maximally reusable (as in “just reuse”, rather than “tweak and reuse”), you definitely want to adopt an abstract-algebraic mindset. Source: http://www.stlport.org/resources/StepanovUSA.html http://www.stlport.org/resources/StepanovUSA.html

Drup 10y ago

I would tend to say: It's the basis of everything. Here are some examples that were not given in other comments: - Graph theory is pretty algebra-heavy, and graphs are everywhere. - Static analysis, in particular abstract interpretation, relies heavily on vector spaces and various algebraic structures. - All the "highly functional" structures (you know, monads and the like) are an off-shot branch of algebra. - Patch theory (git, darcs and other versioning systems that rely on patches). You get nice stuff if you use algebraic properties (such as having your patch commutes and things like that).

jinfiesto 10y ago
To extend the "functional structures" comment, monoids are literally everywhere in software.

cpsempek 10y ago

I don't know about very specific applications, but I think the field itself and is very complimentary to CS, especially when considering finite or discrete structures. As it's name suggests, abstract algebra abstracts "nice" properties of, e.g., integers and formalizes them in a very concise and general manner. Modern abstract algebra is deeply tied to category theory, and so now these "nice" properties get abstracted even further out to maps between objects, and as maps between categories (i.e., functors). As such abstract algebra is tied to functional programming on some level (I know nothing about this connection though). Linear algebra is a subfield of abstract algebra, and lots of general theorems about what classes of matrices are diagonalizable, or what their eigenvalues look like, etc. are within the purview of abstract algebra. These types of results are relevant to many algorithms, e.g., page rank. Aside from that, I think abstract algebra is quite a beautiful field in its own right. Two books I would recommend are Artin's Abstract Algebra (as an intro) and Lang's Algebra (more advanced, good bridge into the category theory perspective).

semigroupoid 10y ago
I second the recommendation for Artin's Algebra. I'd also recommend Paolo Aluffi's Algebra: Chapter 0, which is a nice alternative to Lang and also uses category theory right from the beginning and doesn't require many prerequisites. [0] https://www.amazon.com/Algebra-Chapter-Graduate-Studies-Mathematics/dp/0821847813/ https://www.amazon.com/Algebra-Chapter-Graduate-Studies-Math...

axlprose 10y ago

One way to view it, is that all other fields with the word "algebra" in them, are applications of Abstract Algebra. That includes Linear Algebra, Relational Algebra, and Boolean Algebra, which you might already be familiar with and know their relevance to CS.

imh 10y ago

Followup question: Are there good applied books that cover examples in broader fields than just crypto and coding theory?

platform 10y ago

abstract algebra is foundation for a) arithmetic as applied to 'Classes'. Eg overloading arithmetic operators that work on custom classes -- is, in a way, what abstract algebra does . b) Interval arithmetic. For example alen algebra applied to arithmetic of time intervals c) relational database theory as relates to various ways to construct functions on relations. d) type theory (see https://homotopytypetheory.org/book/ https://homotopytypetheory.org/book/ ) e) combinatorics and linear programming (basically being able to express recursive and generative constructs, and reason about them).

Smaug123 10y ago
Though note that HoTT is not the only approach to type theory; there are many others.

chas 10y ago

I think that Abstract Algebra has the same relationship with CS as Linear Algebra has with the theory of most engineering disciplines. That is to say that in computer science, Abstract Algebra is the natural setting to define and decompose problems and design their solutions. For a specific example, CRDTs are a fundamentally algebraic approach to problem solving in computer science. They were discussed recently on HN here. [0] If you want to go further down that rabbit hole, Joseph Goguen spent a large portion of his career working on applications of Abstract Algebra to computer science. He produced a category-theory-focused introduction here. [1] [0] https://news.ycombinator.com/item?id=13803843 https://news.ycombinator.com/item?id=13803843 [1] https://www.cs.ox.ac.uk/files/3395/PRG72.pdf https://www.cs.ox.ac.uk/files/3395/PRG72.pdf

tptacek 10y ago

Crypto is probably a better way to learn abstract algebra than the other way around, for whatever that's worth. You don't need more than a surface level understanding of abstract algebra to do fairly serious crypto work, but a lot of abstract algebra made more sense to me after a few years of crypto.

madhadron 10y ago

Off the topic of my head, pretty much everything to know about consistency in distributed systems boils down to semilattices.

EdwardCoffin 10y ago

Guy Steele [1] sometimes mentions it. He gave an interesting Google Tech Talk called Four Solutions to a Trivial Problem [2], and at 1:59 [3] he said: Also, algebraic properties are important. I've got a background in applied algebra, and I think that has informed my programming. And I think that making programmers aware of algebraic properties of their code, and communicating some of those properties to the compiler, may be worthwhile. The language Fortress [4], which he was one of the language designers of, allowed one to explicitly provide the compiler with such information - you could say that a certain operation was distributive or associative for instance, and the compiler could then do some refactorings and optimizations taking this knowledge into account. [1] https://en.wikipedia.org/wiki/Guy_L._Steele_Jr https://en.wikipedia.org/wiki/Guy_L._Steele_Jr. [2] https://youtu.be/ftcIcn8AmSY https://youtu.be/ftcIcn8AmSY [3] https://youtu.be/ftcIcn8AmSY?t=1m59s https://youtu.be/ftcIcn8AmSY?t=1m59s [4] https://en.wikipedia.org/wiki/Fortress_(programming_language) https://en.wikipedia.org/wiki/Fortress_(programming_language...

FullyFunctional 10y ago
GHC Haskell (not standard Haskell) supports this and it's heavily used. Look for "Rewrite rules".