Ƶ
Back to
Professor Serge Gaspers

Professor Serge Gaspers

Professor
Engineering
Computer Science and Engineering

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).
E-mail
serge.gaspers@unsw.edu.au
Location
K17 506
  • Books | 2024
    Fernau H; Gaspers S; Klasing R, 2024, Preface
    Books | 2010
    Gaspers S, 2010, Exponential Time Algorithms - Structures, Measures, and Bounds., VDM
  • Book Chapters | 2024
    Fernau H; Gaspers S; Klasing R, 2024, 'Preface', in SOFSEM 2024: Theory and Practice of Computer Science, pp. v - vii,
    Book Chapters | 2017
    Gaspers S; Ordyniak S; Szeider S, 2017, 'Backdoor Sets for CSP', in Krokhin AA; Zivný S (ed.), The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 137 - 157,
    Book Chapters | 2017
    Gaspers S; Walsh T, 2017, 'Preface', in Theory and Applications of Satisfiability Testing – SAT 2017, Springer International Publishing, pp. V - VIII
    Book Chapters | 2016
    Gaspers S, 2016, 'Backdoors to SAT.', in Encyclopedia of Algorithms, Springer Science & Business Media, pp. 167 - 170,
    Book Chapters | 2015
    Gaspers S, 2015, 'Backdoors to SAT', in Encyclopedia of Algorithms, Springer Berlin Heidelberg, pp. 1 - 5,
    Book Chapters | 2012
    Gaspers S; Szeider S, 2012, 'Backdoors to Satisfaction', in Bodlaender HL; Downey R; Fomin FV; Marx D (ed.), The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, Springer, Berlin, pp. 287 - 317,
    Book Chapters | 2011
    Fellows MR; Gaspers S; Rosamond FA, 2011, 'Multivariate Complexity Theory', in Blum EK; Aho AV (ed.), Computer Science: The Hardware, Software and Heart of It, Springer, New York, pp. 269 - 293,
  • Journal articles | 2023
    Gaspers S; Lee EJ, 2023, 'Faster Graph Coloring in Polynomial Space', Algorithmica, 85, pp. 584 - 609,
    Journal articles | 2022
    Aziz H; Biró P; Fleiner T; Gaspers S; de Haan R; Mattei N; Rastegari B, 2022, 'Stable matching with uncertain pairwise preferences', Theoretical Computer Science, 909, pp. 1 - 11,
    Journal articles | 2022
    Smith J; Asghar HJ; Gioiosa G; Mrabet S; Gaspers S; Tyler P, 2022, 'Making the Most of Parallel Composition in Differential Privacy', Proceedings on Privacy Enhancing Technologies, 2022, pp. 253 - 273,
    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, 65, pp. 344 - 409,
    Journal articles | 2021
    Smith J; Asghar HJ; Gioiosa G; Mrabet S; Gaspers S; Tyler P, 2021, 'Making the Most of Parallel Composition in Differential Privacy.', CoRR, abs/2109.09078
    Journal articles | 2020
    Aziz H; Biró P; Gaspers S; Haan RD; Mattei N; Rastegari B, 2020, 'Stable Matching with Uncertain Linear Preferences.', Algorithmica, 82, pp. 1410 - 1433
    Journal articles | 2020
    Aziz H; Biró P; Gaspers S; de Haan R; Mattei N; Rastegari B, 2020, 'Stable Matching with Uncertain Linear Preferences', Algorithmica, 82, pp. 1410 - 1433,
    Journal articles | 2019
    Fomin FV; Gaspers S; Lokshtanov D; Saurabh S, 2019, 'Exact Algorithms via Monotone Local Search.', J. ACM, 66, pp. 8:1 - 8:23,
    Journal articles | 2019
    Gaspers S; Gudmundsson J; Jones M; Mestre J; Rümmele S, 2019, 'Turbocharging Treewidth Heuristics', Algorithmica, 81, pp. 439 - 475,
    Journal articles | 2019
    Gaspers S; Huang S; Paulusma D, 2019, 'Colouring square-free graphs without long induced paths.', J. Comput. Syst. Sci., 106, pp. 60 - 79,
    Journal articles | 2019
    Gaspers S; Huang S, 2019, '(2P2,K4)-Free graphs are 4-Colorable', SIAM Journal on Discrete Mathematics, 33, pp. 1095 - 1120,
    Journal articles | 2019
    Gaspers S; Huang S, 2019, 'Linearly χ-bounding (P6, C4)-free graphs*', Journal of Graph Theory, 92, pp. 322 - 342,
    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, 262, pp. 1 - 14,
    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, 47, pp. 543 - 555,
    Journal articles | 2018
    Gaspers S; Mackenzie S, 2018, 'On the number of minimal separators in graphs', Journal of Graph Theory, 87, pp. 653 - 659,
    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, 85, pp. 38 - 56,
    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, 13,
    Journal articles | 2016
    Gaspers S; Ordyniak S; Ramanujan MS; Saurabh S; Szeider S, 2016, 'Backdoors to q-Horn', Algorithmica, 74, pp. 540 - 557,
    Journal articles | 2015
    Aziz H; Gaspers S; Mackenzie S; Walsh T, 2015, 'Fair assignment of indivisible objects under ordinal preferences', Artificial Intelligence, 227, pp. 71 - 92,
    Journal articles | 2015
    Aziz H; Gaspers S; Mackenzie S; Walsh T, 2015, 'Fair assignment of indivisible objects under ordinal preferences.', Artif. Intell., 227, pp. 71 - 92,
    Journal articles | 2015
    Aziz H; Gaspers S; Mackenzie S; Walsh T, 2015, 'Two Desirable Fairness Concepts for Allocation of Indivisible Objects under Ordinal Preferences', ACM SIGECOM EXCHANGES, 14, pp. 16 - 21,
    Journal articles | 2015
    Frati F; Gaspers S; Gudmundsson J; Mathieson L, 2015, 'Augmenting Graphs to Minimize the Diameter.', Algorithmica, 72, pp. 995 - 1010,
    Journal articles | 2015
    Gaspers S; Koivisto M; Liedloff M; Ordyniak S; Szeider S, 2015, 'On finding optimal polytrees.', Theor. Comput. Sci., 592, pp. 49 - 58
    Journal articles | 2015
    Gaspers S; Liedloff M; Stein M; Suchan K, 2015, 'Complexity of splits reconstruction for low-degree trees', Discrete Applied Mathematics, 180, pp. 89 - 100,
    Journal articles | 2015
    van Bevern R; Downey RG; Fellows MR; Gaspers S; Rosamond FA, 2015, 'Myhill–Nerode Methods for Hypergraphs', Algorithmica, 73, pp. 696 - 729,
    Journal articles | 2014
    Gaspers S; Ordyniak S; Ramanujan MS; Saurabh S; Szeider S, 2014, 'Backdoors to q-Horn', Algorithmica,
    Journal articles | 2014
    Gaspers S; Szeider S, 2014, 'Guarantees and limits of preprocessing in constraint satisfaction and reasoning', Artificial Intelligence, 216, pp. 1 - 19,
    Journal articles | 2013
    Binkele-Raible D; Fernau H; Gaspers S; Liedloff M, 2013, 'Exact and parameterized algorithms for max internal spanning tree', Algorithmica, 65, pp. 95 - 128,
    Journal articles | 2013
    Fomin FV; Gaspers S; Saurabh S; Thomasse S, 2013, 'A linear vertex kernel for maximum internal spanning tree', JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 79, pp. 1 - 6,
    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, 79, pp. 1 - 6,
    Journal articles | 2013
    Fürer M; Gaspers S; Kasiviswanathan SP, 2013, 'An exponential time 2-approximation algorithm for bandwidth', Theoretical Computer Science, 511, pp. 23 - 31,
    Journal articles | 2013
    Gaspers S; Mnich M, 2013, 'Feedback vertex sets in tournaments', Journal of Graph Theory, 72, pp. 72 - 89,
    Journal articles | 2012
    Bevern RV; Fellows MR; Gaspers S; Rosamond FA, 2012, 'How applying Myhill-Nerode methods to hypergraphs helps mastering the Art of Trellis Decoding', CoRR, abs/1211.1299
    Journal articles | 2012
    Fellows MR; Gaspers S; Rosamond FA, 2012, 'Parameterizing by the Number of Numbers', Theory of Computing Systems, 50, pp. 675 - 693,
    Journal articles | 2012
    Fellows MR; Gaspers S; Rosamond FA, 2012, 'Parameterizing by the Number of Numbers.', Theory Comput. Syst., 50, pp. 675 - 693,
    Journal articles | 2012
    Gaspers S; Koivisto M; Liedloff M; Ordyniak S; Szeider S, 2012, 'On Finding Optimal Polytrees', Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI 2012, pp. 750 - 756
    Journal articles | 2012
    Gaspers S; Kratsch D; Liedloff M, 2012, 'On Independent Sets and Bicliques in Graphs', Algorithmica, 62, pp. 637 - 658,
    Journal articles | 2012
    Gaspers S; Liedloff M, 2012, 'A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set', Discrete Mathematics & Theoretical Computer Science, 14, pp. 29 - 42,
    Journal articles | 2012
    Gaspers S; Liedloff M, 2012, 'A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set', Discrete Mathematics & Theoretical Computer Science, Vol. 14 no. 1,
    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, 78, pp. 305 - 335,
    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, 77, pp. 1071 - 1078,
    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.', J. Comput. Syst. Sci., 77, pp. 1071 - 1078
    Journal articles | 2010
    Binkele-Raible D; Fernau H; Gaspers S; Liedloff M, 2010, 'Exact exponential-time algorithms for finding bicliques', Information Processing Letters, 111, pp. 64 - 67,
    Journal articles | 2010
    Fomin FV; Gaspers S; Golovach PA; Kratsch D; Saurabh S, 2010, 'Parameterized algorithm for eternal vertex cover', Information Processing Letters, 110, pp. 702 - 706,
    Journal articles | 2010
    Fomin FV; Gaspers S; Kratsch D; Liedloff M; Saurabh S, 2010, 'Iterative compression and exact algorithms', Theoretical Computer Science, 411, pp. 1045 - 1053,
    Journal articles | 2010
    Gaspers S; Messinger ME; Nowakowski RJ; Prałat P, 2010, 'Parallel cleaning of a network with brushes', Discrete Applied Mathematics, 158, pp. 467 - 478,
    Journal articles | 2009
    Fomin FV; Gaspers S; Saurabh S; Stepanov AA, 2009, 'On two techniques of combining branching and treewidth', Algorithmica (New York), 54, pp. 181 - 207,
    Journal articles | 2009
    Gaspers S; Kratsch D; Liedloff M; Todinca I, 2009, 'Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes', ACM TRANSACTIONS ON ALGORITHMS, 6,
    Journal articles | 2009
    Gaspers S; Messinger ME; Nowakowski RJ; Prałat P, 2009, 'Clean the graph before you draw it!', Information Processing Letters, 109, pp. 463 - 467,
    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), 52, pp. 293 - 307,
  • Preprints | 2024
    Clinch K; Gaspers S; Saffidine A; Zhang T, 2024, A Piecewise Approach for the Analysis of Exact Algorithms, ,
    Conference Papers | 2024
    Gaspers S; Li JZ, 2024, 'Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems', in Leibniz International Proceedings in Informatics, LIPIcs,
    Conference Papers | 2024
    Orang AV; Dorri A; Gaspers S; Ruj S, 2024, 'Blockchain-Enabled Private and Secure Task Allocation Framework', in 2024 16th International Conference on COMmunication Systems and NETworkS, COMSNETS 2024, pp. 666 - 670,
    Preprints | 2023
    Gaspers S; Li JZ, 2023, Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and Packing Problems, ,
    Conference Papers | 2022
    Gaspers S; Kaploun A, 2022, 'Faster Algorithms for Weak Backdoors', in Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022, pp. 3741 - 3748
    Conference Papers | 2020
    Aziz H; Gaspers S; Sun Z; Yokoo M, 2020, 'Multiple Levels of Importance in Matching with Distributional Constraints: Extended Abstract.', in Seghrouchni AEF; Sukthankar G; An B; Yorke-Smith N (eds.), AAMAS, International Foundation for Autonomous Agents and Multiagent Systems, pp. 1759 - 1761,
    Conference Papers | 2020
    Aziz H; Gaspers S; Sun Z; Yokoo M, 2020, 'Multiple levels of importance in matching with distributional constraints', in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, pp. 1759 - 1761
    Conference Papers | 2020
    Aziz H; Gaspers S; Sun Z, 2020, 'Mechanism design for school choice with soft diversity constraints', in IJCAI International Joint Conference on Artificial Intelligence, pp. 153 - 159
    Conference Papers | 2020
    Aziz H; Gaspers S; Sun Z, 2020, 'Mechanism design for school choice with soft diversity constraints', in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, pp. 1756 - 1758
    Conference Papers | 2019
    Aziz H; Sun Z; Gaspers S; Walsh T, 2019, 'From matching with diversity constraints to matching with regional quotas', in Elkind E; Veloso M; Agmon N; Taylor ME (eds.), Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, ASSOC COMPUTING MACHINERY, CANADA, Montreal, pp. 377 - 385, presented at 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), CANADA, Montreal, 13 May 2019 - 17 May 2019,
    Conference Papers | 2019
    Fomin FV; Gaspers S; Lokshtanov D; Saurabh S, 2019, 'Exact algorithms via monotone local search', in Journal of the ACM,
    Conference Papers | 2019
    Gaspers S; Lau J, 2019, 'Minimizing and computing the inverse geodesic length on trees', in Leibniz International Proceedings in Informatics, LIPIcs, Shanghai, China, presented at 30th International Symposium on Algorithms and Computation (ISAAC 2019) held in Shanghai, China on December 8-11, 2019, Shanghai, China, 08 December 2019 - 11 December 2019,
    Conference Papers | 2019
    Gaspers S; Li R, 2019, 'Enumeration of Preferred Extensions in Almost Oriented Digraphs.', in Rossmanith P; Heggernes P; Katoen J-P (eds.), MFCS, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 74:1 - 74:1,
    Conference Papers | 2019
    Gaspers S; Li R, 2019, 'Enumeration of preferred extensions in almost oriented digraphs', in Leibniz International Proceedings in Informatics, LIPIcs, Aachen, Germany, presented at 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Aachen, Germany, 26 August 2019,
    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,
    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,
    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,
    Conference Papers | 2018
    Aziz H; Gaspers S; Lee EJ; Najeebullah K, 2018, 'Defender stackelberg game with inverse geodesic length as utility metric', in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, International Foundation for Autonomous Agents and Multiagent Systems, Stockholm, Sweden, pp. 694 - 702, presented at AAMAS (International Conference on Autonomous Agents and Multiagent Systems) 2018, Stockholm, Sweden, 10 July 2018 - 15 July 2018,
    Conference Papers | 2018
    Chen J; Sun Z; Aziz H; Gaspers S, 2018, 'Stability and pareto optimality in refugee allocation matchings', in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, ACM, Stockholm, Sweden, pp. 964 - 972, presented at 17th International Conference on Autonomous Agents and MultiAgent Systems, Stockholm, Sweden, 10 July 2018 - 15 July 2018,
    Conference Papers | 2018
    Gaspers S; Gudmundsson J; Horton M; Rümmele S, 2018, 'When is red-blue nonblocker fixed-parameter tractable?', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 515 - 528,
    Conference Papers | 2018
    Gaspers S; Huang S; Paulusma D, 2018, 'Colouring square-free graphs without long induced paths', in Niedermeier R; Vallée B (ed.), Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Caen, France, pp. 35:1 - 35:15, presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France, 28 February 2018 - 03 March 2018,
    Conference Papers | 2017
    Aziz H; Biro P; Fleiner T; Gaspers S; de Haan R; Mattei N; Rastegari B, 2017, 'Stable Matching with Uncertain Pairwise Preferences', in Larson K; Winikoff M; Das S; Durfee EH (eds.), Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, ACM, Sao Paulo, Brazil, pp. 344 - 352, presented at AAMAS 2017 - 16th Conference on Autonomous Agents and MultiAgent Systems, Sao Paulo, Brazil, 08 May 2017 - 12 May 2017,
    Conference Papers | 2017
    Aziz H; Gaspers S; Najeebullah K, 2017, 'Weakening covert networks by minimizing inverse geodesic length', in IJCAI International Joint Conference on Artificial Intelligence, pp. 779 - 785,
    Conference Papers | 2017
    Bonnet E; Gaspers S; Lambilliotte A; Rümmele S; Saffidine A; Ruemmele S, 2017, 'The Parameterized Complexity of Positional Games', in Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Warsaw, Poland, pp. 90:1 - 90:14, presented at ICALP 2017 - 44th International Colloquium on Automata, Languages, and Programming, Warsaw, Poland, 10 July 2017 - 14 July 2017,
    Conference Papers | 2017
    Gaspers S; Huang S, 2017, 'Linearly χ -Bounding (P6, C4) -Free Graphs', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Eindhoven, The Netherlands, pp. 263 - 274, presented at 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, 21 June 2017 - 23 June 2017,
    Conference Papers | 2017
    Gaspers S; Lee EJ, 2017, 'Exact Algorithms via Multivariate Subroutines', in Chatzigiannakis I; Indyk P; Kuhn F; Muscholl A (eds.), Proceedings of ICALP 2017, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Warsaw, Poland, pp. 69:1 - 69:13, presented at ICALP 2017 - 44th International Colloquium on Automata, Languages, and Programming, Warsaw, Poland, 10 July 2017 - 14 July 2017,
    Conference Papers | 2017
    Gaspers S; Lee EJ, 2017, 'Faster Graph Coloring in Polynomial Space', in Cao Y; Chen J (ed.), COCOON, Springer, Hong Kong, China, pp. 371 - 383, presented at COCOON 2017 - 23rd International Conference on Computing and Combinatorics, Hong Kong, China, 03 August 2017 - 05 August 2017,
    Conference Papers | 2017
    Gaspers S; Rümmele S; Saffidine A; Tran K, 2017, 'Minesweeper with limited moves', in 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, Association for the Advancement of Artificial Intelligence, New Orleans, Louisiana, USA, pp. 860 - 867, presented at Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, USA, 02 February 2017 - 07 February 2017,
    Conference Proceedings (Editor of) | 2017
    Gaspers S; Walsh T, (ed.), 2017, 'Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings', Springer, Vol. 10491
    Conference Papers | 2016
    Abeliuk A; Aziz H; Berbeglia G; Gaspers S; Kalina P; Mattei N; Peters D; Stursberg P; Hentenryck PV; Walsh T, 2016, 'Interdependent Scheduling Games.', in Kambhampati S (ed.), IJCAI, IJCAI/AAAI Press, pp. 2 - 9,
    Conference Papers | 2016
    Abeliuk A; Aziz H; Berbeglia G; Gaspers S; Kalina P; Mattei N; Peters D; Stursberg P; Van Hentenryck P; Walsh T, 2016, 'Interdependent scheduling games', in IJCAI International Joint Conference on Artificial Intelligence, pp. 2 - 9,
    Conference Papers | 2016
    Aziz H; Biró P; Gaspers S; de Haan R; Mattei N; Rastegari B, 2016, 'Stable matching with uncertain linear preferences', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), SPRINGER INT PUBLISHING AG, Liverpool, UK, pp. 195 - 206, presented at Algorithmic Game Theory - 9th International Symposium (SAGT 2016), Liverpool, UK, 19 September 2016 - 21 September 2016,
    Conference Papers | 2016
    Casel K; Fernau H; Gaspers S; Gras B; Schmid ML, 2016, 'On the complexity of grammar-based compression over fixed alphabets', in Chatzigiannakis I; Mitzenmacher M; Rabani Y; Sangiorgi D (eds.), Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Rome, Italy, pp. 122:1 - 122:1, presented at 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 11 July 2016 - 15 July 2016,
    Conference Papers | 2016
    Cochefert M; Couturier J-F; Gaspers S; Kratsch D, 2016, 'Faster Algorithms to Enumerate Hypergraph Transversals.', in Kranakis E; Navarro G; Chávez E (eds.), LATIN, Springer, pp. 306 - 318,
    Conference Papers | 2016
    Gaspers S; Gudmundsson J; Jones M; Mestre J; Ruemmele S, 2016, 'Turbocharging Treewidth Heuristics', in Guo J; Hermelin D (ed.), Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Aarhus, Denmark, pp. 13:1 - 13:1, presented at 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, Aarhus, Denmark, 24 August 2016 - 26 August 2016,
    Conference Papers | 2016
    Gaspers S; Papadimitriou C; Saether SH; Telle JA, 2016, 'On Satisfiability Problems with a Linear Structure', in Leibniz International Proceedings in Informatics, LIPIcs, Aarhus, Denmark, presented at 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Aarhus, Denmark, 24 August 2016 - 26 August 2016
    Conference Papers | 2016
    Gaspers S; Papadimitriou CH; Sæther SH; Telle JA, 2016, 'On Satisfiability Problems with a Linear Structure.', in Guo J; Hermelin D (ed.), IPEC, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 14:1 - 14:1,
    Conference Papers | 2015
    Aleksandrov M; Aziz H; Gaspers S; Walsh T, 2015, 'Online Fair Division: Analysing a Food Bank Problem.', in Yang Q; Wooldridge MJ (ed.), IJCAI, AAAI Press, pp. 2540 - 2546,
    Conference Papers | 2015
    Aziz H; Gaspers S; Gudmundsson J; Mackenzie S; Mattei N; Walsh T, 2015, 'Computational Aspects of Multi-Winner Approval Voting.', in Weiss G; Yolum P; Bordini RH; Elkind E (eds.), AAMAS, ACM, pp. 107 - 115,
    Conference Papers | 2015
    Aziz H; Gaspers S; Gudmundsson J; Mestre J; Täubig H, 2015, 'Welfare maximization in fractional hedonic games', in IJCAI International Joint Conference on Artificial Intelligence, pp. 461 - 467
    Conference Papers | 2015
    Aziz H; Gaspers S; Mackenzie S; Mattei N; Narodytska N; Walsh T, 2015, 'Equilibria Under the Probabilistic Serial Rule.', in Yang Q; Wooldridge MJ (ed.), IJCAI, AAAI Press, pp. 1105 - 1112,
    Conference Papers | 2015
    Aziz H; Gaspers S; Mackenzie S; Mattei N; Narodytska N; Walsh T, 2015, 'Manipulating the Probabilistic Serial Rule.', in Weiss G; Yolum P; Bordini RH; Elkind E (eds.), AAMAS, ACM, pp. 1451 - 1459,
    Conference Papers | 2015
    Gaspers S; Mackenzie S, 2015, 'On the Number of Minimal Separators in Graphs.', in Mayr EW (ed.), WG, Springer, pp. 116 - 121,
    Conference Papers | 2015
    Gaspers S; Sorkin GB, 2015, 'Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.', in Halldórsson MM; Iwama K; Kobayashi N; Speckmann B (eds.), ICALP (1), Springer, pp. 567 - 579,
    Conference Papers | 2014
    Aziz H; Gaspers S; Mackenzie S; Mattei N; Stursberg P; Walsh T, 2014, 'Fixing a balanced knockout tournament', in Proceedings of the National Conference on Artificial Intelligence, pp. 552 - 558
    Conference Papers | 2014
    Aziz H; Gaspers S; Mackenzie S; Walsh T, 2014, 'Fair Assignment Of Indivisible Objects Under Ordinal Preferences', in AAMAS'14: PROCEEDINGS OF THE 2014 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS, ASSOC COMPUTING MACHINERY, FRANCE, Paris, pp. 1305 - 1312, presented at International Conference on Autonomous Agents and Multiagent Systems (AAMAS), FRANCE, Paris, 05 May 2014 - 09 May 2014,
    Conference Papers | 2014
    Aziz H; Gaspers S; Mackenzie S; Walsh T, 2014, 'Fair assignment of indivisible objects under ordinal preferences', in Bazzan ALC; Huhns MN; Lomuscio A; Scerri P (eds.), 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, Elsevier, pp. 1305 - 1312,
    Conference Papers | 2014
    Gaspers S; Misra N; Ordyniak S; Szeider S; Zivny S, 2014, 'Backdoors into Heterogeneous Classes of SAT and CSP', in PROCEEDINGS OF THE TWENTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE, CANADA, Quebec City, pp. 2652 - 2658, presented at 28th AAAI Conference on Artificial Intelligence, CANADA, Quebec City, 27 July 2014 - 31 July 2014,
    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 | 2014
    Gaspers S; Naroditskiy V; Narodytska N; Walsh T, 2014, 'Possible and Necessary Winner Problem in Social Polls (extended abstract)', Saint Paul, presented at roceedings of the 2013 international conference on Autonomous agents and multi-agent system, Saint Paul, 06 May 2014 - 10 May 2014,
    Conference Papers | 2014
    Gaspers S; Naroditskiy V; Narodytska N; Walsh T, 2014, 'Possible and necessary winner problem in social polls', in 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, pp. 613 - 620
    Conference Papers | 2013
    Aziz H; Gaspers S; Mattei N; Narodytska N; Walsh T, 2013, 'Ties matter: Complexity of manipulation when tie-breaking with a random vote', in desJardins, M; Littman M (ed.), Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013, Bellevue, Washington, USA, pp. 74 - 80, presented at 27th AAAI Conference on Artificial Intelligence, AAAI 2013, Bellevue, Washington, USA, 14 July 2013 - 18 July 2013,
    Conference Papers | 2013
    Chu G; Gaspers S; Narodytska N; Schutt A; Walsh T, 2013, 'On the complexity of global scheduling constraints under structural restrictions', in IJCAI International Joint Conference on Artificial Intelligence, pp. 503 - 509
    Conference Papers | 2013
    Frati F; Gaspers S; Gudmundsson J; Mathieson L, 2013, 'Augmenting Graphs to Minimize the Diameter', Springer, pp. 383 - 393, presented at ISAAC 2013: 24th Annual International Symposium on Algorithms and Computation, 16 December 2013 - 18 December 2013,
    Conference Papers | 2013
    Gaspers S; Kalinowski T; Narodytska N; Walsh T, 2013, 'Coalitional manipulation for Schulze's rule.', in Gini ML; Shehory O; Ito T; Jonker CM (eds.), AAMAS, IFAAMAS, pp. 431 - 438,
    Conference Papers | 2013
    Gaspers S; Kim EJ; Ordyniak S; Saurabh S; Szeider S, 2013, 'Don't Be Strict in Local Search!', in Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, Bellevue, WAshington, USA, pp. 486 - 492, presented at Twenty-Seventh Conference on Artificial Intelligence (AAAI-13), Bellevue, WAshington, USA, 14 July 2013 - 18 July 2013,
    Conference Papers | 2013
    Gaspers S; Koivisto M; Liedloff M; Ordyniak S; Szeider S, 2013, 'On Finding Optimal Polytrees', in Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, Bellevue, WAshington, USA, pp. 750 - 756, presented at Twenty-Seventh Conference on Artificial Intelligence (AAAI-13), Bellevue, WAshington, USA, 14 July 2013 - 18 July 2013,
    Conference Papers | 2013
    Gaspers S; Ordyniak S; Ramanujan MS; Saurabh S; Szeider S, 2013, 'Backdoors to q-Horn', Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 67 - 79, presented at 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Dagstuhl, Germany, 27 February 2013 - 02 March 2013,
    Conference Papers | 2013
    Gaspers S; Szeider S, 2013, 'Strong Backdoors to Bounded Treewidth SAT', in Reingold O (ed.), Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, Berkeley, CA, USA, presented at FOCS 2013: 54th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, USA, 27 October 2013 - 29 October 2013
    Conference Papers | 2013
    van Bevern R; Fellows MR; Gaspers S; Rosamond FA, 2013, 'Myhill-Nerode Methods for Hypergraphs', in Algorithms and Computation, Springer, pp. 372 - 382, presented at ISAAC 2013: 24th Annual International Symposium on Algorithms and Computation, 16 December 2013 - 18 December 2013,
    Conference Papers | 2012
    Fomin FV; Gaspers S; Fomin FV; Suchan K; Szeider S; van Leeuwen EJ; Vatshelle M; Villanger Y, 2012, 'k-Gap Interval Graphs', in Proceedings of the 10th Latin American Symposium on Theoretical Informatics, Springer, Berlin, pp. 350 - 361, presented at 10th Latin American Symposium on Theoretical Informatics, Arequipa, Peru, 16 April 2012 - 20 April 2012,
    Conference Papers | 2012
    Gaspers S; Szeider S, 2012, 'Backdoors to Acyclic SAT', in Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), LNCS 7391, Springer, Warwick, UK, pp. 363 - 374, presented at International Colloquium on Automata, Languages and Programming, Warwick, UK, 09 July 2012 - 13 July 2012,
    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,
    Conference Papers | 2011
    Gaspers S; Liedloff M; Stein M; Suchan K, 2011, 'Complexity of splits reconstruction for low-degree trees', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 167 - 178,
    Conference Papers | 2011
    Gaspers S; Szeider S, 2011, 'Kernels for global constraints', in IJCAI International Joint Conference on Artificial Intelligence, pp. 540 - 545,
    Conference Papers | 2011
    Gaspers S; Szeider S, 2011, 'The parameterized complexity of local consistency', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 302 - 316,
    Conference Papers | 2010
    Fellows MR; Gaspers S; Rosamond FA, 2010, 'Parameterizing by the number of numbers', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 123 - 134,
    Conference Papers | 2010
    Fernau H; Gaspers S; Raible D, 2010, 'Exact and parameterized algorithms for max internal spanning tree', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 100 - 111,
    Conference Papers | 2010
    Gaspers S; Mnich M, 2010, 'Feedback vertex sets in tournaments', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 267 - 277,
    Conference Papers | 2009
    Bessy S; Fomin FV; Gaspers S; Paul C; Perez A; Saurabh S; Thomasse S, 2009, 'Kernels for feedback arc set in tournaments', in Leibniz International Proceedings in Informatics, LIPIcs, pp. 37 - 47,
    Conference Papers | 2009
    Fernau H; Gaspers S; Kratsch D; Liedloff M; Raible D, 2009, 'Exact exponential-time algorithms for finding bicliques in a graph', in 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009 - Proceedings of the Conference, pp. 205 - 209
    Conference Papers | 2009
    Fomin FV; Gaspers S; Saurabh S; Thomassé S, 2009, 'A linear vertex kernel for Maximum Internal Spanning Tree', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 275 - 282,
    Conference Papers | 2009
    Fürer M; Gaspers S; Kasiviswanathan SP, 2009, 'An exponential time 2-approximation algorithm for bandwidth', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 173 - 184,
    Conference Papers | 2009
    Gaspers S; Sorkin GB, 2009, 'A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between', in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 606 - 615,
    Conference Papers | 2008
    Fomin FV; Gaspers S; Kratsch D; Liedloff M; Saurabh S, 2008, 'Iterative compression and exact algorithms', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 335 - 346,
    Conference Papers | 2008
    Gaspers S; Kratsch D; Liedloff M, 2008, 'On independent sets and bicliques in graphs', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 171 - 182,
    Conference Papers | 2008
    Gaspers S; Saurabh S; Stepanov AA, 2008, 'A moderately exponential time algorithm for full degree spanning tree', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 479 - 489,
    Conference Papers | 2007
    Fomin FV; Gaspers S; Saurabh S, 2007, 'Improved exact algorithms for counting 3- and 4-colorings', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 65 - 74,
    Conference Papers | 2006
    Fomin FV; Gaspers S; Pyatkin AV, 2006, 'Finding a minimum feedback vertex set in time O(1.7548n)', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 184 - 191,
    Conference Papers | 2006
    Fomin FV; Gaspers S; Saurabh S, 2006, 'Branching and treewidth based exact algorithms', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 16 - 25,
    Conference Papers | 2006
    Gaspers S; Kratsch D; Liedloff M, 2006, 'Exponential time algorithms for the minimum dominating set problem on some graph classes', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 148 - 159,
    Conference Papers | 2006
    Gaspers S; Liedloff M, 2006, 'A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 78 - 89,

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

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

My Teaching

I designed and teach .