### Monday, July 13

## Joint Plenary Presentation 1

Graph Algorithms Via Spectral Techniques

9:00 AM-10:00 AM

*Chair: Michael Molloy, University of Toronto, Canada*

*Room: Convocation Hall*

The existence of efficient algorithms to compute the eigenvectors and eigenvalues of graphs supplies a useful tool for the design of various graph algorithms.

The speaker will describe several algorithms of this type, mentioning their application as approximation algorithms and focusing on their performance for randomly generated input graphs. The algorithmic problems considered include ones motivated by questions in scheduling and VLSI circuit design, like graph coloring and graph bisection, and the methods used combine algebraic, probabilistic and combinatorial techniques.

A representative recent result, obtained jointly with M. Krivelevich and B. Sudakov, is a spectral technique for finding efficiently a clique of size epsilon n^{ ½} in a random graph on n vertices with a clique of this size placed in it randomly.

**Noga Alon**

*Department of Mathematics, Tel-Aviv University, Israel and*

*Institute for Advanced Study, Princeton*

DM98 Home | AN98 Home | General Information

MMD Created: 3/9/98 Updated: 3/23/98