J. Maurice Rojas
In this talk, we'll see how counting the real solutions of a system of equations (an algebraic problem) is related to simple diagrams one can draw by hand (polyhedral combinatorics). In particular, we will derive polynomial-time algorithms for detecting real solutions in certain instances where only exponential-time algorithms were known before.
We assume no background in algebraic geometry or algorithmic complexity. Some of the results we'll see are joint work with Frederic Bihan, Alicia Dickenstein, Korben Rusek, Justin Shih, Frank Sottile, and Casey Stella.
J. Maurice Rojas
We reveal a completely different approach, arising from seminal work of Pascal Koiran, that uses number theory to get sub-exponential algorithms. In particular, we'll see how the famous Riemann Hypothesis relates to the complexity of this new class of algorithms.
While we thus reveal a link between P=NP, the Riemann hypothesis, and equation solving, we assume no background in complexity theory, number theory, or algebraic geometry.
S. Benz Suanmali
Laurie Zack
Jay Shapiro
Geir Agnarsson
Frank J. Hall
George Mason University
Title: Embedding into Free Objects Satisfying the ACC
Abstract: It is a known fact that the free monoid $\langle x_1,\ldots,x_n\rangle$
on $n$ generators can be embedded into the ring $M_2(\mathbb{Z})$ of $2\times 2$
matrices over the integers. In fact, the free group on two generators also
embeds into $M_2(\mathbb{Z})$. This can be done in various ways and some
embeddings are nicer than others.
In this talk we discuss some of these embeddings and also a similar open
question of G.~M.~Bergman of whether the free $k$-algebra $k\langle x_1,\ldots,x_n\rangle$
allows a similar embedding into some free object satisfying the ascending chain
condition (ACC), where $k$ is a field or a commutative ring.
Title: Polynomial Extension of Rational Realizations of Minimum
Rank Matrices in a Sign Pattern Class
Abstract: A sign pattern matrix is a matrix whose entries come from the
set {+, -, 0}. The minimum rank of a sign pattern matrix A is the minimum
of the ranks of the real matrices whose entries have signs equal to the
corresponding entries of A. It is conjectured that the minimum rank of
every sign pattern matrix can be realized by a rational matrix. The
equivalence of this conjecture to several seemingly unrelated statements is
established. For some special cases, such as when A is entrywise nonzero,
or the minimum rank of A is at most 2, or the minimum rank is least n * 1 (where
A is m by n), the conjecture is shown to hold. Connections between this
conjecture and the existence of positive rational solutions of certain systems
of homogeneous quadratic polynomial equations with each coefficient equal to
either 1 or -1 are investigated.
This is joint work with Marina Arav, Selcuk Koyuncu, Zhongshan Li, and Bhaskara
Rao.
Jason Rosenhouse
Title: Decomposition Theorems for Cayley Graphs of the Modular Group
over a Finite Field
Abstract: Cayley graphs of the modular group over over various rings are
of interest both for their combinatorial properties, and for their connections
with spectral geometry. We discuss various ways of decomposing certain
quotients of such graphs. We then use these decompositions to prove
theorems about the Hamiltonicity and expansion properties of these graphs.
Gary Peterson
Title: The Idempotent Quiver of a Nearring
Abstract: The idempotent quiver of a nearring R is a directed graph formed using primitive idempotents of R corresponding to the isomorphism classes of minimal R-modules. An overview of the theory of such quivers, their computation and their relationship with the structure of R and its modules will be presented.
Jack Perry
North Carolina Wesleyan College
Title: Some criteria on leading terms for detecting S-polynomial
representations
Abstract:
Gr\"{o}bner bases are by now a fundamental method in computer algebra. To
decide whether $F=\left(f_1,f_2,\ldots,f_m\right)$ is a Gr\"{o}bner basis,
one must determine whether the $S$-polynomials of $F$ have a special
representation modulo $F$. Sometimes, the leading terms of $F$ imply that one
can skip an explicit computation of some $S$-polynomial representations. In
addition to developing the first algorithm to compute Gr\"{o}bner bases,
Bruno Buchberger gave two such criteria. These are well-known and commonly used.
Are Buchberger's criteria the most general criteria using leading terms alone?
We show that the answer is, ``almost, but not quite,'' for it depends on how
many leading terms are considered. We give an example of a more general
criterion on leading terms, and indicate how we hope to find the most general
criterion possible using leading terms alone.
Greg Dresden
Washington & Lee University
Title: On the Mahler Measure of P(f/g)
Abstract: One way of thinking about the Mahler measure is to interpret it
as an indication of how close the roots of a given polynomial are to the unit
circle; equivalently, how close a given polynomial is to being cyclotomic. For
P(f/g), we need to first consider the cases when it (or one of its factors) is
cyclotomic, which happens surprisingly often. Then, we can establish some lower
bounds for the Mahler measure of this polynomial.
Dominic Lanphier
Western Kentucky University
Title: Extending Rankin-Cohen Algebras
Abstract: A Rankin-Cohen algebra (RC-algebra) over a field is defined to
be a graded algebra with a certain class of bilinear operators, [,]_n, called
Rankin-Cohen brackets. These brackets satisfy various identities: :for example
the operator [,]_0 is just multiplication and [,]_1 is a Lie bracket. This gives
an RC-algebra the stucture of a Lie algebra. The notion of an RC-algebra is
derived from the theory of modular forms and the analytic properties of modular
forms are used to give a specific definition of the nth Rankin-Cohen bracket.
We give an overview of RC-algebras and then extend their definition to a certain
class of bigraded algebras equipped with a derivation operator. This
allows us to give an alternative, algebraic definition of an RC-algebra.
Ed Swartz
Cornell University
Title: Face ring multiplicity via CM-connectivity sequences
Abstract: Let R=k[x_1,...,x_n]/I be a homogeneous quotient of a
polynomial ring. Huneke, Herzog and Srinivasan have conjectured upper and
(when R is Cohen-Macaulay) lower bounds for the multiplicity of R strictly in
terms of the minimal and maximal degrees occurring in a (minimal)
resolution of R. We verify the lower bound for several types of face
rings. These include face rings of two-dimensional Cohen-Macaulay
complexes, Gorenstein complexes of dimension three and four and large classes of
doubly Cohen-Macaulay posets. This is joint work with
Isabella Novik (U. of Washington).
Stefan Kolb
Title: On the Bernstein-Gelfand-Gelfand Resolution for Quantized Enveloping Algebras
Abstract: The usual proof of the exactness of the Bernstein-Gelfand-Gelfand (BGG) resolution for
symmetrizable Kac-Moody algebras relies on the standard resolution in Lie algebra homology.
For quantized enveloping algebras however, the standard resolution is not available, and
hence many authors revert to specialization techniques.
In this talk we present an elementary proof of the exactness of the BGG resolution which
does not depend on the standard resolution and which also works in the quantum group setting
avoiding specialization. (Joint work with Istvan Heckenberger.)
Dewey Taylor
Virginia Commonwealth University
Title: Bruhat Interesections for Reductive Monoids