DIMACS Summer 2015

General Information

Name: Asa Goodwillie
Office: CoRE 434
Home inst.: Amherst College
E-mail: agoodwillie16 [at] amherst dot edu
Project: Boolean and Arithmetic Circuit Complexity
Mentor: Eric Allender

Project Description

The theory of circuit complexity provides tools (namely, circuit complexity classes) for understanding the relative computational complexity of problems low in the complexity hierarchy (i.e., beneath P). Boolean circuit classes are defined in terms of abstract circuits whose nodes are gates computing logical functions (AND, OR, NOT, and a few others), while arithmetic circuit classes are defined in terms of circuits whose nodes compute algebraic operations (addition and multiplication) over an underlying algebraic structure (in practice often a finite field). The project of relating these two families of circuit classes and understanding the structure of the circuit complexity hierarchy is still in progress, and we are seeking to learn more about the relationships between these classes.

Weekly Log

Week 1
I have been reading a paper ("Dual VP Classes", Allender, Gál, and Mertz) that describes some relationships between certain complexity classes defined in terms of Boolean and arithmetic circuits. I am trying to work out slight generalizations of some of the results in this paper, particularly two "degree reduction" theorems which show that under certain circumstances no expressive power is lost by restricting the fan-in (i.e., number of inputs) to particular gates in the circuits in question. I have also been reading various other papers (some of which contain results cited in the first paper) in order to better understand the work that predates and underlies the theorems I am trying to expand upon.
Week 2
I am continuing to work on the generalizations described above. I am now also working on generalizing another theorem, which relates arithmetic circuit classes defined over finite fields to more familiar Boolean classes augmented with so-called "counting" gates. We want to prove a similar theorem involving arithmetic circuit classes defined over the rings of integers modulo m, for all values of m.
Week 3
I spent most of this week trying to prove characterizations of the arithmetic classes over ℤ/mℤ described above in terms of Boolean circuit classes. I have not yet had as much success as I had hoped in understanding these classes, but the ways in which my attempts at proofs have failed have at least been informative, and I think I have a stronger sense of where the difficulties lie now.
Week 4
I have proven a minor result that lets us describe the arithmetic circuit classes VP and ΛP over ℤ/mℤ in terms of the special case in which the modulus m is a prime power. In some sense, this reduces the problem of finding Boolean characterizations of VP and ΛP over ℤ/mℤ to the problem of finding such Boolean characterizations for VP and ΛP over ℤ/pkℤ, where p is a prime.
Week 5
I have now figured out the prime power modulus cases of VP and ΛP mentioned above, and I have been working on writing up all of this material in one document in order to make sure that I really understand how all of these pieces fit together. I am also reading some papers on a slightly different topic (though still related to these circuit classes) which my mentor suggested might be interesting.
Week 6
I spent this week working on a conjecture (proposed in the paper mentioned above) about logspace reducibility between some of these Boolean and arithmetic classes. I have not had any success, though I think my attempts to prove the conjecture are helping me to get a better intuitive grasp on the relationships between these classes.
Week 7
I spent more time on the logspace reducibility material this week, but I have not made any further progress. I have spent most of my time this week preparing my presentation for Friday and revising my write-up of the VP and ΛP material from earlier in the summer. On Monday we leave for Prague.