קולוקוויום בביה"ס למדעי המחשב - Algorithms and data structures for uncertain environments
Much of the research on the foundations of graph algorithms is carried out under the assumption that the algorithm has full knowledge of the input data. In spite of the theoretical appeal and simplicity of this setting, the assumption that the algorithm has full knowledge does not always hold. Indeed, uncertainty and partial knowledge arise in many settings. One example is where the data is very large, in which case even reading the entire data once is infeasible, and sampling is required.
Another example is where data changes occur over time (e.g., social networks where information is fluid). A third example is where processing of the data is distributed over computation nodes, and each node has only local information. In this talk I will discuss settings where the algorithm has to face some uncertainty and partial knowledge.
I will focus on two main fundamental areas - dynamic algorithms and distributed graph algorithms. In the second part of the talk I will discuss in more details one example in dynamic graph algorithms – maintaining shortest paths while the graph changes over time.