<p>In addition to the Geometric Complexity Theory Program already mentioned by Sasho Nikolov (see e.g. <a href="http://gct.cs.uchicago.edu/">here</a>, and - shameless self plug, but has tons of references on uses of AG in complexity - <a href="http://tuvalu.santafe.edu/~jgrochow/grochow-gct-unity.pdf">here</a>), there's also:</p>

<ul>
<li><p>Work on matrix multiplication (Strassen's work especially come to mind, as well as the more recent GCT-style work of Burgisser and Ikenmeyer, but also some other stuff in between)</p></li>
<li><p>Mulmuley's "P vs NC" result (this is a <em>Boolean</em> result - if you need convincing I'm happy to), which can be seen as building off of Ben-Or's sorting lower bound and others</p></li>
<li><p>Work on derandomizing polynomial identity testing (several papers of M. Agrawal come to mind). (Which, in retrospect, is <a href="http://gct.cs.uchicago.edu/gct5.pdf">deeply related to GCT</a>.)</p></li>
<li><p>Coding theory (there's a whole "subfield" on AG codes)</p></li>
</ul>

CC BY-SA 3.0
2014-11-20T21:08:05.373Z
2014-11-20T21:08:05.373Z
Joshua Grochow
<p>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?</p>

CC BY-SA 3.0
2014-11-20T19:43:23.380Z
A related question on cstheory: [Papers on relation between computational complexity and algebraic geometry/topology?](http://cstheory.stackexchange.com/q/7958/3247)
Marzio De Biasi
CC BY-SA 3.0
2014-11-20T20:24:01.387Z
Are you aware of the Mulmuley-Sohoni geometric complexity theory program?
Sasho Nikolov
CC BY-SA 3.0
2014-11-20T20:33:40.887Z
@SashoNikolov yes... but permanent-determinant, matrix-multiplication deal with 1) specific functions 2) and are so far abstracted away from concrete Boolean functions.
Turbo
CC BY-SA 3.0
2014-11-20T20:51:28.080Z
@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
CC BY-SA 3.0
2014-11-20T22:28:19.977Z
@JoshuaGrochow let me ask you one more question before I clarify further. are these related to representations by rational functions as well? If so, give me a good reference. I need to look at it before I can clarify further.
Turbo
CC BY-SA 3.0
2014-11-21T20:19:38.627Z
@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
<survey>
Applications of algebraic geometry in Boolean complexity
Turbo
# Applications of algebraic geometry in Boolean complexity

(Asked by: username_0 on 2014-11-20)

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?

**Tags:** survey

> **Comments:**
> **username_1**: A related question on cstheory: [Papers on relation between computational complexity and algebraic geometry/topology?](http://cstheory.stackexchange.com/q/7958/3247)  
> **username_2**: Are you aware of the Mulmuley-Sohoni geometric complexity theory program?  
> **username_0**: @SashoNikolov yes... but permanent-determinant, matrix-multiplication deal with 1) specific functions 2) and are so far abstracted away from concrete Boolean functions.  
> **username_3**: @username_0: 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?  
> **username_0**: @JoshuaGrochow let me ask you one more question before I clarify further. are these related to representations by rational functions as well? If so, give me a good reference. I need to look at it before I can clarify further.  
> **username_3**: @username_0: 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.  

---

## 1 answers

### Answer by username_3 on 2014-11-20. Score: 6

In addition to the Geometric Complexity Theory Program already mentioned by username_2 (see e.g. [here](http://gct.cs.uchicago.edu/), and - shameless self plug, but has tons of references on uses of AG in complexity - [here](http://tuvalu.santafe.edu/~jgrochow/grochow-gct-unity.pdf)), there's also:

* Work on matrix multiplication (Strassen's work especially come to mind, as well as the more recent GCT-style work of Burgisser and Ikenmeyer, but also some other stuff in between)
* Mulmuley's "P vs NC" result (this is a *Boolean* result - if you need convincing I'm happy to), which can be seen as building off of Ben-Or's sorting lower bound and others
* Work on derandomizing polynomial identity testing (several papers of M. Agrawal come to mind). (Which, in retrospect, is [deeply related to GCT](http://gct.cs.uchicago.edu/gct5.pdf).)
* Coding theory (there's a whole "subfield" on AG codes)


---

