AlgoMaNet - Algorithms and Mathematics Network

AlgoMaNet is a network based on a collaboration among four Central European universities (Charles University in Prague, Jagiellonian University in Kraków, Masaryk University in Brno and the University of Warsaw) in the areas of discrete algorithms, discrete mathematics and theoretical computer science. The network offers lectures on advanced topics primarily to MSc and PhD students affiliated with one of the four universities. The aims of the program resemble those of the intensive programs for senior undergraduate and graduate students organized by Charles University in 2014, in 2016 and 2018.

Registration

The registration is free. To register, send an e-mail to Darina Boukalová (boukalova@fi.muni.cz) by October 18, 2019 October 22, 2019. Please register even if you intend to attend a locally organized course. In your registration e-mail, please indicate who you are (your name and affiliation in particular), which lectures you would like to attend and what level of support is necessary for you to participate.

We may be able to accept registrations by students not affiliated with either of the four universities in the network. These registrations will be confirmed after the registration deadline if space constraints permit.

Courses in the academic year 2019/20

In the academic year 2019/20, there will be seven intensive courses. The courses are organized in two-week blocks, and it is possible (and actually expected) to attend only some of the seven courses. Three courses are offered as intensive courses with a lecture held on each weekday during the two-week block, two as one-week courses with two lectures each day, and two as one-week courses with a single lecture each day. A part of each weekday will be also devoted to solving exercises given during the lectures. While the schedule will allow one to attend all courses in a block, it is possible to register for a single course in the block.

  • January 13-January 24, University of Warsaw
    Mikołaj Bojańczyk (University of Warsaw): Automata, semigroups and logic (Jan 13-17)
    Michał Pilipczuk (University of Warsaw): Combinatorics and algorithms for sparse graphs (Jan 20-24)
  • January 27-February 7, Masaryk University, Brno
    Andrzej Grzesik (JU Kraków): Extremal graph theory
    Petr Hliněný (MU Brno): Geometric and topological graph theory (half course, Feb 3-7)
    Dan Kráľ (MU Brno): Regularity method (half course, Jan 27-31)
  • May 4-May 15, Charles University, Prague
    Pavel Hubáček (Charles University): Foundations of theoretical cryptography
    Michal Koucký (Charles University): Fine-grained complexity
Syllabus for the course "Foundation of theoretical cryprograhy"

The central aim of modern theoretical cryptography is to characterize the minimal necessary assumptions for solving a particular cryptographic task. This course introduces general cryptographic assumptions and their applications in constructions of cryptographic primitives and provably secure protocols.

  • Basics
    • one-time pad, perfect security, computational security, indistinguishability
    • pseudorandom generators and computational one-time pad
    • pseudorandom functions and permutations
  • Data integrity
    • message authentication codes and cryptographic hashing
    • signature schemes
    • applications in distributed cryptographic currencies: Bitcoin
  • Zero-knowledge
    • definitions and basic protocols
    • commitment schemes
    • applications in cryptographic currencies: Zerocash
Syllabus for the course "Fine-grained complexity"

The series of lectures will provide a tutorial on fine-grained complexity. Fine-grained complexity which emerged over the past decade maps the landscape of problems solvable in polynomial time, and provides insight into their exact asymptotic complexities. By building a formal connection between the complexity of problems like the Longest Common Subsequence and the complexity of solving NP-complete problems such as SAT it provides a plausible explanation why despite lots of effort we did not manage to improve on the trivial quadratic or cubic algorithms for such problems. The course will cover the Strong Exponential Time Hypothesis (SETH) and its variants, problems in P such as Orthogonal Vectors Problem, 3SUM, Longest Common Subsequence and many others, and exhibit a striking relationships between their complexities.

Contact details

The program is overseen by the steering committee assisted by Darina Boukalová (boukalova@fi.muni.cz) from Masaryk University, Brno.

Steering committee

  • Zdeněk Dvořák (Charles University, Prague)
  • Daniel Kráľ (Masaryk University, Brno)
  • Szymon Toruńczyk (University of Warsaw)
  • Bartosz Walczak (Jagiellonian University, Kraków)