AlgoMaNet - summer 2021

Location

The two courses scheduled for the summer 2021 will take place at Charles University in its building at Malostranské náměstí 25. The courses will be delivered in the hybrid mode, with both in-person and remote participation of students. The in person lectures will take place in the Charles University building at Malostranské náměstí 25 in the lecture room S1; those registered to participate remotely will receive information on how to connect via Zoom by e-mail.

Registration

The registration is free. To register, send an e-mail to Darina Boukalová (boukalova@fi.muni.cz) by Friday August 6, 2021. 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, whether you will participate physically or remotely, 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.

Participation of Charles University in the network is supported by the RSJ foundation.

Pavel Hubáček (Charles University): Foundations of theoretical cryptography

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

Schedule: August 23 - August 27, 2021

Note that there will be no exercise session on Wednesday August 25.

Michal Koucký (Charles University): Fine-grained complexity (Aug 30-Sep 3)

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 striking relationships between their complexities.

Schedule: August 30 - September 3, 2021

Note that there will be no morning lecture on Friday September 3.