moteur de recherche

Séminaire Algo - Rémi de Joannis de Verclos
Séminaire Algo - Rémi de Joannis de Verclos
23-Jan-2018 14:30
Age: 1 year

Rémi de Joannis de Verclos

Easily testable properties of dense graphs

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: A graph of size n is ɛ-far from having a property P if one have to add or delete at least ɛn² edges of G to have a graph satisfying P. A graph property P is testable if for every ɛ there is a constant m(ɛ) such that it is possible to distinguish (with one-sided error) between graphs of P and graphs that are ɛ-far from P with an algorithm that examines only a random induced subgraph of size m(ɛ). It has been proven that every hereditary property is testable but the query complexity m(ɛ) proved is an exponential tower in 1/ɛ. Following a work of Alon and Fox, we seek to classify graph classes for which this query complexity m(ɛ) is a polynomial in 1/ɛ, which are called "easily" testable.

<- Back to: Accueil