BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.25717.field_data.0@www.diag.uniroma1.it
DTSTAMP:20240529T080059Z
CREATED:20230607T082449Z
DESCRIPTION:AbstractSpectral properties of graphs are of paramount importan
ce. While important properties of graphs are reflected in properties of th
eir spectra\, fundamental connections between spectral and topological pro
perties of graphs are at the core of some successful approaches in a numbe
r of problems\, e.g.\, graph partitioning or community detection. At the s
ame time\, graph spectra are related to key properties of random walks in
graphs. These\, in turn\, describe key aspects of some fundamental dynamic
s on graphs.The goal of this course is introducing students to these topic
s\, providing an overview of key notions\, some reference applications and
how spectral properties of graphs can be investigated from different pers
pectives\, leading to insights into applications of interest both in compu
ter science and other areas of research.Speakers: Prof. Luca Becchetti (Sa
pienza University) and Prof. Francesco Pasquale (University Tor Vergata Ro
me)Course schedule Monday\, June 12th9am - 11am. Francesco PasqualeIntr
oduction to Markov chains and random walks. Examples: birth-and-death chai
ns. Applications: An algorithm for 3-SAT with running time O((4/3)^n \poly
(n)).11am - 1pm. Francesco PasqualeRandom walks\, stationary distributions
. Irreducibility and aperiodicity\, lazy chains. Total variation distance\
, mixing time. Relaxation time and the second eigenvalue. Mixing and relax
ation.Tuesday\, June 13th10am - 12am noon. Luca BecchettiGraphs and graph
matrices. Spectral theorem for symmetric matrices. Variational characteriz
ation of eigenvalues. Graph matrices.2pm - 4pm. Luca BecchettiBottlenecks
and cuts. Finding cuts of minimum conductance. Easy part of Cheeger's ineq
uality. Sparse cuts and Laplacian's second eigenvecto's profile: Examples.
Wednesday\, June 14th10am - 12am noon. Francesco PasqualeSampling and coun
ting\, the Monte Carlo Method. Approximate sampling and approximate counti
ng. Application: DNF-counting. Introduction to the Markov Chain Monte Carl
o method.2pm - 4pm. Luca BecchettiHard part of Cheeger's inequality and im
plications.Thursday\, June 15th10am - 12am noon. Francesco PasqualeTechniq
ues for bounding mixing time: coupling\, path coupling\, bottleneck ratio.
Example: Random walk on the hypercube.2pm - 4pm. Luca BecchettiEigenvalue
s\, bottlenecks and rapid mixing. Mixing time and conductance. Expanders a
nd expander mixing lemma.Friday\, June 16th10am - 12am noon. Francesco Pas
qualeThe Markov Chain Monte Carlo method. Application: Approximate countin
g proper colorings.2pm - 4pm. Luca Becchetti: Spectral Graph TheoryBeyond
conductance: graph partitioning and k-way constant. Brief overview of high
er-order Cheeger's inequalities. Spectral embeddings and Spectral graph cl
ustering with examples.Zoom link: https://uniroma1.zoom.us/j/98700192862?p
wd=VlRPQmEyQjJUWXdjTzJyMFVDZEVXdz09
DTSTART;TZID=Europe/Paris:20230612T090000
DTEND;TZID=Europe/Paris:20230616T160000
LAST-MODIFIED:20230607T082905Z
LOCATION:Room B203@DIAG\, via Ariosto 25\, Rome
SUMMARY:PhD course - Spectral graph theory and random walks: connections an
d applications - Luca Becchetti (Sapienza University) and Francesco Pasqua
le (University Tor Vergata Rome)\n\n\n \n \n\n \n\n\nLuca\n\n\nBecche
tti \n\n \n\n \n\n\n\n\n\nProfessore associato\n\n\npagina personale
\n\nstanza: \n\nB206\n\ntelefono: \n\n+39 0677274025 \n\n \n\n \n\nBi
ografia: \n\n\n\nPosition:\n\n\n- December 2012 - present: Associate Profe
ssor at Dipartimento di Ingegneria Gestionale 'Antonio Ruberti'\, Sapienza
University of Rome.\n\n\n- March 2001 - December 2012: Research associate
at Dipartimento di Ingegneria Gestionale 'Antonio Ruberti'\, Sapienza Uni
versity of Rome.\n\n\nEducation:\n\n\n- PhD in computer engineering at Dip
artimento di Ingegneria Gestionale 'Antonio Ruberti'\, Sapienza University
of Rome\, 1998\n\n\n- M. Sc. in computer engineering at Dipartimento di I
ngegneria Gestionale 'Antonio Ruberti'\, Sapienza University of Rome\, 199
5\n\n\nVitae:\n\n\nA longer version of my curriculum can be found at this
link\n\n\n \n\n\nInteressi di ricerca: \n\n\n\nI have a background interes
t in the design and analysis of algorithms for NP-hard and on-line optimiz
ation problems\, with emphasis on network efficient design and resource al
location. More recently\, I studied problems arising in the modelling and
analysis of algorithms and techniques for the mining and analysis of large
scale information networks\, such as Internet and the Web.\n\n\nCurrent r
esearch directions include the application of spectral graph theory techn
iques to fully distributed graph clustering and the algorithmic modelling
and analysis of large complex systems. A new further research direction is
the application of advanced graph mining and spectral analysis techniques
in the emerging area of Network Medicine.\n\n\nqualifica_rr: \n\nAssociat
e professors
URL;TYPE=URI:https://www.diag.uniroma1.it/node/25717
END:VEVENT
END:VCALENDAR