Professor Serge Gaspers
Professor

Professor Serge Gaspers

Engineering
Computer Science and Engineering

I am a Professor and the Associate Head of School (Research) 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).

Location
K17 506
  • Journal articles | 2021
    Casel K; Fernau H; Gaspers S; Gras B; Schmid ML, 2021, 'On the Complexity of the Smallest Grammar Problem over Fixed Alphabets', Theory of Computing Systems, vol. 65, pp. 344 - 409, http://dx.doi.org/10.1007/s00224-020-10013-w
    Journal articles | 2020
    Aziz H; Biró P; Gaspers S; de Haan R; Mattei N; Rastegari B, 2020, 'Stable Matching with Uncertain Linear Preferences', Algorithmica, vol. 82, pp. 1410 - 1433, http://dx.doi.org/10.1007/s00453-019-00650-0
    Journal articles | 2019
    Gaspers S; Gudmundsson J; Jones M; Mestre J; Rümmele S, 2019, 'Turbocharging Treewidth Heuristics', Algorithmica, vol. 81, pp. 439 - 475, http://dx.doi.org/10.1007/s00453-018-0499-1
    Journal articles | 2019
    Gaspers S; Huang S, 2019, '(2P2,K4)-Free graphs are 4-Colorable', SIAM Journal on Discrete Mathematics, vol. 33, pp. 1095 - 1120, http://dx.doi.org/10.1137/18M1205832
    Journal articles | 2018
    Aziz H; Gaspers S; Mackenzie S; Mattei N; Stursberg P; Walsh T, 2018, 'Fixing balanced knockout and double elimination tournaments', Artificial Intelligence, vol. 262, pp. 1 - 14, http://dx.doi.org/10.1016/j.artint.2018.05.002
    Journal articles | 2018
    Finbow S; Gaspers S; Messinger ME; Ottaway P, 2018, 'A note on the eternal dominating set problem', International Journal of Game Theory, vol. 47, pp. 543 - 555, http://dx.doi.org/10.1007/s00182-018-0623-0
    Journal articles | 2018
    Gaspers S; Mackenzie S, 2018, 'On the number of minimal separators in graphs', Journal of Graph Theory, vol. 87, pp. 653 - 659, http://dx.doi.org/10.1002/jgt.22179
    Journal articles | 2017
    Gaspers S; Misra N; Ordyniak S; Szeider S; Živný S, 2017, 'Backdoors into heterogeneous classes of SAT and CSP', Journal of Computer and System Sciences, vol. 85, pp. 38 - 56, http://dx.doi.org/10.1016/j.jcss.2016.10.007
    Journal articles | 2017
    Gaspers S; Sorkin GB, 2017, 'Separate, measure and conquer: Faster polynomial-space algorithms for Max 2-CSP and counting dominating sets', ACM Transactions on Algorithms, vol. 13, http://dx.doi.org/10.1145/3111499
    Journal articles | 2013
    Binkele-Raible D; Fernau H; Gaspers S; Liedloff M, 2013, 'Exact and parameterized algorithms for max internal spanning tree', Algorithmica, vol. 65, pp. 95 - 128, http://dx.doi.org/10.1007/s00453-011-9575-5
    Journal articles | 2013
    Fomin FV; Gaspers S; Saurabh S; Thomassé S, 2013, 'A linear vertex kernel for maximum internal spanning tree', Journal of Computer and System Sciences, vol. 79, pp. 1 - 6, http://dx.doi.org/10.1016/j.jcss.2012.03.004
    Journal articles | 2013
    Gaspers S; Mnich M, 2013, 'Feedback vertex sets in tournaments', Journal of Graph Theory, vol. 72, pp. 72 - 89, http://dx.doi.org/10.1002/jgt.21631
    Journal articles | 2012
    Fellows MR; Gaspers S; Rosamond FA, 2012, 'Parameterizing by the Number of Numbers', Theory of Computing Systems, vol. 50, pp. 675 - 693, http://dx.doi.org/10.1007/s00224-011-9367-y
    Journal articles | 2012
    Gaspers S; Sorkin GB, 2012, 'A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between', Journal of Computer and System Sciences, vol. 78, pp. 305 - 335, http://dx.doi.org/10.1016/j.jcss.2011.05.010
    Journal articles | 2011
    Bessy S; Fomin FV; Gaspers S; Paul C; Perez A; Saurabh S; Thomassé S, 2011, 'Kernels for feedback arc set in tournaments', Journal of Computer and System Sciences, vol. 77, pp. 1071 - 1078, http://dx.doi.org/10.1016/j.jcss.2010.10.001
    Journal articles | 2010
    Fomin FV; Gaspers S; Kratsch D; Liedloff M; Saurabh S, 2010, 'Iterative compression and exact algorithms', Theoretical Computer Science, vol. 411, pp. 1045 - 1053, http://dx.doi.org/10.1016/j.tcs.2009.11.012
    Journal articles | 2009
    Fomin FV; Gaspers S; Saurabh S; Stepanov AA, 2009, 'On two techniques of combining branching and treewidth', Algorithmica (New York), vol. 54, pp. 181 - 207, http://dx.doi.org/10.1007/s00453-007-9133-3
    Journal articles | 2008
    Fomin FV; Gaspers S; Pyatkin AV; Razgon I, 2008, 'On the minimum feedback vertex set problem: Exact and enumeration algorithms', Algorithmica (New York), vol. 52, pp. 293 - 307, http://dx.doi.org/10.1007/s00453-007-9152-0
  • Conference Papers | 2019
    Fomin FV; Gaspers S; Lokshtanov D; Saurabh S, 2019, 'Exact algorithms via monotone local search', in Wichs D; Mansour Y (ed.), Journal of the ACM, ACM, pp. 764 - 775, presented at Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, http://dx.doi.org/10.1145/3284176
    Conference Papers | 2019
    Gaspers S; Najeebullah K, 2019, 'Optimal Surveillance of Covert Networks by Minimizing Inverse Geodesic Length', in THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE, Honolulu, HI, pp. 533 - 540, presented at 33rd AAAI Conference on Artificial Intelligence / 31st Innovative Applications of Artificial Intelligence Conference / 9th AAAI Symposium on Educational Advances in Artificial Intelligence, Honolulu, HI, 27 January 2019 - 01 February 2019, http://dx.doi.org/10.1609/aaai.v33i01.3301533
    Conference Papers | 2019
    Gerding EH; Perez-Diaz A; Aziz H; Gaspers S; Marcu A; Mattei N; Walsh T, 2019, 'Fair online allocation of perishable goods and its application to electric vehicle charging', in IJCAI International Joint Conference on Artificial Intelligence, Macao, China, pp. 5569 - 5575, presented at Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-, Macao, China, 10 August 2019, http://dx.doi.org/10.24963/ijcai.2019/773
    Conference Papers | 2018
    Abu-Khzam FN; Egan J; Gaspers S; Shaw A; Shaw P, 2018, 'Cluster editing with vertex splitting', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 1 - 13, http://dx.doi.org/10.1007/978-3-319-96151-4_1
    Conference Papers | 2014
    Aziz H; Gaspers S; Mackenzie S; Walsh T, 2014, 'Fair assignment of indivisible objects under ordinal preferences', in 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, pp. 1305 - 1312
    Conference Papers | 2014
    Gaspers S; Misra N; Ordyniak S; Szeider S; Živný S, 2014, 'Backdoors into heterogeneous classes of SAT and CSP', in Proceedings of the National Conference on Artificial Intelligence, pp. 2652 - 2658
    Conference Papers | 2012
    Gaspers S; Szeider S, 2012, 'Strong backdoors to nested satisfiability', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7317 LNCS, Springer Verlag, Trento, Italy, pp. 72 - 85, presented at 15th International Conference on Theory and Applications of Satisfiability Testing, SAT 2012, Trento, Italy, 17 June 2012 - 20 June 2012, http://dx.doi.org/10.1007/978-3-642-31612-8_7
    Conference Papers | 2010
    Fellows MR; Gaspers S; Rosamond FA, 2010, 'Parameterizing by the number of numbers', in Raman V; Saurabh S (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 123 - 134, presented at Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, http://dx.doi.org/10.1007/978-3-642-17493-3_13

  • 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)

  • 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 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; kernelization; extremal combinatorics; graph algorithms; computational social choice; resource allocation; satisfiability; constraint satisfaction

My Teaching

I designed and teach COMP6741 - Algorithms for intractable problems.