# Applications of algebraic geometry in Boolean complexity

Representing boolean functions by polynomials or rational functions either perfectly or approximately is an important topic while polynomials and rational functions is the body of algebraic geometry. Why is algebraic geometry not that applicable to this area of complexity theory? Or atleast what are some of the important papers in representing boolean functions that uses algebraic geometry?

• A related question on cstheory: Papers on relation between computational complexity and algebraic geometry/topology? – Marzio De Biasi Nov 20 '14 at 19:43
• Are you aware of the Mulmuley-Sohoni geometric complexity theory program? – Sasho Nikolov Nov 20 '14 at 20:24
• @SashoNikolov yes... but permanent-determinant, matrix-multiplication deal with 1) specific functions 2) and are so far abstracted away from concrete Boolean functions. – 1.. Nov 20 '14 at 20:33
• @Turbo: Check out Valiant's work from the 70s and 80s in which he introduced VP and VNP, as well as Burgisser's paper "Cook's versus Valiant's hypothesis" and you will see that permanent vs determinant is not so far from Boolean functions. Same goes for matrix multiplication, via Boolean matrix multiplication and the myriad Boolean problems whose runtime is closely related to $O(n^{\omega})$, the time complexity of matrix multiplication. Also, you seem to be trying to indicate a difference between "specific" and "concrete" functions - perhaps you could elaborate? – Joshua Grochow Nov 20 '14 at 20:51
• @Turbo: Some of the apps of AG in CC work by representing a Boolean function by a polynomial and studying that, but many work in slightly or more-than-slightly different ways. Without knowing more about what you have in mind re: representations by polynomials/rational functions, it's a bit hard to answer your last comment precisely. I will mention Strassen's result that for computing polynomials by algebraic circuits, divisions don't help (up to polynomial size). This is getting into discussion territory though; I'd be happy to discuss privately by email if you prefer. – Joshua Grochow Nov 21 '14 at 20:19