BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/106
DTSTAMP:20230914T125910Z
SUMMARY:On Universal and Differentially Private Steiner Trees and TSPs
DESCRIPTION:Speaker: Deeparnab Chakrabarty\nUniversity of Pennsylvania\nDep
 artment of Computer and Information\nSciences\nPhiladelphia\n\nAbstract: \
 nGiven a collection of vertices in a network\, the problem of finding the 
  minimum cost sub-network connecting a set of  client nodes to a dedicated
  hub-node is the Steiner tree problem. Consider the following two twists. 
 In the first setting\, the set of client nodes is unknown\, and the algori
 thm needs to output a master tree  which  works well  for all plausible se
 t of clients. In the second setting\,  the set of clients is known\, howev
 er\, the algorithm's output must respect  privacy constraints and not reve
 al any information about a node (of it being a client or a not). These two
  settings\, defined similarly for the traveling salesman problem\, lead to
  the universal and private versions of the problem\, respectively. Clearly
 \, these need the design of new classes of algorithms and the question tha
 t naturally arises is: how good/bad is the performance of these compared t
 o the traditional algorithms?\n\nAfter giving precise definitions of the p
 roblems in hand\, we'll resolve the above question for the above two probl
 ems by giving lower bounds which match the known upper bounds (which also 
 we'll sketch) up to constant factors. Our constructions are simple\, and I
 'll attempt to convey them in this self contained talk (joint work with An
 and Bhalgat and Sanjeev Khanna\, both at University of Pennsylvania).\n
URL:https://www.tcs.tifr.res.in/web/events/106
DTSTART;VALUE=DATE:20100722
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR