Fine-Grained Rough Draft

Speaker: Sebastian Krinninger
The Power and Limitations of Randomness in Dynamic Graph Algorithms

In this talk we consider a class of algorithms whose task is to update the solution to a graph problem as the underlying graph is undergoing updates, such as insertions and deletions of edges. Randomization is a very useful tool in designing dynamic graph algorithms, allowing very fast update times in many cases. However, the use of randomness usually requires an oblivious adversary whose sequence of updates to the graph is independent of the random choices of the algorithm. We argue that for dynamic algorithms to unleash their full potential this assumption is obstructive. Correctness against an adaptive online adversary is crucial if, for example, the dynamic algorithm is repeatedly called by another algorithm. We demonstrate our main points with a very simple partially dynamic algorithm for maintaining the shortest paths of a directed graph.

Speaker: Elad Haramaty
Connection Between Low Degree Testing and Algorithms

The polynomial method is a general method of solving some mathematical problem as follows. First, an instance of the problem is converted into a polynomial. Then properties of polynomials are used get insights into the original problem. This method is often used in algorithms and specifically in upper bounds of parameterized complexity. In this case usually some kind of Polynomial Identity Testing (PIT) algorithm (e.g. Schwartz–Zippel) is used on the resulting polynomial.

In this talk we will argue that, in addition to PIT, there are other algorithms that can be used in order to get insight into polynomials. Specifically, we claim that nowadays low degree testers are strong enough to play a role in such reductions. We will show, as an example (from [Abasi-Bshouty-Gabizon-H 14]), how to get O*(2^k) algorithm for finding a path of length k in a graph ([Williams 09]) using low degree testing.