1

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?

Turbo
  • 12,812
  • 1
  • 19
  • 68
  • A related question on cstheory: Papers on relation between computational complexity and algebraic geometry/topology? – Marzio De Biasi Nov 20 '14 at 19:43
  • 2
    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. – Turbo 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
  • @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 Nov 20 '14 at 22:28
  • 1
    @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

1 Answers1

6

In addition to the Geometric Complexity Theory Program already mentioned by Sasho Nikolov (see e.g. here, and - shameless self plug, but has tons of references on uses of AG in complexity - here), 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.)

  • Coding theory (there's a whole "subfield" on AG codes)

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228