Helsinki Algorithms Seminar

Helsinki Algorithms Seminar2018-09-07T14:16:46+00: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).

Upcoming meetings

September 2018

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.

October 2018

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.