- CIRCUIT COMPLEXITY, PROOF C...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in May 2014

## CIRCUIT COMPLEXITY, PROOF COMPLEXITY, AND POLYNOMIAL IDENTITY TESTING

**Speaker:**
Toniann Pitassi
, University of Toronto

**Date:**
Monday, May 12, 2014

**Time:**
4:00 PM to 5:00 PM
** Note: all times are in the Eastern Time Zone**

**Refreshments:**
3:45 PM

**Public:**
Yes

**Location:**
32-G449

**Event Type:**

**Room Description:**

**Host:**
Ankur Moitra, TOC, CSAIL, MIT

**Contact:**
Holly A Jones, hjones01@csail.mit.edu

**Relevant URL:**
http://toc.csail.mit.edu/node/494

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
seminars@csail.mit.edu, toc@csail.mit.edu, theory-seminars@csail.mit.edu

**Reminder Subject:**
TALK: CIRCUIT COMPLEXITY, PROOF COMPLEXITY, AND POLYNOMIAL IDENTITY TESTING

Special Day and Time!

Abstract: We introduce a new algebraic proof system, which has tight connections to (algebraic) circuit complexity.

In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system

implies that the permanent does not have polynomial-size algebraic circuits (VNP is not equal to VP).

As a corollary to the proof, we also show that super-polynomial lower bounds on the number of lines in

Polynomial Calculus proofs (as opposed to the usual measure of number of monomials) imply the Permanent

versus Determinant Conjecture. Note that, prior to our work, there was no proof system for which lower bounds

on an arbitrary tautology implied any computational lower bound. Our proof system helps clarify the relationships

between previous algebraic proof systems, and begins to shed light on why proof complexity lower bounds for various

proof systems have been so much harder than lower bounds on the corresponding circuit classes. In doing so, we

highlight the importance of polynomial identity testing (PIT) for understanding proof complexity.

More specifically, we introduce certain propositional axioms satisfied by any Boolean circuit computing PIT.

We use these PIT axioms to shed light on AC^0[p]-Frege lower bounds, which have been open for nearly 30 years,

with no satisfactory explanation as to their apparent difficulty. We show that either: a) Proving super-polynomial

lower bounds on AC^0[p]-Frege implies VNP does not have polynomial-size circuits of depth d - a notoriously open

question for d at least 4 - thus explaining the difficulty of lower bounds on AC^0[p]-Frege, or b) AC^0[p]-Frege

cannot efficiently prove the depth d PIT axioms, and hence we have a lower bound on AC^0[p]-Frege.

Using the algebraic structure of our proof system, we propose a novel way to extend techniques from algebraic

circuit complexity to prove lower bounds in proof complexity.

This is joint work with Joshua A. Grochow.

**Research Areas:**

**Impact Areas:**

Created by Holly A Jones at Tuesday, May 06, 2014 at 1:52 PM.