We announce that the registration for the summer admission process is now open!
Those interested in attending the Security and Applied Logic Master Program should register here until the 15th of July 2022.
Follow the Faculty’s Admission webpage here for more information and updates!
The weekly Logic Seminar (Thu 10-12) and LOS Research Center Seminar (Tue 14-16) will now also take place physically in the Google Room. Students of the SAL Master are strongly encouraged to participate and engage in the research activities.
The Practical Training options for first year SAL students has been posted at the address:
UNbreakable Romania starts the registration for the autumn-winter season of the national cybersecurity contest. Check the official website: https://unbreakable.ro/stiri/au-inceput-inscrierile-la-unbreakable-romania-sezonul-de-toamna-iarna-2021/
A team of the University of Bucharest placed first in the Competition Unbreakable Romania (season spring-summer 2021). Congratulations to Dragos Albastroiu, Mihail Feraru (undergraduates at Faculty of Mathematics and Computer Science), and Andrei Ciobanu (master student enrolled at our Security and Applied Logic master program) for finishing the team competition on the first place! More information available here.
The University of Bucharest is placed in the top for the best score at the Individual Competition Unbreakable Romania (season spring-summer 2021). Congratulations to Dragos Albastroiu, undergraduate at Faculty of Mathematics and Computer Science, for finishing the individual competition on the first place! More information available here.
Title: Active Defense in Cybersecurity
Speaker: Sergiu Bogdan Meseșan & Andreea Drugă, Cybersecurity Specialists at ENEA
- Active Defense Mechanisms – Notions, principles and Active Defense mechanisms (ca.1h)
- Practical Application for Honeypot Analytics and Attacks Data Collection – Presentation of a platform implemented by ENEA specially for this lecture, a practical demo of Active Defense (ca.1h)
- Active Defense DIY – Workshop installation, running, Internet access for a Honeypot type VM using an open source platform (Telekom Tpot CE) (ca.1h-1.5h)
For the students interested to attend the meeting: please contact Ruxandra Olimid (firstname.lastname@example.org)
Title: Kernelization, Proof Complexity and Social Choice
Speaker: Gabriel Istrate (West University of Timișoara)
We display an application of the notions of kernelization and data reduction from parameterized complexity to proof complexity: Specifically, we show that the existence of data reduction rules for a parameterized problem having (a) a small-length reduction chain, and (b) small-size (extended) Frege proofs certifying the soundness of reduction steps implies the existence of subexponential size (extended) Frege proofs for propositional formalizations of the given problem. We apply our result to infer the existence of subexponential Frege and extended Frege proofs for a variety of problems. Improving earlier results of Aisenberg et al. (ICALP 2015), we show that propositional formulas expressing (a stronger form of) the Kneser-Lovasz Theorem have polynomial size Frege proofs for each constant value of the parameter k. Previously only quasipolynomial bounds were known (and only for the ordinary Kneser-Lovasz Theorem). Another notable application of our framework is to impossibility results in computational social choice: we show that, for any fixed number of agents, propositional translations of the Arrow and Gibbard-Satterthwaite impossibility theorems have subexponential size Frege proofs.
This is joint work with Cosmin Bonchiș and Adrian Crăciun.
Title: An Introduction to Protocols in Dynamic Epistemic Logic
Speaker: Alexandru Dragomir (University of Bucharest)
Dynamic epistemic logics are useful in reasoning about knowledge and acts of learning, seen as epistemic actions. However, not all epistemic actions are allowed to be executed in an initial epistemic model, and this is where the concept of a protocol comes in: a protocol stipulates what epistemic actions are allowed to be performed in a model. The aim of my presentation is to introduce the audience to two accounts of protocols in DEL: Hoshi’s , and Wang’s .
Title: Regular matching problems for infinite trees
Speaker: Mircea Marin (West University of Timișoara)
We study the matching problem “∃σ:σ(L)⊆R?” where L and R are regular tree languages over finite ranked alphabets X and Σ respectively, and σ is a substitution such that σ(x) is a set of trees in T(Σ∪H)∖H for all x∈X. Here, H denotes a set of holes which are used to define a concatenation of trees. Conway studied this problem in the special case for languages of finite words in his classical textbook Regular algebra and finite machines
and showed that if L and R are regular, then the problem “∃σ:∀x∈X:σ(x)≠∅∧σ(L)⊆R?” is decidable. Moreover, there are only finitely many maximal solutions, which are regular and effectively computable. We extend Conway’s results when L and R are regular languages of finite and infinite trees, and language substitution is applied inside-out. We show that if L⊆T(X) and R⊆T(Σ) are regular tree languages then the problem “∃σ∀x∈X:σ(x)≠∅∧σio
(L)⊆R?” is decidable. Moreover, there are only finitely many maximal solutions, which are regular and effectively computable. The corresponding question for the outside-in extension σoi
remains open, even in the restricted setting of finite trees. Our main result is the decidability of “∃σ:σio
(L)⊆R?” if R is regular and L belongs to a class of tree languages closed under intersection with regular sets. Such a special case pops up if L is context-free.
This is joint work with Carlos Camino, Volker Diekert, Besik Dundua and Géraud Sénizergues.
 C. Camino, V. Diekert, B. Dundua, M. Marin, G. Sénizergues, Regular matching problems for infinite trees. arXiv:2004.09926 [cs.FL], 2021.