Chaire Aisenstadt 2006 Aisenstadt Chair
Professor Noga Alon
(Tel Aviv University)

La conférence en photos / The conference in pictures

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

Le lundi 11 septembre 2006 / Monday, September 11, 2006

16 h / 4:00 p.m.

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

Cette conference s'adresse à un large auditoire.
Suitable for a general audience.

Approximation algorithms and Grothendieck type inequalities

I will describe a connection between a classical inequality of Grothendieck and approximation algorithms based on semidefinite programming.

The investigation of this connection suggests the definition of a new graph parameter, called the Grothendieck constant of a graph, whose study is motivated by algorithmic applications and leads to several extensions of the inequality of Grothendieck, to an improvement of a recent result of Kashin and Szarek, and to a solution of a problem of Megretski and of Charikar and Wirth.

The lecture will include a description of Grothendieck's Inequality, its extensions, and their relevance to approximation algorithms. The new material is based on three recent papers with various subsets of A. Naor, E. Berger, K. Makarychev, and Y. Makarychev.

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).

Le mercredi 13 septembre 2006 / Wednesday, September 13, 2006

16 h / 4:00 pm

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

Additive Approximation for Edge-Deletion Problems

I will sketch a proof that for any monotone graph property P and any ε>0 one can approximate efficiently the minimum number of edges that have to be deleted from an n-vertex input graph to get a graph that satisfies P, up to an additive error of εn2. Moreover, for any dense monotone property, that is, a property for which there are graphs on n vertices with Ω(n2) edges that satisfy it, it is NP-hard to approximate this minimum up to an additive error of n2−ε, for any fixed positive ε. The second part answers a question raised by Yannakakis in 1981.

Joint work with A. Shapira and B. Sudakov.

Le vendredi 15 septembre 2006 / Friday, September 15, 2006

16 h / 4:00 pm

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

Graph Property Testing

Let P be a property of graphs. A testing algorithm for P is a randomized
algorithm which, given the ability to make queries whether a desired
pair of vertices of an input graph G on n vertices are adjacent or not,
determines, with high probability, if G satisfies P or it has to be
modified by deleting and adding to it at least $\epsilon n^2$ edges
so that it satisfies P.

Graph Property Testing deals mainly with the investigation
of the graph properties for which there are testing algorithms whose
query complexity is bounded by a function of $\epsilon$ only, and does
not grow with the size of the input graph. I will survey some of the
main known results on this topic, focusing on several recent ones that
illustrate the techniques applied, and will also discuss the main
remaining open problems.