Helsinki Algorithms Seminar

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. 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: [email protected] or [email protected] — contact P.K. if you want to reserve a slot)

To join the seminar's mailing list, send an email to '[email protected]' or see here.

Meetings

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

Spring 2018

Thu 18 January

• Lauri Himanen, "Towards Data-driven Materials Science: Opportunities and Challenges", T-Building T5 (Otaniemi)

Thu 25 January

• Laszlo Kozma, "Selection from heaps, row-sorted matrices and X + Y using soft heaps", Exactum B222 (Kumpula)

Thu 1 February

• Parinya Chalermsook, "Dynamic Programs meet Linear Programs: Approximation Algorithms for Group Steiner Problems on Low-Treewidth Graphs", T-Building T5 (Otaniemi)

Thu 8 February

• Keijo Heljanko, "Minimizing Test Suites with Unfoldings of Multithreaded Programs", Exactum B222 (Kumpula)

Thu 15 February

• Gorav Jindal, "On Approximation of Rank of Symbolic Matrices", T-Building T5 (Otaniemi)

Thu 22 February

• Mikaël Rabie, "Distributed Recoloring", Exactum B222 (Kumpula)

Thu 1 March

• Fabian Kuhn, "On the Role of Randomization in Local Distributed Graph Algorithms", T-Building T5 (Otaniemi)

Thu 8 March

• Alkida Balliu, "Certification of Compact Low-Stretch Routing Schemes", Exactum B222 (Kumpula)

Thu 15 March

• Charalampos Tsourakakis, "Predicting Positive and Negative Links with Noisy Queries: Theory & Practice", T-Building T5 (Otaniemi)

Thu 22 March

• Topi Talvitie, "Counting Linear Extensions in Practice", Exactum B222 (Kumpula)

Thu 29 March

• Sergiy Vorobyov, "An Algebraic Approach to Rank-Constrained Semi-Definite Programs with Sum-of-Squares Constraints", T-Building T5 (Otaniemi)

Thu 5 April

• Wanchote Jiamjitrak, "An Illustrative Charging Scheme for Dynamic BST", Exactum B222 (Kumpula)

Thu 12 April

• Ameet Gadekar, "Graph Coloring via Semidefinite Programming", T-Building T5 (Otaniemi)

Thu 19 April

• Dennis Olivetti, "Pareto and Nash stability in Social Distance Games", Exactum B222 (Kumpula)

Thu 26 April

• Jussi Rintanen, "Intelligent Automation in Software Production", T-Building T5 (Otaniemi)

Thu 3 May

• Petteri Kaski, "Moderately-exponential-time integer factorization", Exactum B222 (Kumpula)

Thu 10 May

• [No seminar]

Thu 17 May

•  Chris Brzuska, "On the existence of one-way functions", Exactum B222 (Kumpula)

Thu 24 May

• Mihai Florea, "An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems", T-Building T5 (Otaniemi)

Thu 31 May

• TBA, Exactum B222 (Kumpula)

Thu 7 June

• Rohit Babbar, TBA, T-Building T5 (Otaniemi)

Thu 14 June

• TBA, Exactum B222 (Kumpula)

Autumn 2017

Thu 5 October

• Mikko Koivisto, "Treewidth and counting linear extensions revisited", Exactum B222 (Kumpula)

Thu 12 October

• Antti Ukkonen, "Data analysis with relative distance comparisons", T-Building T5 (Otaniemi)

Thu 19 October

• Petteri Kaski, "Delegatable and error-tolerant algorithms", Exactum B222 (Kumpula)

Thu 26 October

• Jarno Alanko, "Revisiting the classical greedy shortest common superstring algorithm", T-Building T5 (Otaniemi)

Thu 2 November

• Jukka Suomela, "Sinkless orientations, balanced orientations, and balanced splitting", Exactum B222 (Kumpula)

Thu 9 November

• Hector Ferrada, "Hybrid Indexing", T-Building T5 (Otaniemi)

Thu 16 November

• Lukasz Kowalik, "Improving TSP tours using dynamic programming over tree decompositions", Exactum B222 (Kumpula)

Spring 2017

Thu 12 January

• Petteri Kaski, "The near-linear-time toolbox for univariate polynomials", Learning Centre 126 Juho (Otaniemi)

Thu 19 January

• Christopher Purcell, "Role colourings and hereditary properties of graphs", Exactum B119 (Kumpula)

Thu 26 January

• [No seminar]

Thu 2 February

• Antti Laaksonen, "Constructing codes using transitive permutation groups", Exactum B119 (Kumpula)

Thu 9 February

• Sumedha Uniyal, "Capacitated k-Median Problem", Learning Centre 126 Juho (Otaniemi)

Thu 16 February

• [No seminar]

Thu 23 February

• Ragnar Freij, "Rota's conjecture/theorem, and applications in information theory", Learning Centre 126 Juho (Otaniemi)

Thu 2 March

• Lasse Leskelä, "Supermodular functions and stochastic orders", Exactum B119 (Kumpula)

Thu 9 March

• Janne H. Korhonen, "Towards a complexity theory for the congested clique", Learning Centre 126 Juho (Otaniemi)

Thu 16 March

• Dmitrii Kosolobov, "Construction of a compressed Lempel-Ziv-based data structure", Exactum B119 (Kumpula)

Thu 23 March

• [No seminar]

Thu 30 March

• Syamantak Das, "On minimizing the makespan with bag constraints", Exactum B119 (Kumpula)

Thu 6 April

• Bundit Laekhanukit, "Hardness of Approximating Polynomial-Time Solvable Problems -- Similarity Search", Learning Centre 126 Juho (Otaniemi)

Thu 13 April

• Canceled, to be postponed to another date: Topi Talvitie, "The mixing of Markov chains on linear extensions in practice", Exactum B119 (Kumpula)

Thu 20 April

• Thatchaphol Saranurak, "Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n^{1/2-\epsilon})-Time", Learning Centre 126 Juho (Otaniemi)

Thu 27 April

• Joel Rybicki, "Points on a plane!", Exactum B119 (Kumpula)

Thu 4 May

• Jukka Suomela, "Understanding Computation with Computation", Learning Centre 126 Juho (Otaniemi)

Thu 11 May

• Parinya Chalermsook, "From Gap-ETH to FPT Inapproximability: Cliques, Dominating Set, and More", Exactum B119 (Kumpula)

Thu 18 May

• Mario Di Francesco, "Perfectly Periodic Scheduling of Collective Data Streams", Learning Centre 126 Juho (Otaniemi)

Thu 25 May

• [Ascension Day -- no seminar]

Thu 1 June

• Large Structures Mini-Workshop, 1:00pm--5:30pm M240 Otakaari 1 (Otaniemi)

• Olli Saarikivi, "Minimization of Symbolic Transducers", Learning Centre 126 Juho (Otaniemi)

Autumn 2016

Thu 8 September

• Roland Meyer, "Summaries for Context-Free Games", T4/Otaniemi

Thu 15 September

• Parinya Chalermsook, "Graph products, hardness of approximation, and beyond", Exactum B119/Kumpula

Thu 22 September

• Nikos Parotsidis, "Decremental Single-Source Reachability and Strongly Connected Components in \widetilde{O}(m \sqrt{n}) Total Update Time", T4/Otaniemi

Thu 29 September

• Polina Rozenshtein, "Temporal PageRank", Exactum B119/Kumpula

Thu 6 October

• Leena Salmela, "Safe solutions for gap filling in genomic assemblies", T4/Otaniemi (paper, paper)

Thu 13 October

• Jukka Kohonen, "How do you find arbitrarily large additive bases with a finite combinatorial search? A new parametrized construction", Exactum B119/Kumpula (paper)

Thu 20 October 

• Kustaa Kangas, "Counting linear extensions of sparse posets", T4/Otaniemi (paper)

• Joel Rybicki, "On simultaneous responses to external stimuli", Exactum B119/Kumpula (paper)

• Janne H. Korhonen, "Fast and practical generalised position weight matrix matching", T4/Otaniemi (paper)

• Antti Honkela, "Efficient differentially private learning improves drug sensitivity prediction", Exactum B119/Kumpula (paper)

• David Karpuk, "Efficient Algorithms for Solving the Closest Vector Problem and Applications to Communications Engineering", T4/Otaniemi

• Christopher Purcell, "Labelling Grids Locally", Exactum B119/Kumpula

• Tuomo Lempiäinen, "On the existence of constant-space non-constant-time distributed algorithms", T4/Otaniemi

• Matti Karppa, "Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time", Exactum B119/Kumpula (paper)

• [free -- T4/Otaniemi]

Spring 2016

Thu 14 January

• Mika Göös, "Communication Complexity vs. Partition Numbers", TUAS TU6/Otaniemi

Thu 21 January

• Jukka Kohonen, "Fast zeta transform in semimodular lattices -- the art of taking many related sums", Exactum B119/Kumpula

Thu 28 January

• Jukka Suomela, "Non-local probes do not help with graph problems" (paper, slides), TUAS TU6/Otaniemi

Thu 4 February

• Petteri Kaski, "Reliability and verifiability in parallel hardware and algorithm design", Exactum B119/Kumpula

Thu 11 February

• Petteri Kaski, "How proofs are prepared at Camelot" (paper), TUAS TU6/Otaniemi

Thu 18 February

• Jukka Suomela, "Distributed computing and intermediate problems" (paper, slides), Exactum B119/Kumpula

Thu 25 February

• Alexandru Tomescu, "Where do we come from? The flow of (meta)genomic reads back home" (paper), TUAS TU6/Otaniemi

Thu 3 March

• Veli Mäkinen, "Doing things with less data structures and filling gaps in the story", Exactum B119/Kumpula

Thu 10 March

• Tapani Raiko, "Representing Natural Data in Vector Spaces using Deep Learning", TUAS TU6/Otaniemi

Thu 17 March

• Kevin Perrot, "Emergence on sandpile models", Exactum B119/Kumpula

Thu 24 March

• [Easter break -- no seminar]

Thu 31 March

• Kaie Kubjas, "The geometry of nonnegative and positive semidefinite rank", TUAS TU6/Otaniemi

Thu 7 April

• Jiaheng Lu, "Holistic job optimization for big data analytics" (paper), Exactum B119/Kumpula

Thu 14 April

• Pierre-Etienne Meunier, "Asynchronous distributed computing and category theory", T4/Otaniemi

Thu 21 April

• Valtteri Niemi, "Garbling and Applications", Exactum B119/Kumpula

Thu 28 April

• Joel Rybicki, "Dazed and confused: How to find a common beat?", T4/Otaniemi

Thu 5 May

• [Ascension Day -- no seminar]

Thu 12 May

• Colva Roney-Dougal, "Proving hyperbolicity in polynomial time", T4/Otaniemi

Thu 19 May

• Alex Jung, "Graph Signal Recovery using Convex Optimization", Exactum B119/Kumpula

Thu 26 May

• Padraig Ó Catháin, "Correlation amplifiers for binary vectors", T4/Otaniemi

Thu 2 June

• Ralf Eggeling, "Searching optimal parsimonious context trees", Exactum B119/Kumpula

Tue 7 June

• Orr Fischer, "Public vs. Private Randomness in Simultaneous Multi-Party Communication Complexity", T4/Otaniemi

Thu 9 June

• [Aalto CS Summer Excursion -- no seminar]

Thu 16 June

• Jan Holub, "Approximate String Matching for Self-Indexes", Exactum B119/Kumpula

Fall 2015

Thu 10 September

• Juho Lauri, "On the Complexity of Rainbow Coloring Problems", Exactum C222/Kumpula

Thu 17 September

• Jukka Suomela, "Local coordination and symmetry breaking" (paper, slides), TUAS TU6/Otaniemi

Thu 24 September

• Adrian Kosowski, "Discrete Lotka-Volterra Population Protocols: Convergence, Majority Amplification, and Equity for Under-Represented Minorities", Exactum C222/Kumpula

Thu 1 October

• Joel Rybicki, "Efficient counting with optimal resilience" & Jara Uitto, "Fault-Tolerant ANTS", TUAS TU6/Otaniemi

Thu 8 October

• Pekka Parviainen, "Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number", Exactum C222/Kumpula

Thu 22 October

• Christopher Purcell, "Boundary properties of graphs and their applications", Exactum C222/Kumpula

Thu 5 November

• Przemysław Uznański, "Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences", Exactum B121/Kumpula

Thu 26 November

• Nikolaj Tatti, "Strongly polynomial efficient approximation scheme for segmentation", TUAS TU6/Otaniemi

Thu 3 December

• Tuomo Lempiäinen, "A lower bound for the distributed Lovász local lemma", Exactum B121/Kumpula

Thu 10 December

• Eric Malmi, "Integer programming for collective entity resolution", TUAS TU6/Otaniemi

Thu 17 December

• Matti Karppa, "Finding Outlier Correlations in Subquadratic Time", TUAS TU6/Otaniemi

Spring 2015

Thu 15 January

• Przemysław Uznański, "Tight tradeoffs for approximating palindromes in streams", Exactum B119/Kumpula

Thu 22 January

• Juho Rousu, "Multilabel Classification through Random Tree Approximation", T5/Otaniemi

Thu 29 January

• Martin Gebser, "Space-efficient enumeration in modern Boolean constraint solving", Exactum B119/Kumpula

Thu 5 February

• Przemysław Uznański, "Lock-in Problem for Parallel Rotor-router Walks", T5/Otaniemi

Thu 12 February

• Enrico Bartolini, "Exact algorithms for vehicle routing problems", Exactum B119/Kumpula

Thu 19 February

• Djamal Belazzougui, "Time-optimal string indexing and analysis in small space", T5/Otaniemi

Thu 26 February

• Louis Theran, "Matroid regression", B119/Kumpula

Thu 5 March

• Lasse Leskelä, "Markov couplings, stochastic orders, and stochastic relations", T5/Otaniemi

Thu 12 March

• Przemysław Uznański, "On the power of one bit: How to explore a graph when you cannot backtrack?", B119/Kumpula

Thu 19 March

• Petteri Kaski, "Subset sum in the absence of concentration", T5/Otaniemi

Thu 26 March

• Keijo Heljanko, "Big Data Platforms for Next Generation Sequencing Data Processing", B119/Kumpula

Thu 2 April

• [Easter break -- no seminar]

Thu 9 April

• Jukka Kohonen, "Algorithmic number theory: Searching for additive bases", B119/Kumpula

Thu 16 April

• Cordian Riener, "Symmetry and efficiency in geometric problems", T5/Otaniemi

Thu 23 April

• Joel Rybicki, "Towards optimal synchronous counting", B119/Kumpula

Thu 30 April

• [1st of May -- no seminar]

Thu 7 May

• Pierre-Étienne Meunier, "A pumping lemma for noncooperative tile assembly", B119/Kumpula

Thu 14 May

• [Helatorstai -- Ascension Day -- no seminar]

Thu 21 May

• Topi Talvitie, "Shortest path to a segment and quickest visibility queries", B119/Kumpula

Thu 28 May

• Juho Hirvonen, ”Distributed load balancing”, T5/Otaniemi

Thu 4 June

• Abdulmelik Mohammed, "Designs and algorithms for folding DNA into custom nanoscale polyhedra", **T3**/Otaniemi

Thu 11 June

• Johannes Wallner, "Abstract dialectical frameworks: Semantics and complexity", B119/Kumpula

Fall 2014

Thu 23 October

• Jukka Suomela, "Median filtering is equivalent to sorting" (paper, slides), TU5/Otaniemi.

Thu 30 October

• Petteri Kaski, "Motif search for large graphs", Exactum B121/Kumpula

Thu 6 November

• Travis Gagie, "Searching and indexing genomic databases via kernelization", T5/Otaniemi

Thu 13 November

• Janne H. Korhonen, "Algebraic tricks for distributing computation", Exactum B121/Kumpula

Thu 20 November

• Leena Salmela, "Assembling a butterfly genome", T5/Otaniemi

Thu 27 November

• Juho-Kustaa Kangas, "Learning chordal Markov networks by dynamic programming", Exactum B121/Kumpula

Spring 2014

Fri 10 January

• Aristides Gionis, "Maximization of submodular set functions", B119/Kumpula.

Fri 17 January

• Dieter Kratsch, "Minimal Dominating Sets in Graphs: Enumeration, Combinatorial Bounds and Graph Classes", TU6/Otaniemi.

Fri 24 January

• Nikolaj Tatti, "PAV algorithm for solving linear isotonic regression, or how to find the densest interval in a sequence really really really fast", B119/Kumpula.

Fri 31 January

• Petteri Kaski, "The low rank phenomenon", TU6/Otaniemi.

Fri 7 February

• Stefan Schmid, "Virtual Network Embedding Algorithms with Good and Bad Intentions", B119/Kumpula.

Fri 14 February

• Barbara Keller, "Convergence in (Social) Influence Networks", TU6/Otaniemi.

Fri 21 February

• Travis Gagie, "Jumbled Pattern Matching", B119/Kumpula.

Fri 28 February

• Janne Korhonen, "The strong exponential time hypothesis and lower bounds for polynomial-time problems", TU6/Otaniemi.

Fri 14 March

• Juho Hirvonen, "Algorithmic barriers from phase transitions", TU6/Otaniemi.

Fri 21 March

• Kustaa Kangas, "Shearer's entropy lemma with applications in subgraph counting", B119/Kumpula.

Fri 28 March

• Jukka Suomela, "Large cuts with local algorithms" (demo, slides), TU6/Otaniemi.

Fri 4 April

• Petteri Kaski, "Graph motifs", B119/Kumpula.

Fri 11 April

• David Karpuk, "An Introduction to LDPC Codes", TU6/Otaniemi.

Fri 25 April

• Camilla Hollanti, "Coding and decoding in fading channels", B119/Kumpula.

Fri 9 May

• Christoph Lenzen, "Distributed Shortest-Path Algorithms", T5/Otaniemi.

Fri 16 May

• Rémi Lemoy, "A novel local search based on variable-focusing for random K-SAT", B119/Kumpula.

Fri 23 May

• Tomi Janhunen, "Learning chordal Markov networks by constraint satisfaction", T5/Otaniemi.

Fall 2013

Fri 29 November

• Petteri Kaski, "The good, the bad, and the isolation lemma", TU5/Otaniemi.

Fri 13 December

• Mikko Koivisto, "Counting by optimization revisited: a look at ``Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization''" (Ermon et al. ICML'13), C220/Kumpula.

Links

Here are some other Helsinki area seminars that may be of interest to algorithmics people:

• HIIT Seminars
• ANTA Seminar
• Helsinki Logic Seminar