• https://fme.upc.edu/ca/esdeveniments/lunch-seminar-mesio-upc-ub-7
• Lunch Seminar MESIO UPC-UB
• 2017-04-19T14:00:00+02:00
• 2017-04-19T15:00:00+02:00

Quan

19/04/2017 de 14:00 a 15:00

On

Sala de juntes FME / Sala de reunions

URL de l'esdeveniment

Lloc web relacionat

Afegeix un esdeveniment al calendari

iCal

Speaker:

Abstract:

Volem saber si un graf amb molts vèrtexs i moltes arestes té algun triangle. Aquesta és una propietat local i una resposta definitiva pot requerir una exploració de tot el graf. Si en tenim prou de saber que el graf no està lluny de no tenir triangles de sobte descobrim (amb gran fascinació) que n’hi ha prou amb analitzar una sola mostra.

Aquesta estratègia, que s’aplica a estructures combinatòries i algebraiques bastant generals, es coneix amb el nom de Property Testing. En el cas de grafs densos està relacionat amb un resultat cèlebre, el teorema de Szemerédi, que es pot descriure dient que una classe ampla d’estructures combinatòries   (un graf, per exemple) té una component aleatòria i una component estructurada que es poden analitzar per separat. El Property Testing explota aquesta dualitat per plantejar un mètode de mostreig de propietats d’una eficàcia inusual. Tot i que l’èxit d’aquesta estratègia es basa en la naturalesa de l’univers que s’explora, té un àmbit d’aplicació sorprenentment ampli. El pla de la xerrada és exposar l’estratègia general, avaluar-ne l'eficàcia i ilustrar-la amb alguns exemples..