Toniann Pitassi Department of Computer Science, University of Arizona, Tuscon, AZ 85721 toni@cs.arizona.edu Title: Algebraic proof systems and binomial ideals The polynomial calculus (PC) is a natural, algebraic proof system for proving that a system of polynomial equations are unsolvable. In this system, one starts with an initial family of polynomial equations, $P_1 =0, .., P_m =0$, (typically over a field), and the goal is to derive $1=0$. The allowable operations are: (1) adding linear combinations of previously derived equations, and (2) multiplying a previously derived equation by a variable. The degree of a PC refutation is the maximal degree of any intermediate polynomial in the derivation. This proof system and its variants have been well-studied over the last several years due to its fundamental nature, and also because of its connections with classical proof complexity. In this talk, we first present a brief survey of algebraic proof systems: what they are, their connections to classical proofs, and the state-of-the-art in lower and upper bounds. We will then focus on proving good lower bounds on PC degree, a problem that has received much attention recently. We will present nearly optimal lower bounds on the minimal degree of PC refutations of Tseitin's graph tautologies and the mod p counting principles. The lower bounds apply to the PC over rings or fields. These are the first linear lower bounds for PC; and distinguish linearly the rings $Z_q$ and $Z_r$ where $q$ and $r$ do not have identical prime factors. Moreover, our proof is quite simple, and the method applies to any initial system of binomial ideals. This is joint work with Sam Buss, Dima Grigoriev and Russell Impagliazzo