Professor Serge Gaspers | UNSW Research

My Expertise

My expertise is in algorithms for computationally “intractable” problems from a large number of domains. While intractable in classical complexity theory, domain-specific features and structure often make these problems easier to solve in the real world. Modern approaches, like parameterized algorithms and complexity, identify and exploit the domain-specific structure. Quantum algorithms have the potential to further speed up these computations.

Please get in touch to talk about projects that appeal to both industry and academia.

Domains and Keywords
Boolean satisfiability, computational chemistry, constraint satisfaction, fair resource allocation, graph and network algorithms, preference aggregation, preprocessing, quantum algorithms, scheduling, self-interested agents, turbocharging heuristics, worst-case running time guarantees.

Fields of Research (FoR)

Data structures and algorithms, Theory of computation, Autonomous agents and multiagent systems, Quantum computation

SEO tags

Expanding Knowledge in the Information and Computing Sciences

Biography

I am a Professor in the School of Computer Science and Engineering at UNSW.

I joined UNSW in 2012, first as an ARC DECRA Fellow and then as a Future Fellow. I obtained a PhD in Computer Science from the University of Bergen (Norway) under the supervision of Fedor V. Fomin in 2008. From 2009-2012, I held postdoctoral positions in Montpellier (France), Santiago (Chile), and Vienna (Austria).

My Grants

ARC Discovery Project...view more

I am a Professor in the School of Computer Science and Engineering at UNSW.

My Grants

ARC Discovery Project for the project DP210103849 "Improved algorithms via random sampling" (with Fedor Fomin and Daniel Lokshtanov), A$ 435,346 (2021–2023)
Data61, CSIRO / UNSW Collaborative Research Project on the Computational Complexity of Resource Allocation Problems (with Toby Walsh and Haris Aziz), A$ 198,847 (2016–2018)
ARC Discovery Project for the project DP150101134 "Local reoptimization for turbocharging heuristics" (with Joachim Gudmundsson, Michael R Fellows, Julian Mestre, and Fedor Fomin), A$ 355,100 (2015–2017)
ARC Future Fellowship for the project FT140100048 “Algorithms for hard graph problems based on auxiliary data”, A$ 711,489 (2014–2018)
NICTA / UNSW Collaborative Research Project on the Computational Complexity of Resource Allocation Problems (with Toby Walsh), A$ 379,038 (2012–2016)
ARC Discovery Early Career Researcher Award (DECRA) for the project DE120101761 “Solving intractable problems: from practice to theory and back”, A$ 375,000 (2012–2014)

My Awards

ARC Future Fellowship 2014
IJCAI 2013 Most Educational Video Award
ARC Discovery Early Career Researcher Award (DECRA) 2012
UNSW Vice-Chancellor’s Postdoctoral Research Fellowship 2012 (declined to take up the DECRA instead)

My Research Activities

My research focuses on algorithms for solving NP-hard problems, especially graph and reasoning problems, with applications in Boolean satisfiability, computational social choice, constraint satisfaction, and resource allocation.

Keywords: exponential time algorithms; parameterized complexity; quantum algorithms, kernelization; extremal combinatorics; graph algorithms; computational social choice; resource allocation; satisfiability; constraint satisfaction