Logic and Computation Seminar   RSS

Planned sessions

28/06/2022, 14:00 — 15:00 — Instituto Superior Técnico
Diogo Poças, Faculdade de Ciências de Universidade Lisboa

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

We study the existence of approximate pure Nash equilibria (PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d. Previously it was known that d-approximate equilibria always exist, while nonexistence was established only for small constants, namely for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have √d-approximate PNE, which provides the first super-constant lower bound.

Furthermore, we provide a black-box gap-introducing method of combining such nonexistence results with a specific circuit gadget, in order to derive NP-completeness of the decision version of the problem. In particular, deploying this technique we are able to show that deciding whether a weighted congestion game has an √d-PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions. The circuit gadget is of independent interest and it allows us to also prove hardness for a variety of problems related to the complexity of PNE in congestion games.

14/07/2022, 14:00 — 15:00 — Room P3.10, Mathematics Building Instituto Superior Técnico
, King's College, UK

Formal Methods for Socio-Technical Security (Formal and Automated Analysis of Security Ceremonies)

Software engineers and analysts traditionally focus on cyber systems as technical systems, which are built only from software processes, communication protocols, crypto algorithms, etc. They often neglect, or choose not, to consider the human user as a component of the system’s security as they lack the expertise to fully understand human factors and how they affect security. However, humans should not be designed out of the security loop. Instead, we must deal with security assurance as a true socio-technical problem rather than a mere technical one, and consider cyber systems as socio-technical systems with people at their hearts. The main goal of this talk is to advocate the use of formal methods to establish the security of socio-technical systems, and to discuss some of the most promising approaches, including those that I have helped develop. I will also discuss my recent work on “Cybersecurity Show and Tell”, namely how different kinds of artworks can be used to explain cybersecurity and how telling (i.e., explaining notions in a formal, technical way) can be paired with showing through visual storytelling or other forms of storytelling.

Funded under the scope of UID/EEA/50008/2013.

Instituto de TelecomunicaçõesFCT