BARC talk by Cornelius Brand

Wednesday, 12 June, Cornelius Brand, PhD student at Saarland University, Germany, will give a talk "Algorithms for the wedge product: Making nothing from something" 

Title:
Algorithms for the wedge product: Making nothing from something

Abstract:
"Some 170 years ago, Hermann Graßmann introduced the exterior algebra of a vector space. It has become a tool of striking ubiquity in physics, differential geometry, algebraic geometry, and countless other mathematical subfields. Recently, it made its debut also in algorithms for hard subgraph problems.  The wedge product from the title of this talk is connected to this as follows: Turning a vector space into an algebra requires, above all, making sense of the product of the elements of the vectors pace, i.e., vectors.  In the exterior algebra, this is accomplished by means of this very wedge product, which---roughly speaking---associates to a bunch of vectors, say k many vectors, the k-dimensional parallelotope that has the k vectors as its 'edges.'

Given its prominence, it is rather surprising that the wedge product is poorly understood from an algorithmic perspective, and has received little to no attention from any of the relevant research communities. (This, following Gian-Carlo Rota, seems to be a recurring theme, for as he put it: "The neglect of the exterior algebra is the mathematical tragedy of our century.")
In particular, it is closely related to variants of the, in contrast, very well-understood subset convolutions, but curiously (and stubbornly) resists resolution by similar techniques.
Adding insult to injury, the best known algorithm for the problem proceeds as follows: To compute the wedge product, it computes instead a (seemingly) much harder product (namely the one of a so-called Clifford algebra, which are far more general objects than exterior algebras), then throws away a vast part of the answer to this harder problem, and what remains is then the wedge product.

In this talk, I will give an account of the problem, present the fastest known method of computing it, and point out connections to related problems, as well as indicate promising avenues towards improving upon the very unsatisfactory current state of affairs."

Cornelius Brand is PhD student at Saarland University