אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Inmodern applications of graph algorithms, where the graphs of interest arelarge and dynamic, it is unrealistic to assume that an input representationcontains the full information of a graph being studied. For example, consider asocial network, where a vertex corresponds to a user and an edge corresponds toa friendship relation. It is reasonable to assume that users do not alwaysupdate new friendships on the social network, and that sometimes theydo not fully disclose their friendship relations for security or privacyreasons. This motivates the design of graph algorithms that, in spite of beinggiven only a (large) subgraph as input, output solutions that are close to thesolutions output when the whole graph is available. In this talk, I willintroduce a notion of sensitivity of graph algorithms that formalizes thisdesirable feature. After discussing the basic properties of our sensitivitydefinition, I will give an overview of the key ideas used in the design of algorithmswith low sensitivity for the maximum matching problem, the minimum cutproblems, and the balanced cut problem.