Helsinki Algorithms Seminar

Helsinki Algorithms Seminar History 2018-06-28T16:08:49+00:00

History of Past Meetings

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, 14:15–15:00 (joint slot with CS Forum)

  • Fabian Reiter, “Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment”, T-Building T3 (Otaniemi)

Thu 31 May

  • [No seminar]

Thu 7 June

  • Rohit Babbar, “Algorithms for Extreme Multi-label Classification”, T-Building T5 (Otaniemi)

Thu 14 June

  • [No seminar]

Thu 21 June, 13:15–14:00

  • David Gleich, “Low-rank methods for network alignment”, T-Building T5 (Otaniemi)

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)

Thu 23 November

  • Veli Mäkinen, “Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics”, T-Building T5 (Otaniemi)

Thu 30 November

  • Janne H. Korhonen, “New Classes of Distributed Time Complexity”, Exactum B222 (Kumpula)

Thu 7 December

  • [No seminar on Independence Day week]

Thu 14 December

  • Bernhard Bliem, “Answer Set Programs with Groundings of Small Treewidth”, 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

Thu 8 June
  • 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)
Thu 27 October
  • Joel Rybicki, “On simultaneous responses to external stimuli”, Exactum B119/Kumpula (paper)
Thu 3 November
  • Janne H. Korhonen, “Fast and practical generalised position weight matrix matching”, T4/Otaniemi (paper)
Thu 10 November
  • Antti Honkela, “Efficient differentially private learning improves drug sensitivity prediction”, Exactum B119/Kumpula (paper)
Thu 17 November
  • David Karpuk, “Efficient Algorithms for Solving the Closest Vector Problem and Applications to Communications Engineering”, T4/Otaniemi
Thu 24 November
  • Christopher Purcell, “Labelling Grids Locally”, Exactum B119/Kumpula
Thu 1 December
  • Tuomo Lempiäinen, “On the existence of constant-space non-constant-time distributed algorithms”, T4/Otaniemi
Thu 8 December
  • Matti Karppa, “Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time”, Exactum B119/Kumpula (paper)
Thu 15 December
  • [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.