Loading Events

« All Events

  • This event has passed.

Colloquium – Gregory Gutin

September 14, 2022 @ 1:30 pm - 2:30 pm

Gregory Gutin
Royal Holloway, University of London

Wednesday, Sept 14
1:30 – 2:30 pm
3780 WEB

Parameterized algorithmics in access control: linking theory and practice

Abstract: Access control is an important area of information security. The first paper in application of parameterized algorithmics in access control was published in 2010 by Qihua Wang and Ninghui Li. In the paper, the authors suggested a parameterization of the Workflow Satisfiability Problem (WSP). In its basic form, WSP is simply the Constraint Satisfaction Problem, which Wang and Li parameterized by the number of steps (= variables in CSP terms). Wang and Li proved that WSP is W[1]-hard and identified a practically important class of constraints for which WSP is FPT. They also conducted computational experiments using an off-the-shelf solver. Unfortunately, in their paper, the theoretical results and practical computation were not linked.
In the last decade, Jason Crampton (Information Security Group, RHUL), the speaker and their co-authors studied theoretical and practical computing aspects initially for WSP with user-independent (UI) non-unary constraints and its variations and then for other access control problems. Several FPT algorithms and lower bounds were obtained, FPT algorithms were implemented and off-the-shelf solvers were used in computational experiments. Among practical computing highlights are FPT algorithms for WSP with UI non-unary constraints performing in practice much better than off-the-shelf solvers, and the possibility for off-the-shelf solvers to emulate FPT algorithms for WSP and other access control problems (approximately, the runtime exponential growth is wrt the parameter only).This theoretical and practical computing research was highly acknowledged by the access control community: most of the papers were published in top information security journals and some papers received the best paper awards in the annual symposium on access control (SACMAT).

Bio: Gregory Gutin is a Professor of Computer Science, Department of Computer Science, Royal Holloway, University of London. He held the Royal Society Wolfson Research Merit award in 2014-2018 and was elected to Academia Europaea in 2017 and to AAIA (Asia-Pacific Artificial Intelligence Association) in 2021. He received best paper awards at ACM SACMAT in 2015, 2016 and 2021. Gutin’s main research interests include graphs and combinatorics, parameterized, polynomial, exact and approximation algorithms, access control in information security, combinatorial optimization and theoretical economics.


September 14, 2022
1:30 pm - 2:30 pm
Event Category:


3780 WEB