# Helsinki Algorithms Seminar

Helsinki Algorithms Seminar2018-09-07T14:16:46+03:00

### Description

The Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

### Who and where

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT.

### Contacts

 Prof. Parinya Chalermsook Aalto University Prof. Aristides Gionis Aalto University Prof. Tomi Janhunen Aalto University Prof. Petteri Kaski Aalto University Prof. Mikko Koivisto University of Helsinki Prof. Veli Mäkinen University of Helsinki Prof. Pekka Orponen Aalto University Prof. Juho Rousu Aalto University Prof. Jukka Suomela Aalto University

(e-mail addresses: first.last@aalto.fi or first.last@helsinki.fi — contact Parinya Chalermsook to reserve a slot)

To join the seminar’s mailing list, send an email to ‘hiit-algorithms-list-join@list.aalto.fi’ or see here.

### Meetings

The meetings are on Thursdays, 4pm to 5pm.

For Autumn 2018, the meetings are at T4, Konemiehentie 2 (Otaniemi) and Exactum C122 (Kumpula).

## Multiplicative Weight Updates for Efficient Algorithms and Data Structures: Some New Results from Old Techniques

Date: September 13, 2018 [Rescheduled]

Speaker: Parinya Chalermsook (Aalto University)

Meeting place: Exactum C122 (Kumpula)

Abstract: Multiplicative Weight Update (MWU) is a powerful online prediction technique that has been useful in algorithms design in the past decades. In this talk, I will give an overview of my recent efforts to use the MWU-style updates to design (i) near-linear time algorithms for approximate LP solvers with exponential number of constraints and (ii) efficient online binary search trees that are able to achieve new search properties.

## A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs

Date: September 20, 2018

Speaker: Sumedha Uniyal (Aalto University)

Meeting place: Konemiehentie 2, Room T4 (Otaniemi)

Abstract: A cactus graph is a graph in which any two cycles are edge-disjoint.We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 1/6 fraction of the triangular faces of G. We also show that this ratio cannot be improved by showing a tight lower bound.Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing “dense planar structures” inside any graph: (i) A 1/6 approximation algorithm for, given any graph G, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous 1/11-approximation; (ii) An alternate (and arguably more illustrative) proof of the 4/9-approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind.

## Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity

Date: September 27, 2018
Speaker: Joachim Spoerhase  (Aalto University)
Meeting place: Exactum C122 (Kumpula)
Abstract: We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line segments of minimum total length so that every rectangle is stabbed by some line segment. A line segment stabs a rectangle if it intersects its left and its right boundary. The problem, which we call Stabbing, can be motivated by a resource allocation problem and has applications in geometric network
design. To the best of our knowledge, only special cases of this problem have been considered so far.Stabbing is a weighted geometric set cover problem, which we show to be NP-hard. A constrained variant of Stabbing turns out to be even APX-hard. While for general set cover the best possible approximation ratio is Θ(log n), it is an important field in geometric approximation algorithms to obtain better ratios for geometric set cover problems. Chan et al. [SODA’12] generalize earlier results by Varadarajan [STOC’10] to obtain sub-logarithmic performances for a broad class of weighted geometric set cover instances that are characterized by having low shallow-cell complexity. The shallow-cell complexity of Stabbing instances, however, can be high so that a direct application of the framework of Chan et al. gives only logarithmic bounds. We still achieve a constant-factor approximation by decomposing general instances into what we call laminar instances that have low enough complexity.

Our decomposition technique yields constant-factor approximations also for the variant where rectangles can be stabbed by horizontal and vertical segments and for two further geometric set cover problems.

## Maximizing the diversity of exposure in a social network

Date: October 04, 2018 16:15–17:00
Place: Konemiehentie 2, Room T4 (Otaniemi)
Speaker: Cigdem Aslay

Title: Maximizing the diversity of exposure in a social network

Abstract: In this talk I will present our recent result that provides a novel approach to contribute towards bursting filter bubbles. We formulate the problem as a task of recommending news articles to selected users with the aim to maximize the overall diversity of information exposure in a social network. We consider a realistic setting where we take into account the political leanings of users and articles, and the probability of users to further share articles. We show that this problem is a challenging generalization of the influence maximization problem, which is NP-hard, and it corresponds to the problem of maximizing a monotone submodular function subject to a matroid constraint on the allocation of articles to users. We introduce the notion of random reverse co-exposure sets and a set of estimation techniques based on martingales for efficiently estimating expected diversity of exposure. Accordingly, we devise a scalable instantiation of the greedy algorithm that provides (1/2-epsilon)-approximation to the optimum with high probability.

## Multiplicative Weight Updates for Efficient Algorithms and Data Structures: Some New Results from Old Techniques

Date: October 11, 2018 16:15–17:00
Place: Konemiehentie 2, Room T4 (Otaniemi)
Speaker: Parinya Chalermsook

Title: Multiplicative Weight Updates for Efficient Algorithms and Data Structures: Some New Results from Old Techniques

Abstract: Multiplicative Weight Update (MWU) is a powerful online prediction technique that has been useful in algorithms design in the past decades. In this talk, I will give an overview of my recent efforts to use the MWU-style updates to design (i) near-linear time algorithms for approximate LP solvers with exponential number of constraints and (ii) efficient online binary search trees that are able to achieve new properties.

## On the Complexity of Symmetric Polynomials

Date: October 18, 2018 16:15–17:00
Place: Konemiehentie 2, Room T4 (Otaniemi)
Speaker: Gorav Jindal

Title : On the Complexity of Symmetric Polynomials

Abstract :It is an easy exercise to show that all symmetric Boolean functions are easy to compute (corresponding language is in the complexity class TC^0). Lipton and Regan ([1]) ask whether the same is also true for symmetric polynomials? They ask whether “Understanding the arithmetic complexity of symmetric polynomials is enough ?” In this work, we answer this question in affirmative.The fundamental theorem of symmetric polynomials states that for a symmetric polynomial f_sym \in C[x_1, x_2, …, x_n], there exists a unique “witness” f \in  C[y_1, y_2, .., y_n] such that f_sym = f(e_1, e_2, .., e_n), where the e_i’s are the elementary symmetric polynomials.We study the arithmetic complexity L(f) of the witness f as a function of the arithmetic complexity L(f_sym) of f_sym . We show that the arithmetic complexity L(f) of f is bounded by poly(L(f_sym ), deg(f), n). To the best of our knowledge, prior to this work only exponential upper bounds were known for L(f). The main ingredient in our result is an algebraic analogue of Newton’s iteration on power series.As a corollary of this result, we show that if VP \neq VNP then there exist symmetric polynomial families which have super-polynomial arithmetic complexity.
This is a joint work with Prof. Markus Bläser (Department of Computer Science, Saarland University)
[1] : https://rjlipton.wordpress.com/2009/07/10/arithmetic-complexity-and-symmetry/

## Rank Vertex Cover as a Natural Problem for Algebraic Compression

Date: October 25, 2018 16:15–17:00
Place: Exactum C122 (Kumpula)
Speaker: Syed Meesum (Wroclaw)

Title: Rank Vertex Cover as a Natural Problem for Algebraic Compression

Abstract: The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a longstanding, notorious open problem in Parameterized Complexity. Six years ago, the breakthrough work by Kratsch and Wahlstr ̈om on representative sets finally answered this question in the affirmative [FOCS 2012]. In this talk, I will present an alternative, algebraic compression of the Vertex Cover Above LP problem into the Rank Vertex Cover problem. Here, the input consists of a graph G, a parameter k, and a bijection between V(G) and the set of columns of a representation of a matroid M, and the objective is to find a vertex cover whose rank is upper bounded by k.

## Extensor-coding: A unified algebraic approach to the longest path problem

Date: November 01, 2018 16:15–17:00
Place: Konemiehentie 2, Room T4 (Otaniemi)
Speaker: Cornelius Brand (Saarland)

Title: Extensor-coding: A unified algebraic approach to the longest path problem

Abstract: We devise an algorithm that approximately computes the number of paths of length k in a given directed graph with n vertices up to a multiplicative error of 1 ± ε. Our algorithm runs in time 4^k*(n+m)*poly(k)/ε². The algorithm is based on associating with each vertex an element in the exterior (or, Grassmann) algebra, called an extensor, and then performing computations in this algebra. This connection to exterior algebra generalizes a number of previous approaches for the longest path problem and is of independent conceptual interest. Using this approach, we also obtain a deterministic 2^k*poly(n) time algorithm to find a k-path in a given directed graph that is promised to have few of them. Our results and techniques generalize to the subgraph isomorphism problem when the subgraphs we are looking for have bounded pathwidth. Finally, we also obtain a randomized algorithm to detect k-multilinear terms in a multivariate polynomial given as a general algebraic circuit. To the best of our knowledge, this was previously only known for algebraic circuits not involving negative constants.

## Coresets for k-Means clustering

Date: November 08, 2018 16:15–17:00
Place: Exactum C122 (Kumpula)
Speaker: Michael Mathioudakis

Speaker: Michael Mathioudakis (University of Helsinki)

Title: Coresets for k-Means clustering

Abstract:
Coresets are compact representations of data, accompanied with a guarantee that models trained on them have competitive performance with models trained on all the data. In this talk, I will discuss state-of-the-art algorithms on coresets for k-Means by Bachem et.al. [1], presented earlier this year at the KDD conference.

[1] Bachem, Olivier, Mario Lucic, and Andreas Krause. “Scalable k-Means Clustering via Lightweight Coresets.” International Conference on Knowledge Discovery and Data Mining (KDD). 2018.

## The effects of teamwork in time-inconsistent planning

Date: November 15, 2018 16:15–17:00
Place: Konemiehentie 2, Room T4 (Otaniemi)
Speaker: Aris Gionis

Title: The effects of teamwork in time-inconsistent planning

Abstract: The problem of inconsistent planning in decision making, which leads to undesirable effects such as procrastination, has been studied in the behavioral-economics literature, and more recently in the context of computational behavioral models. Individuals, however, do not function in isolation, and successful projects most often rely on team work. Team performance does not depend only on the skills of the individual team members, but also on other collective factors, such as team spirit and cohesion. It is not an uncommon situation that a hard-working individual has the capacity to give a good example to her team-mates and motivate them to work harder.

In this work we adopt the model of Kleinberg and Oren (EC’14) on time-inconsistent planning, and extend it to account for the influence of procrastination within the members of a team. Our first contribution is to model collaborative work so that the relative progress of the team members, with respect to their respective subtasks, motivates (or discourages) them to work harder. We compare the total cost of completing a team project when the team members communicate with each other about their progress, with the corresponding cost when they work in isolation. Our main result is a tight bound on the ratio of these two costs, under mild assumptions. We also show that communication can either increase or decrease the total cost.

We also consider the problem of assigning subtasks to team members, with the objective of minimizing the negative effects of teamwork. We show that while a simple problem of forming teams of two members can be solved in polynomial time, the problem of assigning n tasks to n agents is NP-hard.

This is joint work with Aris Anagnostopoulos and Nikos Parotsidis.

## Probabilistic tensors and opportunistic Boolean matrix multiplication

Date: November 22, 2018 16:15–17:00
Place: Exactum C122 (Kumpula)

Title: Probabilistic tensors and opportunistic Boolean matrix multiplication

Abstract: We study probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. These probabilistic extensions enable improvements over their deterministic counterparts for specific tensors of interest, starting from the tensor $\langle 2,2,2 \rangle$ that represents $2\times 2$ matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank of $\langle 2,2,2 \rangle$ is 7 [V. Strassen, Numer. Math. 13 (1969); J. E. Hopcroft and L. R. Kerr, SIAM J. Appl. Math. 20 (1971); S. Winograd, Linear Algebra Appl. 4 (1971); J. M. Landsberg, J. AMS 19 (2006)] we show that the probabilistic rank of $\langle 2,2,2 \rangle$ is at most 6+\frac{6}{7} and the probabilistic border rank is at most 6+\frac{2}{3}. By submultiplicativity, this leads immediately to novel randomized algorithm designs, such as algorithms for Boolean matrix multiplication as well as detecting and estimating the number of triangles in graphs.

Joint work with Matti Karppa (Aalto University).

## Reasoning in Bayesian Opinion Exchange Networks is Computationally Hard

Date: November 29, 2018 16:15–17:00
Place: Konemiehentie 2, Room T4 (Otaniemi)
Speaker: Jan Hazla (MIT)

Title: Reasoning in Bayesian Opinion Exchange Networks is Computationally Hard

Abstract: Bayesian models of opinion exchange are extensively studied in economics, dating back to the work of Aumann on the agreement theorem. An important class of such models features agents arranged on a network (representing, e.g., social interactions), with the network structure determining which agents communicate with each other. It is often argued that the Bayesian computations needed by agents in such models are difficult, but prior to our work there were no rigorous arguments for such hardness.

We consider a well-studied model where fully rational agents receive private signals indicative of an unknown state of the world. Then, they repeatedly announce the state of the world they consider most likely to their neighbors, at the same time updating their beliefs based on their neighbors’ announcements.

I will discuss our complexity-theoretic results establishing hardness of agents’ computations in this model. Specifically, we show that these computations are NP-hard and extend this result to PSPACE-hardness. We show hardness not only for exact computations, but
also that it is computationally difficult even to approximate the rational opinion in any meaningful way.

Joint work with Ali Jadbababie, Elchanan Mossel and Amin Rahimian.