Hot answers tagged

47

My impression is that, by and large, traditional algebra is rather too specific for use in Computer Science. So Computer Scientists either use weaker (and, hence, more general) structures, or generalize the traditional structures so that they can fit them to their needs. We also use category theory a lot, which mathematicians don't think of as being part ...


40

A type $C$ has a logarithm to base $X$ of $P$ exactly when $C \cong P\to X$. That is, $C$ can be seen as a container of $X$ elements in positions given by $P$. Indeed, it's a matter of asking to what power $P$ we must raise $X$ to obtain $C$. It makes sense to work with $\mathop{log}F$ where $F$ is a functor, whenever the logarithm exists, meaning $\mathop{...


27

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


24

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.


23

My all-time favorite application of group theory in TCS is Barrington's Theorem. You can find an exposition of this theorem on the complexity blog, and Barrington's exposition in the comment section of that post.


18

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 in $\mathsf{P}$ assuming that PIT can be black-box derandomized). Update 4/18/18: It was recently shown that for the variety $\overline{\mathsf{VP}}$ it is in $...


17

You could try the notes from Madhu Sudan's course: Algebra and Computation


16

There is not a canonical such category, for the same reason there is no canonical category of computations. However, there are large and useful algebraic structures on data structures. One of the more general such structures, which is still nevertheless useful, is the theory of combinatorial species. A species is a functor $F : B \to B$, where $B$ is the ...


15

Groups, rings, fields, and modules are everywhere in computational topology. See especially Carlsson and Zomorodian's work [ex: 1] on (multidimensional) persistent homology, which is all about graded modules over principal ideal domains.


15

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.


14

Indeed, there is a different notion than isomorphism which is more useful in programming. It is called "behavioural equivalence" (sometimes called "observational equivalence") and it is established by giving a "simulation relation" between data structures rather than bijections. Algebraists came in and established an area called "algebraic data types" in ...


14

Here is a very nice, practical use: an algorithm for computing graph connectivity (from FOCS2011). To compute the s->t connectivity of a graph, the authors give an algorithm that assigns random vectors with entries drawn from a finite field to the out edges from s, then construct similar vectors for all of the edges in the graph by taking random linear ...


14

Finite automata in which the initial state is also the unique accepting state have the form $r^∗$, where $r$ is some regular expression. However, as J.-E. Pin points out below, the converse is not true: there are languages of the form $r^*$ which are not accepted by a DFA with a unique accepting state. Intuitively, given a sequence of states $q_0, \ldots, ...


12

[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 would have brought out the connection already? Wild speculation. Let me entertain the reader with thoughts about why a categorical rendering of ...


12

Universal algebra is an important tool in studying the complexity of constraint satisfaction problems. For example, the Dichotomy Conjecture states that, roughly speaking, a constraint satisfaction problem over a finite domain is either NP-complete or polynomial-time solvable. Note that by Ladner's theorem there are problems in NP which are not in P and ...


12

Lattices and fixed points are at the foundations of program analysis and verification. Though advanced results from lattice theory are rarely used because we are concerned with algorithmic issues such as computing and approximating fixed points, while research in lattice theory has a different focus (connections to topology, duality theory, etc). The initial ...


12

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, subgroups of $S_n$ (and algorithms related thereto) are typically called "permutation groups" rather than merely "subgroups (of $S_n$)". So you can google "...


12

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-complete language has a poly-time group action with few orbits, PH collapses. For, with this additional assumption about sampleability, the standard $\mathsf{coAM}$ ...


11

Here are two applications from a different part of TCS. Semirings are used for modelling annotations in databases (especially those needed for provenance), and often also for the valuation structures in valued constraint satisfaction. In both of these applications, individual values must be combined together in ways which lead naturally to a semiring ...


11

One possibily path into abstract algebra could be to look at it from point of view of cryptography, which is about algorithms on finite field. Fields are rings, and fields are also two groups coupled by simple laws. Field theory uses vector spaces in prominent position (Galois theory), so this angle should cover a lot of abstract algebra. The book A ...


11

There is a more general question on mathoverflow. I asked a similar question on CS.SE. jbapple provided a good answer. To quote "Necklaces, Convolutions, and X+Y", By Bremner et al. shows a $O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$ algorithm for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in the nonuniform linear decision ...


11

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


11

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 paywall it would be great. I requested the full-text on ResearchGate. Title: Which Finite Monoids are Syntactic Monoids of Rational omega-Languages. Authors: ...


11

In a more elementary way than Denis's answer, the following is extracted from Pippenger's "Theories of Computability", p.87, and immediate to check. Definition: Let $M$ be a monoid, and $Y \subseteq M$. Define the congruence relation $\equiv_Y$ over $M$ by $x \equiv_Y y$ iff $\big[\forall w, z \in M$, $wxz \in Y \Leftrightarrow wyz \in Y\big]$. Definition:...


11

From a programming language theory perspective, as opposed to the computability perspective other answers and comments have offered, C++ templates combined with concepts correspond to bounded polymorphism or constrained genericity. Concepts themselves correspond to the constraints or bounds placed on a type. A template is type-level function, parameterised ...


10

Rings, modules, and algebraic varieties are used in error correction and, more generally, coding theory. Specifically, there is an abstract error correcting scheme (algebraic-geometry codes) which generalizes Reed-Solomon codes and Chinese Remainder codes. The scheme is basically to take your messages to come from a ring R and encode it by taking its ...


10

An important subclass of this family is a sub-class of 0-reversible languages. A language is 0-reversible if the reversal of the minimal DFA for the language is also deterministic. The reversing operation is defined as swapping initial and final states, and inverting the edge relation of the DFA. This means that a 0-reversible language can have only one ...


10

The terminology rigid seems to be relatively new compared to the term disjunctive used in the late 70's (and probably before, I didn't check for earlier references). A subset $P$ of a monoid $M$ is disjunctive if and only if the syntactic congruence of $P$ in $M$ is the equality relation. Thus a monoid is the syntactic monoid of a language if and only if it ...


10

To my knowledge (which is definitely incomplete), there has been relatively little work on this, presumably because it requires assimilating two relatively intricate bodies of knowledge. However, little does not mean nonexistent. Thierry Coquand and his collaborators have written quite a few papers on the connections between commutative algebra and ...


9

You are working on your PhD. Saying "I am not well versed in $X$" is not an excuse. And if you're good, then saying "my advisor does not know $X$" is not an excuse either. You are using monoids where you should be using categories. Your monoid operations presupposes that you can combine any $\delta$'s together. But does this really make sense, for example, ...


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