# Research Seminar (Winter Term 2015)

## Organizers

## Description

A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks.

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Prof. Tobias Friedrich.

## Announcements

For announcements of talks, subscribe to our mailing list.

## Talks (click on title to show abstract)

Date | Room | Speaker | Title |
---|---|---|---|

9.3. 13:30 | H-E.51 | Ankit Chauhan | Introduction to parameterized problems in Arithmetic circuits I will be giving an introductory talk on arithmetic circuits and one of the most studied algorithmic problems on arithmetic circuits, arithmetic circuit identity testing(ACIT). Also, I will give an introduction to parameterized arithmetic circuit identity testing(p-ACIT) based on the degree of the polynomial computed by the arithmetic circuit which results in a parameterized analogue of the Schwartz-Zipple Lemma. Further, I will give an introduction to the parameterized version of Determinant and Permanent. |

24.09. 16:00 | HS 1 | Mike Fellows | An Introduction to Multivariate Algorithmics The talk will focus on concrete practical motivations, examples and perspectives that have driven and continue even more forcefully to drive the development of the parameterized / multivariate theory of algorithms and complexity. The objective is not to describe the details of the theory, but rather to concretely motivate it. The talk is aimed at practical computer scientists who have often been rightly skeptical that algorithms and complexity theory has anything much to offer. The advent of multivariate algorithmics opens up many new ways in which a mathematically disciplined theory of algorithms and complexity can be deployed to strengthen practical computing. |

28.09. 13:30 | A-1.1 | Lena Schlipf | Quickest Visibility Queries In this talk we consider the problem of preprocessing a polygonal domain with a fixed starting point in order to answer efficiently the following queries: In the talk we give efficient data structures that allow us to quickly answer such visibility queries. This is joint work with E. M. Arkin, A. Efrat, C. Knauer, J. S. B. Mitchell, V. Polishchuk, G. Rote, and T. Talvitie. |

13.10. 13:30 | A-1.2 | Thomas Sauerwald | Multiple Random Walks: Cover Times, Hitting Times and Applications In this talk we will consider multiple random walks that are run independently and in parallel on a finite, undirected and connected graph. Following Alon, Avin, Koucký, Kozma, Lotker and Tuttle (2008), we will study the speed-up defined as the ratio of the cover time (hitting time) of a single random walk to the cover time (hitting time) of k independent random walks, where all k walks start from a single vertex that maximises their cover time (hitting time). We will exhibit general connections between the speed-up and other parameters like the mixing time or diameter of the underlying graph, and apply these results to specific networks including d-dimensional grids, hypercubes and expanders. Finally, we will outline how multiple random walks can be applied to the design and analysis of efficient load balancing algorithms. |

12.11. 13:30 | H-E.51 | Samadhi Nallaperuma | Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem Randomized Search heuristics are frequently applied to NP-hard combinatorial optimization problems. The runtime analysis of randomized search heuristics has contributed tremendously to their theoretical understanding. Recently, randomized search heuristics have been examined regarding their achievable progress within a fixed time budget. We follow this approach and present a fixed budget analysis for an NP-hard combinatorial optimization problem. We consider the well-known Traveling Salesperson problem (TSP) and analyze the fitness increase that randomized search heuristics are able to achieve within a given fixed time budget. In particular, we analyze Manhattan and Euclidean TSP instances and Randomized Local Search (RLS), (1+1)EA and (1+λ)EA algorithms for the TSP in a smoothed complexity setting and derive the lower bounds of the expected fitness gain for a specified number of generations. |

19.11. 13:30 | A-1.2 | Markus Wagner | Approximate Approaches to the Traveling Thief Problem I am going to report on a study that addresses the recently introduced Traveling Thief Problem (TTP) which combines the classical Traveling Salesman Problem (TSP) with the 0-1 Knapsack Problem (KP). The problem consists of a set of cities, each containing a set of available items with weights and profits. It involves searching for a permutation of the cities to visit and a decision on items to pick. A selected item contributes its profit to the overall profit at the price of higher transportation cost incurred by its weight. The objective is to maximize the resulting profit. We propose a number of problem-specific packing strategies run on top of TSP solutions derived by the Chained Lin-Kernighan heuristic. The investigations provided on the set of benchmark instances prove their rapidity and efficiency when compared with an approximate mixed integer programming based approach and state-of-the-art heuristic solutions from the literature. |

24.11. 13:30 | A-1.2 | Johannes Lengler | Geometric Inhomogeneous Random Graphs For the theoretical study of real-world networks, we propose a model of scale-free random graphs with underlying geometry that we call geometric inhomogeneous random graphs (GIRGs). GIRGs generalize hyperbolic random graphs, which are a popular model to test algorithms for social and technological networks. Our generalization overcomes some limitations of hyperbolic random graphs, which were previously restricted to one dimension. Nevertheless, our model is technically much simpler, while preserving the qualitative behaviour of hyperbolic random graphs. We prove that our model has the main properties that are associated with social and technological networks, in particular power law degrees, a large clustering coefficient, a small diameter, an ultra-small average distance, and small separators. Notably, we determine the average distance of two randomly chosen nodes up to a factor 1+o(1). Some of the results were previously unknown even for the hyperbolic case. |

25.11. 9:15 | HS 1 | Johannes Lengler | Differential Equations for Random Processes and Random Graphs This lecture presents the differential equation method as introduced by Nicholas C. Wormald in the seminal paper "Differential Equations for Random Processes and Random Graphs", Ann. Appl. Probab., Volume 5, Number 4 (1995), 1217-1235. The lecture will be a black-board talk with a number of examples how to use Theorem 5.1 of Wormald. |

30.11. 13:00 | A-2.1 | Maximilian Katzmann | Unbounded Discrepancy of Deterministic Random Walks on Grids Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs, called rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a xed deterministic order. For most setups, both processes behave remarkably similar: Starting with the same initial conguration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal dierence over all vertices and all times is called single vertex discrepancy. Cooper and Spencer (2006) showed that on ℤ |

1.12. 16:30 | A-2.1 | Martin Krejca | The Benefit of Recombination in Noisy Evolutionary Search Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings meta-heuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper we want to support this claim with mathematical rigor. The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the (µ + 1)-EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm which does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population. |

10.12. 13:30 | A-1.2 | Anton Krohmer | Presentation Zen In this talk, I present the book "Presentation Zen“ by Garr Reynolds, which shows a better way to reach the audience through simplicity and storytelling, and gives tools to confidently design and deliver successful presentations. Whether the reader is in research, technology, business, or education–this book will show them how to take what could look like a really dry presenation and reinvigorate the material in totally fresh (and sometimes interactive!) ways that will make it memorable and resonate with the audience. Garr combines solid principles of design with the tenets of Zen simplicity to help readers along the path to simpler, more effective presentations that will be appreciated, remembered, and best of all, acted upon. |

13.1. 9:15 | A-1.2 | Stefan Neubert | A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks Given a network represented by a graph G=(V,E), we consider a dynamical process of influence diffusion in G that evolves as follows: Initially only the nodes of a given S⊆V are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The question is to determine a small subset of nodes S(a target set) that can influence the whole network. This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known [6] that the above optimization problem is hard to approximate within a factor of 2 |

14.1. 13:30 | A-1.2 | Francesco Quinzan | Categories in Computer Science In this talk, I present the basic notions of category theory, which formalizes mathematical structure and its concepts in terms of a collection of objects and of arrows. The study of categories is an attempt to axiomatically capture what is commonly found in various fields of mathematics by relating them to the structure-preserving functions between them. |

27.1. 9:15 | A-1.2 | Felix Montenegro | Packing a Knapsack of Unknown Capacity We study the problem of packing a knapsack without knowing its capacity. Whenever we attempt to pack an item that does not fit, the item is discarded; if the item fits, we have to include it in the packing. We show that there is always a policy that packs a value within factor 2 of the optimum packing, irrespective of the actual capacity. If all items have unit density, we achieve a factor equal to the golden ratio φ ≈ 1.618. Both factors are shown to be best possible. In fact, we obtain the above factors using packing policies that are universal in the sense that they fix a particular order of the items and try to pack the items in this order, independent of the observations made while packing. We give efficient algorithms computing these policies. On the other hand, we show that, for any α > 1, the problem of deciding whether a given universal policy achieves a factor of α is coNP-complete. If α is part of the input, the same problem is shown to be coNP-complete for items with unit densities. Finally, we show that it is coNP-hard to decide, for given α, whether a set of items admits a universal policy with factor α, even if all items have unit densities. |

27.1. 10:00 | A-1.2 | Hannes Rantzsch | Network Formation Games with Heterogeneous Players and the Internet Structure We study the structure and evolution of the Internet’s Autonomous System (AS) interconnection topology as a game with heterogeneous players. In this network formation game, the utility of a player depends on the network structure, e.g., the distances between nodes and the cost of links. We analyze static properties of the game, such as the prices of anarchy and stability and provide explicit results concerning the generated topologies. Furthermore, we discuss dynamic aspects, demonstrating linear convergence rate and showing that only a restricted subset of equilibria is feasible under realistic dynamics. We also consider the case where utility (or monetary) transfers are allowed between the players. |

4.2. 13:30 | A-1.2 | Yun Kuen Cheung | Asynchronous Market Dynamics and Asynchronous Coordinate Descent In this talk, I will discuss an elegant amortized analysis on two asynchronous iterative processes, asynchronous market dynamics and asynchronous coordinate descent. I will justify the importance of carrying on such asynchronous analysis, and discuss the key ideas behind the amortized analysis. At the end of the talk, I will discuss some plausible future research directions. Part I: Asynchronous Market Dynamics In the studies of markets and general equilibrium theory, one of the central problems is to explain how markets can reach an equilibrium with a price dynamic. In the past 20 years, theoretical computer science has shed new insight on this problem, both from algorithmic and complexity perspectives. We believe that if a market equilibrium is realizable, there ought to be a natural and realistic market dynamic that reaches it quickly. We focus on the most well-known market dynamic, tatonnement. In my prior work with Cole and Devanur, we showed that for Fisher markets with any CES utility functions, tatonnement is equivalent to gradient descent on a convex function, which can be derived explicitly by considering the dual of a convex program called Eisenberg-Gale convex program. This allowed us to show that synchronous and multiplicative tatonnement price updates converge toward a equilibrium. We note that real markets are hugely distributed with no central governance, so prices are typically updated asynchronously, and possibly with outdated information. Thus, we analyze asynchronous tatonnement price updates. We use our amortized analysis technique to show that asynchronous tatonnement also converges to a market equilibrium in the above-mentioned markets, with some bounded-asynchrony assumptions. Part II: Asynchronous Coordinate Descent In recent years, in many applications, particularly in machine learning, require solving huge-scale optimization problems. A strong demand for speeding up these processes via massive parallelism is aroused. A standard method for paralleling is each core performs gradient descent update per coordinate (or per block coordinate). We propose an asynchronous coordinate descent algorithm, which requires little synchronization overhead. We use our amortized analysis technique to show how step sizes should be adjusted to ensure that asynchronous coordinate descent converges to an optimal solution. |

4.2. 16:00 | A-1.1 | Christine Markarian | Towards the Price of Leasing Online Many markets have seen a shift from the idea of buying and moved to leasing instead. Arguably, the latter has been a major catalyst for their success. A major difficulty faced by most businesses is the uncertainty aspect of future demands: It is often not clear which demands will be requested in the future. The `Price of Leasing Online' is the price these businesses pay for not knowing the future while making their leasing decisions. Our aim is to study leasing concepts from an algorithmic perspective. In this talk, I will give an overview of results obtained in attempt to have a sound, systematic, and scientific understanding of how to behave in the face of such uncertainties. |

5.2. 11:00 | A-1.1 | Gregor Lagodzinski | Combinatorics of 2-connected series-parallel graphs Series-parallel graphs are K |

8.2. 11:00 | A-1.1 | Andreas Göbel | Modular Counting and Graph Homomorphisms The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy where counting modulo 2, is intractable. A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (non-modular) counting. A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this talk we will discuss the complexity of counting graph homomorphisms modulo 2. Faben and Jerrum are the first to study the complexity of this problem. They show that for a specific family of target graphs the problem of counting homomorphisms to a graph modulo 2 is computationally easy and conjecture that for every other target graph the problem is computationally hard. They also prove their conjecture when H is a tree. Our results build upon the work of Faben and Jerrum. We first prove their conjecture for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. We then show that for all graphs that countain no 4-cycles the problem of counting graph homomorphisms modulo 2 is either easy to compute or hard to compute, and that there are no target graphs H for which the problem has intermediate complexity. Joint Work with Leslie Goldberg and David Richerby. |

15.2. 13:30 | A-1.1 | Martin Schirneck | Towards an Atlas of Computational Learning Theory A major part of our knowledge about Computational Learning stems from comparisons of the learning power of different learning criteria. These comparisons inform about trade-offs between learning restrictions and, more generally, learning settings; furthermore, they inform about what restrictions can be observed without losing learning power. In this talk I propose a This is joint work with Timo Kötzing. |

3.3. 13:00 | A-1.1 | Anna Melnichenko | A Generalized Routing Open Shop Problem A Routing Open Shop Problem is a combination of the Open Shop Scheduling Problem and the Travelling Salesman Problem. It is assumed that the jobs are located at nodes of an undirected transportation network G. The machines have to travel between the nodes (with unit speed) to process the jobs. All machines use the shortest path between the nodes. The makespan of a feasible schedule is the interval between the moment when the machines start working or moving and the moment when the last machine return to the initial node after finishing all its operations. The goal is to minimize the makespan. |