Christopher Hillar

 MSRI Research Member

 NSA Young Investigator

NSF Postdoctoral fellow

Addresses:
Redwood Center for Theoretical Neuroscience
156 Stanley Hall, MC# 3220
Berkeley, CA 94720-3220
Office: 573 Evans Hall
Phone: (510) 642-7252
FAX: (510) 642-7206


MSRI: Mathematical Sciences Research Institute
17 Gauss Way
Berkeley, CA 94720-5070
FAX: (510) 642-8609

Email(s): chillarmsri.org

Ph.D. U.C. Berkeley (Mathematics, 2001 - 2005)
B.S. Yale University (Mathematics, Computer Science, 2000)

my CV


NSF Joint Institutes Postdoctoral Fellowship: I was awarded this at MSRI with the following proposal. MSRI is awesome.

NSA Grant: I was awarded an NSA Young Investigators Grant. My proposal can be found here.

Talk on Grobner Bases and Applications: I recently gave a colloquium talk in the math department at Santa Clara University. Here are the slides.

I also gave a talk at an AMS Special Session on Rational sums of squares and applications. My slides are here.  

New: I will be a research member at MSRI from January - May, 2009, and a postdoc starting there Fall 09.

Open Problems: Since I am phasing out my math projects (a going out of business sale if you will), I will be putting together some notes on open problems (that should be fruitful).

(1) Rational LMI representations and rational sums of squares

Theoretical Neuroscience: I have a Joint Math Institutes Postdoc (technically through MSRI) at the Redwood Center for Theoretical Neuroscience at UC Berkeley. Some projects so far:

(1) with Koepsell and Cadieu, we are working on the mathematics of a new multivariate phase distribution.

(2) With Guy Isely and Fritz Sommer (continuing on work with Will Coulter), I am working on sparse coding combined with compressed sensing. (ICASSP 2010 accepted submission pdf)

(3) With Lek-Heng Lim, we are working on some complexity problems involving tensors. Most tensor problems are NP-Hard, submitted to STOC 2010. pdf (a journal article version is in preparation).

(4) With D. Rhea, we are working on statistical learning theory, causality, and action (very preliminary at this point)

(5) with R. Mehta, F. Sommer (continuing on work with P. Kanerva), we are working on online associative learning models.

I presented a paper at the ISSAC 2008 conference in Austria. The pdf slides from the talk can be found here. See the section below on Finite Generation of Symmetric Ideals for more information.

Research Interests: Structured polynomial systems, computational algebraic geometry, combinatorics, matrix analysis, applications of mathematics to neuroscience

I was on leave visiting University of Copenhagen Department of Mathematical Sciences from April 6 - May 16. I gave a lecture series to the math department on Groebner Basis and Applications (see below for more details). Notes will be made available soon.

Lecture Series on Groebner Bases and Applications

I gave a lecture series at the University of Copenhagen Department of Mathematical Sciences.

Introduction to Groebner Bases and Applications
Groebner Basics
Applications of Groebner Bases
Invariant Theory and Symmetric Groebner Bases

Time permitting, I will try and put together a set of notes for these lectures.

Sums of polynomial squares over totally real fields are rational sums of squares

(Some slides) Let K be a totally real number field. We prove that if f in Q[x₁,...,x_n] is a sum of squares in K[x₁,...,x_n], then f is a sum of squares in Q[x₁,...,x_n]. Moreover, our argument is constructive. This gives a partial resolution to a question of Sturmfels on the algebraic degree of certain semidefinite programing problems. A practical application is that searching numerically for sums of squares can be done in exact arithmetic over the rationals (if it can be done at all over K). Proceedings of the American Mathematical Society, 137 (2009), 921-930.

Automorphisms of Abelian Groups

We give a complete description of the automorphisms of finite abelian groups. This leads to a formula for their cardinalities. Although this characterization has essentially been known for quite some time, we provide a much needed modern and accessible treatment. (Joint with D. Rhea). The American Mathematical Monthly, 114 (2007), no. 10, 917-923. arXiv | Wikipedia

Algebraic Characterization of Uniquely Vertex Colorable Graphs

(slides from a talk and code for algorithms) The study of graph colorability from an algebraic perspective has introduced novel techniques and algorithms into the field. For instance, k-colorability of a graph can be characterized by whether its graph polynomial is contained in a certain ideal. In this paper, we interpret unique colorability in an analogous manner and use Groebner basis techniques to prove an algebraic characterization for uniquely k-colorable graphs. Our result also gives algorithms for testing unique colorability. As an application, we verify a counterexample to a conjecture of Xu concerning uniquely 3-colorable graphs without triangles. (Joint with T. Windfeldt). Journal of Combinatorial Theory Series B, 98 (2008), 400-414.

We give an elementary and elegant proof of the following generalization of a fundamental result of Artin:

Let A be a symmetric matrix with entries in the polynomial ring R[x₁,...,x_n].

Theorem: If A is postive semidefinite for all substitutions (x₁,...,x_n) in Rⁿ, then A can be expressed as a sum of squares of symmetric matrices with entries in R(x₁,...,x_n).

Moreover, our proof is constructive and gives an explicit representation modulo the scalar case. (Joint with J. Nie). Proceedings of the American Mathematical Society, 136 (2008), 73-76.

Finite Generation of Symmetric Ideals

(some slides from a talk) We prove a finiteness theorem for ideals in infinite dimensional polynomial rings that are invariant under symmetric group action. The proof involves introducing a certain well-quasi-ordering on monomials and developing a theory of Groebner bases and reduction in this setting. We also consider the concept of an invariant chain of ideals for finite-dimensional polynomial rings and relate it to the finite generation result mentioned above. Finally, a motivating question from chemistry is presented. (Joint with Matthias Aschenbrenner). Trans. Amer. Math. Soc., 359 (2007), 5171-5192. (minor errata here).

A follow up note (with Troels Windfeldt) showing that invariant ideals are not always generated by a fixed number of polynomials is here, Proc. Amer. Math. Soc., 136 (2008), 4135-4137. (see also minor errata concerning the Trans. paper above).

New: An Algorithm for computing these Groebner bases | Preliminary manuscript | arxiv

Advances on the Bessis-Moussa-Villani Trace Conjecture

(A poster, some talk slides, and a brief overview of what is known). We make some advances on a long-standing BMV conjecture in mathematical physics due to Bessis, Moussa, and Villani. The statement is enticingly simple (thanks to a reformulation by Elliot Lieb and Robert Seiringer): For every positive integer m and every pair of positive definite matrices A and B, the polynomial

p(t) = Tr[(A+tB)^m]

has nonnegative coefficients. One of the interesting implications is that to prove the conjecture for all m, it is enough to prove it for infinitely many m. Moreover, if it is true for some m, then it is true for all smaller m. Linear Algebra and Applications, 426 (2007), 130-142.

A recent result of Daniel Haegele proves the conjecture for m = 7, although his technique does not generalize to m = 6. However, by my results, this implies the m = 6 case as well.

Solving Symmetric Word Equations

(code that preforms the calculations in this paper: maple code 1 | maple code 2). We continue a study of the solvability of symmetric word equations in positive definite letters. Let S(X,B) be a palindromic word in two letters X and B. A previous result states that for each pair of positive definite matrices B and P, there is a positive definite solution X to the equation S(X,B) = P. The authors also conjectured that these solutions are unique. In this paper, we resolve this conjecture (negatively). Furthermore, we prove that, generically, the number of solutions is odd (and thus finite) in the real case. Our approach utilizes the theory of Brouwer degree and also provides a second proof of existence of such solutions in the real case. (Joint with Scott Armstrong). Journal of the London Mathematical Society, 76 (2007), no. 3, 777-796.