Serge Gaspers

Prof. Serge Gaspers

School of Computer Science and Engineering, UNSW Sydney, Sydney, NSW 2052, Australia
orcid

Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
16 May 2014 in Algorithmica
Verified
Journal Article
Closed access
PDF file
FFFabrizio Frati
Fabrizio Frati
SGSerge Gaspers
Serge Gaspers
JGJoachim Gudmundsson
Joachim Gudmundsson
LMLuke Mathieson
Luke Mathieson

14 November 2019 in Algorithmica
Verified
Journal Article
Open access
PDF file
HAHaris Aziz
Haris Aziz
PBPéter Biró
Péter Biró
SGSerge Gaspers
Serge Gaspers
RHRonald de Haan
Ronald de Haan
NMNicholas Mattei
Nicholas Mattei
BRBaharak Rastegari
Baharak Rastegari
We consider the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model—for each agent, there is a probability distribution over linear preferences, (2) compact indifference model—for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model—there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant.

26 February 2015 in Algorithmica
Verified
Journal Article
Closed access
PDF file
RBRené van Bevern
René van Bevern
RDRodney G. Downey
Rodney G. Downey
MFMichael R. Fellows
Michael R. Fellows
SGSerge Gaspers
Serge Gaspers
Frances  RosamondFrances Rosamond
Frances Rosamond

13 November 2020 in Theory of Computing Systems
Verified
Journal Article
Open access
PDF file
KCKatrin Casel
Katrin Casel
Henning FernauHenning Fernau
Henning Fernau
SGSerge Gaspers
Serge Gaspers
BGBenjamin Gras
Benjamin Gras
MSMarkus L. Schmid
Markus L. Schmid
In the smallest grammar problem, we are given a word w and we want to compute a preferably small context-free grammar G for the singleton language {w} (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is NP-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless P = NP. We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains NP-complete (and its optimisation version is APX-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i. e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields W[1]-hardness. Furthermore, we present an $\mathcal {O}(3^{\mid {w}\mid })$ O ( 3 ∣ w ∣ ) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i. e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the “hierarchical depth” of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.

28 December 2009 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
SGSerge Gaspers
Serge Gaspers
DKDieter Kratsch
Dieter Kratsch
MLMathieu Liedloff
Mathieu Liedloff
ITIoan Todinca
Ioan Todinca
The minimum dominating set problem remains NP-hard when restricted to any of the following graph classes: c -dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, and circle graphs. Developing and using a general approach, for each of these graph classes we present an exponential time algorithm solving the minimum dominating set problem faster than the best known algorithm for general graphs. Our algorithms have the following running time: O (1.4124 n ) for chordal graphs, O (1.4776 n ) for weakly chordal graphs, O (1.4845 n ) for 4-chordal graphs, O (1.4887 n ) for circle graphs, and O (1.2273 (1+√1−2 c ) n ) for c -dense graphs.

20 November 2021 in Proceedings on Privacy Enhancing Technologies
Verified
Journal Article
Open access
PDF file
JSJosh Smith
Josh Smith
HAHassan Jameel Asghar
Hassan Jameel Asghar
GGGianpaolo Gioiosa
Gianpaolo Gioiosa
SMSirine Mrabet
Sirine Mrabet
SGSerge Gaspers
Serge Gaspers
PTPaul Tyler
Paul Tyler
We show that the ‘optimal’ use of the parallel composition theorem corresponds to finding the size of the largest subset of queries that ‘overlap’ on the data domain, a quantity we call themaximum overlapof the queries. It has previously been shown that a certain instance of this problem, formulated in terms of determining the sensitivity of the queries, is NP-hard, but also that it is possible to use graph-theoretic algorithms, such as finding the maximum clique, to approximate query sensitivity. In this paper, we consider a significant generalization of the aforementioned instance which encompasses both a wider range of differentially private mechanisms and a broader class of queries. We show that for a particular class of predicate queries, determining if they are disjoint can be done in time polynomial in the number of attributes. For this class, we show that the maximum overlap problem remains NP-hard as a function of the number of queries. However, we show that efficient approximate solutions exist by relating maximum overlap to the clique and chromatic numbers of a certain graph determined by the queries. The link to chromatic number allows us to use more efficient approximate algorithms, which cannot be done for the clique number as it may underestimate the privacy budget. Our approach is defined in the general setting off-differential privacy, which subsumes standard pure differential privacy and Gaussian differential privacy. We prove the parallel composition theorem forf-differential privacy. We evaluate our approach on synthetic and real-world data sets of queries. We show that the approach can scale to large domain sizes (up to 1020000), and that its application can reduce the noise added to query answers by up to 60%.