Michal Koucký got his Ph.D. in 2003 from Rutgers Univ., followed by postdocs at McGill Univ., Montreal, Canada (2003-2004) and CWI, Amsterdam, The Netherlands (2005). After that he was a researcher in the Institute of Mathematics of the Czech Academy of Sciences until 2013, when he moved to Charles University where he currently serves as the director of the Computer Science Institute of Charles University (IÚUK). He was a visiting professor at Univ. Toronto, Canada (2011) and Aarhus Univ., Denmark (2012).

His expertise is in computational complexity, randomized computation, pseudorandomness and algorithms.  In the area of randomized computation he is known for introduction of exploration sequences, combinatorial objects used by algorithms for graph traversal, that were explicitly constructed by Reingold (2005) in his landmark paper. He did seminal work on parallel random walks in Alon et al. (2011) and random walks on dynamic graphs in Chen, Koucký and Lotker (2008). He introduced the model of catalytic computation with application to space-efficient algorithms (Buhrman et al., 2014). For his breakthrough results on edit distance he received a best paper award at FOCS 2018. In 2021, he received the Research Award of the Ministry of Education.

AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

In this talk I will present a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness and ignoring poly-log factors). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ.
This decomposition has applications to edit distance sketching and streaming approximate pattern matching algorithms.
Joint work with Sudatta Bhattacharya.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

988 5655 4581

passcode not visible

logged in users only

The speaker will give the talk in-person in room 024 at E1 4.
The set-up of the talk will be hybrid. If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.