4
$\begingroup$

Can you give examples of algorithms possessing the following two properties:
1. Solving a non-algebraic problem.
2. Relying on results in algebra.

For example, the paper http://people.csail.mit.edu/nickh/Publications/AlgebraicMatching/Algebraic-SIAM.pdf uses linear algebra to solve graph theoretic problems.

  • 0
    Do algorithms that operate over algebraic structures like groups, monoids, etc. count by your definition? Or do you only want things that directly rely on a result from algebra?2012-01-10

6 Answers 6

5

Primes is in P

4

Finding the intersection of two polynomial surfaces, a common problem in Computer-Aided Design, can be done using Gröbner basis techniques.

3

Coding theory is full of stuff that fits under this umbrella. For example, the algorithms that allow your scratched CD to play as if the scratch didn't exist rely on Reed-Solomon codes (see e.g. http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction). The properties of the particular codes used in CDs need properties of the field GF(256). Ultimately it relies on the fact that a polynomial of degree $n$ cannot have more than $n$ zeros in a field. IIRC $n=23$ is relevant in the CD-application.

2

(Does matrix algebra belong to what "algebra" means here?)

SVD can be applied to text classification.

One can store all document information in matrix $M=(m_{ij})$ (called term-frequency matrix): Each row stands for an article, each column stands for a word, and each entry $m_{ij}$ equals to some kind of word frequency measure (as used commonly, TF–IDF) of the $j$th word in the $i$th article. Perform SVD on matrix $M$ such that $M=U\Sigma V^*$, with the shape like: SVD

, where $U$, $\Sigma$ and $V$ are called term-concept vector matrix, singular values matrix and concept-document vector matrix, respectively. Now each row of $U$ can be viewed as one category of words with similar meanings, whose entries represent correlations (or importance) in the their own category, and each row of $V$ can be viewed as one category of articles with a certain topic, whose entries also act alike. Finally, $\Sigma$ denotes correlations between words and articles.

2

It occurred to me another one, famous and elementary: Angle trisection problem, which involves field extension

  • 0
    I see. OP seemed to want algorithms which exist, but I guess it will be useful to other readers.2011-06-07
1

Not strictly algorithmic, but probably the most famous example of algebraic technique in complexity theory is proof of $\mathsf{IP} = \mathsf{PSPACE}$.

A Boolean formula $\phi$ is converted to a multivariate polynomial $p$ over ${\mathbf F}_q$ which agrees with $\phi$ on $\{0,1\}^n$ (nonzero iff true) and to ensure honesty the verifier might evaluate the polynomial at any point of ${\mathbf F}_q^n$.