### CHAIRE ANDRÉ AISENSTADT CHAIR 2010

Une série de conférences / A series of lectures

Alexander Razborov (Chicago)

*Conférences dans le cadre de l'atelier « Équations et propriétés du premier ordre dans les groupes »
Lectures at the Workshop "Equations and First-order Properties in Groups"*

Alexander Razborov |

Telecharger l'affiche / Download poster

**Mardi 12 octobre 2010, 16h00
Tuesday, October 12, 2010, 4:00 pm**

Centre de recherches mathématiques

Pavillon André-Aisenstadt, Université de Montréal, 2920, ch. de la Tour , Salle / Room 1355

* Topics in extremal combinatorics *

Extremal Combinatorics is one of the most important branches of discrete mathematics that has undergone a period of spectacular growth in recent decades. Loosely speaking, it studies how large (or small) a collection of finite objects can be if it has to satisfy certain restrictions. In this lecture I will be able to review only a handful of classical results and techniques from this vast field. My selection will be highly biased and reflecting personal taste. While some of the material will set the stage for the October 14 lecture, most of it will be included due to its own beauty, elegance and
importance.

**Mercredi 13 octobre 2010, 16h00
Wednesday, October 13, 2010, 4:00 pm**

Centre de recherches mathématiques

Pavillon André-Aisenstadt, Université de Montréal

2920, ch. de la Tour, Salle / Room 6214

*Complexity of propositional proofs*

The underlying question of propositional proof complexity is amazingly simple: when interesting propositional tautologies possess efficient proofs in a given propositional proof system? This theory makes an integral part of more general theory of feasible provability, the later being widely considered as the proof theory for the world of efficiently computable objects. Other motivagions for studying complexity of propositional proofs come from algebra, automated theorem proving and, of course, computational (especially circuit) complexity. Given its mixed origin, the methods currently employed in this area are also very diverse. We will try to illustrate some of them and give the audience at least some feeling of the current state of the art in the area. A special attention will be paid to algebraic and geometric proof systems, such as Polynomial Calculus and various proof systems inspired by Lovasz-Schrijver relaxation procedures (some of the intriguing connections to the classical computational complexity will be reviewed on October 15).

**Jeudi 14 octobre 2010, 16h00 /
Thursday, October 14, 2010, 4:00 pm**

Centre de recherches mathématiques

Pavillon André-Aisenstadt, Université de Montréal

2920, ch. de la Tour , Salle / Room 6214

A substantial part of extremal combinatorics studies relations existing between densities with which given combinatorial structures (fixed size "templates") may appear in unknown (and presumably very large) structures of the same type. Using basic tools and concepts from algebra, analysis and measure theory, we develop a general framework that allows to treat all problems of this sort in an uniform way and reveal mathematical structure that is common for most known arguments in the area. The backbone of this structure is made by commutative algebras defined in terms of finite models of the associated first-order theory. In this talk I will give a general impression of how things work in this framework, and we will pay a special attention to concrete applications of our methods.

Cette conférence s'adresse à un large auditoire / Suitable for a general audience

**Vendredi 15 octobre 2010, 16h00 /
Friday, October 15 2010, 4:00 pm**

Centre de recherches mathématiques, Pavillon André-Aisenstadt, Université de Montréal, 2920, ch. de la Tour, Salle / Room 1360

*Grand challenges in complexity theory
*

Modern complexity theory is a vast, loosely defined area. Its methods and methodology can be successfully applied whenever one has a set of tasks, a class of admissible solutions, and numerical characteristics to measure the "quality" of a solution. This talk will focus on two specific scenarios: classical computational complexity and proof complexity. The story we will tell, however, is highly representative of the methods that have been tried in the field at large, with its mixed bag of successes, setbacks, and promising directions. I will try to reveal some of the tight, beautiful and unexpected connections existing between different branches of complexity theory. I will discuss the "grand challenges" of the field, including "P vs NP" and questions about the power of classical proof systems. This talk will assume no prior knowledge in theoretical computer science.

##### Une réception suivra la conférence au Salon Maurice-L'abbé, Pavillon André-Aisenstadt (Salle 6245).

##### There will be a reception after the lecture in Salon Maurice-L'abbé, Pavillon André-Aisenstadt (Room 6245).