If you do not see this message displayed properly, please click here


The Faculty of Informatics is pleased to announce a seminar given by Matias Korman



Building wireless networks and routing on them
Speaker: Matias Korman
Tohoku University, Japan
Date: Wednesday, May 17, 2017
Place: USI Lugano Campus, room A34, Red building (Via G. Buffi 13)
Time: 9:30-10:30



In this talk I will talk about a network problem that showcases the kind of research problems I work on. A routing scheme $\Rr$ in a network $G=(V,E)$ is an algorithm that allows to send messages from one node to another in the network. 

Given the location of the nodes, we first consider a preprocessing phase in which we construct the network (if possible, we also assing\emph{routing table} with additional information to each node). After this preprocessing, we give a local routing (i.e., we can only use the information from the label of the target and the routing table of the node that we are currently at). 

We present a network construction algorithm paired with a routing scheme in the presence of obstacles: if we are not allowed a routing table, each node stores a constant amount of information and the messages are guaranteed to arrive. If we are allowed a routing table of size of size $\Oe(\eps^{-1}\log n)$ per node, the routing scheme provides a stretch of $1+\eps$  for any $\eps > 0$. is $\Oe(n^2+\eps^{-1}n)$. This improves the best known strategies for general graphs by Roditty and Tov (Distributed Computing 2016).



Matias Korman is an assistant professor at Tohoku University (Japan). His research focuses in the design of algorithms with strong geometric components. Specifically, he is interested in problems related to shortest paths, memory constrained algorithms, and/or wireless networks. 


Host: Prof. Evanthia Papadopoulou


Faculty of Informatics

Faculty of Informatics
Università della Svizzera italiana
Via Giuseppe Buffi 13
CH-6904 Lugano
Tel.: +41 (0)58 666 46 90
Fax: +41 (0)58 666 45 36
Email: decanato.inf@usi.ch
Web: www.inf.usi.ch
Twitter: @USI_INF


Segui USI@EXPO2015 su Twitter Segui USI@EXPO2015 su Facebook Segui USI@EXPO2015 su Linkedin Segui USI@EXPO2015 su YouTube