Back to Homepage

Click on the blue triangle to reveal summary.

Publications, Reports

Algebraic Complexity Theory

Real Tau Conjecture. The tau-complexity of an integer polynomial is the minimum number of additions, substractions and multiplications needed to build it using just the scalar `1' and the indeterminate `x'. The fourth problem in the Smale's list of mathematical problems for the next century is the tau-conjecture due to Shub and Smale (1995). It states that the number of distinct integer zeros of an integer polynomial is polynomially upper bounded by its tau-complexity. A real variant of this conjecture was posed by Koiran (2011), and we survey some of the progress towards it in this thesis.

Spectral / Algebraic Graph Theory, Combinatorics

Permanental Polynomial. The spectrum of a graph is also the multiset of roots of the characteristic polynomial of the adjacency matrix. Another closely related graph polynomial is the permanental polynomial which is less understood as a graph invariant in comparison. The location of the roots of graph polynomials provides useful information about the graph properties. We construct some new graphs with the property that all of their permanental polynomial roots lie on the imaginary axis. The permanent is known for its computational hardness. We also give an expression to compute the permanental polynomial using only the characteristic polynomial for a special class of graphs.
Cospectral Graphs. The spectrum of a graph (the multiset of eigenvalues of the associated adjacency matrix) is a useful graph invariant towards graph isomorphism problem, although not a complete one because there exists many examples of cospectral graphs (a pair of nonisomorphic graphs with the same spectrum). An open problem in spectral graph theory is to prove that "almost all graphs are determined by their spectrum", a conjecture by van Dam and Haemers (2003). By a graph determined by its spectrum, we mean that there is no other nonisomorphic graph with the same spectrum as the given graph. We studied two techniques toproduce cospectral graphs — unfolding and the partitioned tensor product — and discovered they have a connection.