Research interests
- Algorithms and Complexity
- exponential time algorithms
- parameterized complexity
- quantum algorithms
- combinatorial optimization
- Combinatorics
- extremal combinatorics
- graph classes
- graph decompositions
- Satisfiability and Constraints
- backdoors
- (local) consistency
- global constraints
- propagation
- Applications
- algorithmic game theory
- computational social choice
- preprocessing
- resource allocation
- scheduling
Selected publications
J31
Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh.
Exact Algorithms via Monotone Local Search.
J. ACM 2019.
[doi] [arXiv]
C53
Serge Gaspers and Edward J. Lee.
Exact Algorithms via Multivariate Subroutines.
ICALP 2017.
[arXiv]
C52
Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, and Abdallah Saffidine.
The Parameterized Complexity of Positional Games.
ICALP 2017.
[arXiv]
J26
Serge Gaspers and Gregory B. Sorkin.
Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets.
ACM Trans. Algorithms 2017.
[doi] [arXiv]
C30
Serge Gaspers and Stefan Szeider.
Strong Backdoors to Bounded Treewidth SAT.
FOCS 2013.
[doi] [arXiv] [pdf]
J10
Serge Gaspers and Gregory B. Sorkin.
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.
Journal of Computer and System Sciences 2012.
[doi] [arXiv] [pdf]
J3
Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov.
On Two Techniques of Combining Branching and Treewidth.
Algorithmica 2009.
[doi] [TR] [pdf]
J1
Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon.
On the minimum feedback vertex set problem: Exact and enumeration algorithms.
Algorithmica 2008.
[doi] [pdf]
You might have seen me here:
-
Frontiers of Parameterized Complexity: online seminar series, since April 2020.
-
COMSOC Video Seminar: international seminar series on social choice, since April 2020.
-
Algorithmic Graph Theory Seminar Series: Monday with Marty and Students of Sunil, since June 2020.
-
Online Social Choice and Welfare Seminar Series, since May 2020.
-
GAIW 2022: 4th Games, Agents, and Incentives Workshop, Barcelona, Spain (hybrid), 5-9 July 2021.
-
SAT 2021: 24th International Conference on Theory and Applications of Satisfiability Testing, Barcelona, Spain (hybrid), 5-9 July 2021.
-
AAAI 2020: the 34th AAAI Conference on Artificial Intelligence, New York, New York, USA, 7-12 February 2020.
-
WEPA 2019: 3rd International Workshop on Enumeration Problems & Applications, Awaji Island, Japan, 28-31 October 2019.
-
AI-OPT 2019: the 2019 Workshop on AI-based Optimisation, Melbourne, Australia, 1-2 October 2019.
-
MFCS 2019: the 44th International Symposium on Mathematical Foundations of Computer Science, , Aachen, Germany, 26-30 August 2019.
-
AusTrade Artificial Intelligence Mission to the US, Austin, Texas, 13-15 February 2019.
-
AAAI 2019: the 33rd AAAI Conference on Artificial Intelligence, Honolulu, Hawaii, USA, 27 January - 1 February 2019.
-
Dagstuhl Seminar on Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative, Schloss Dagstuhl, Germany, 14-19 October 2018.
-
LuxLogAI 2018: Luxembourg Logic for AI Summit, Esch-sur-Alzette, Luxembourg, 17-26 September 2018.
-
LATIN 2018: the 13th Latin American Theoretical Informatics Symposium, Buenos Aires, Argentina, 16-19 April 2018.
-
AAAI 2018: the 32nd AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, USA, 2-7 February 2018.
-
AIES 2018: the AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society, New Orleans, Louisiana, USA, 1-3 February 2018.
-
5ICC: the 5th International Combinatorics Conference, Melbourne, Australia, 4-9 December 2017.
-
ADT 2017: 5th International Conference on Algorithmic Decision Theory, Luxembourg, Luxembourg, 25-27 October 2017.
-
NII Shonan meeting on Logic and Computational Complexity, Shonan Village, Japan, 18-22 September 2017.
-
SAT 2017: 20th International Conference on Theory and Applications of Satisfiability Testing, Melbourne, Australia, 28 August - 1 September 2017.
-
IJCAI 2017: 26th International Joint Conference on Artificial Intelligence, Melbourne, Australia, 21-25 August 2017.
-
UAI 2017: the 2017 Conference on Uncertainty in Artificial Intelligence, Sydney, Australia, 11-15 August 2017.
-
ICML 2017: 34th International Conference on Machine Learning, Sydney, Australia, 6-11 August 2017.
-
IWOCA 2017: 28th International Workshop on Combinatorial Algorithms, Newcastle, Australia, 17-21 July 2017.
-
CATS 2017: Computational & Algorithmic Topology,
Sydney, University of Sydney, Australia, 27 Jun - 1 Jul 2017.
-
Friday @ Four with Charles Gretton - Let's talk about AI, panel of experts from academia and industry organized by Charles Gretton, Michael Crouch Innovation Centre, UNSW Sydney, Australia, 2 Jun 2017.
-
Inaugural conference of the French Australian Conversations series, UNSW Sydney, Australia, 1 Mar 2017.
-
CCS 2017: Computability and Complexity Symposium 2017,
Raumati (near Wellington), New Zealand, 5-8 January 2017.
-
APCO: 1st workshop on Applied Probability, Combinatorics and Optimisation,
Newcastle, Australia, December 17, 2016.
-
40ACCMCC: 40th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing,
Newcastle, Australia, December 12-16, 2016.
-
ISAAC 2016: 27th International Symposium on Algorithms and Computation,
Sydney, Australia, December 12-14, 2016.
-
SAW 2016: Sydney Algorithms Workshop,
Sydney, Australia, December 6-9, 2016.
-
Dagstuhl Seminar on Fair Division,
Schloss Dagstuhl, Germany, June 5-10, 2016.
-
LATIN 2016: 12th Latin American Theoretical Informatics Symposium,
Ensenada, Mexico, April 11-15, 2016.
-
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms,
Simons Institute, Berkeley, California, USA, November 2-6, 2015.
-
Dagstuhl Seminar on The Constraint Satisfaction Problem: Complexity and Approximability,
Schloss Dagstuhl, Germany, July 19-24, 2015.
-
WorKer 2015: 5th Workshop on Kernelization,
Nordfjordeid, Norway, June 1-4, 2015.
-
ASL 2015: the 2015 North American Annual Meeting of the Association for Symbolic Logic,
Urbana, Illinois, USA, March 25-28, 2015.
-
PRICAI 2014: 13th Pacific Rim International Conference on Artificial Intelligence,
Gold Coast, Queensland, Australia, December 1-5, 2014.
-
Dagstuhl Seminar on Optimality and tight results in parameterized complexity,
Schloss Dagstuhl, Germany, November 2-7, 2014.
-
Graphs & Decisions,
Luxembourg, Luxembourg, October 27-29, 2014.
-
PCCR 2014: 2nd Workshop on the Parameterized Complexity of Computational Reasoning,
Vienna, Austria, July 17-18, 2014. Part of the Vienna Summer of Logic.
-
SAT 2014: 17th International Conference on Theory and Applications of Satisfiability Testing,
Vienna, Austria, July 14-17, 2014. Part of the Vienna Summer of Logic.
-
COPA 2014: Frontiers and Connections between Parametrization and Approximation,
Bertinoro, Italy, May 25-30, 2014.
-
ISAAC 2013: 24th International Symposium on Algorithms and Computation,
Hong Kong, China, December 16-18, 2013.
-
FOCS 2013: 54th Annual Symposium on Foundations of Computer Science,
Berkeley, California, USA, October 27-29, 2013.
-
Dagstuhl Seminar on Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time,
Schloss Dagstuhl, Germany, August 11-16, 2013.
-
Parameterized Complexity 'Not About Graphs III' workshop,
Charles Darwin University, Darwin, Australia, July 31 - August 1, 2013.
-
First Symposium on Structure in Hard Combinatorial Problems,
Vienna, Austria, May 16-18, 2013.
-
WorKer 2013: 4th Workshop on Kernelization,
Warsaw, Poland, April 10-12, 2013.
-
36ACCMCC: 36th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing,
Sydney, Australia, December 10-14, 2012.
-
AI 2012: 25th Australasian Joint Conference on Artificial Intelligence,
Sydney, Australia, December 4-7, 2012.
-
COCOON 2012: 18th Annual International Computing and Combinatorics Conference,
Sydney, Australia, August 20-22, 2012.
-
SAT 2012: 15th International Conference on Theory and Applications of Satisfiability Testing,
Trento, Italy, June 17-20, 2012.
-
Dagstuhl Seminar on Data Reduction and Problem Kernels,
Schloss Dagstuhl, Germany, June 10-15, 2012.
-
LATIN 2012: 10th Latin American Theoretical Informatics Symposium,
Arequipa, Peru, April 16-20, 2012.
-
WorKer 2011: 3rd Workshop on Kernelization,
Vienna, Austria, September 2-4, 2011.
-
IJCAI 2011: 22nd International Joint Conference on Artificial Intelligence,
Barcelona, Spain, July 16-22, 2011.
-
Treewidth Workshop 2011,
Bergen, Norway, May 19-20, 2011.
-
61. Theorietag, Workshop über Algorithmen und Komplexität,
Trier, Germany, February 24-25, 2011.
-
FSTTCS 2010: 30th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science,
Chennai, India, December 15-18, 2010.
-
IPEC 2010: 5th International Symposium on Parameterized and Exact Computation,
Chennai, India, December 13-15, 2010.
-
IMPECS School 2010: IMPECS School on Parameterized and Exact Computation,
Chennai, India, December 11-12, 2010.
-
Dagstuhl Seminar on Exact Complexity of NP-hard Problems,
Schloss Dagstuhl, Germany, October 31 - November 5, 2010.
-
Discretas 2010: V Escuela de Verano en Matemáticas Discretas,
Valparaíso, Chile, January 4-8, 2010.
-
ISAAC 2009: 20th International Symposium on Algorithms and Computation,
Hawaii, USA, December 16-18, 2009.
-
WG 2009: 35th International Workshop on Graph-Theoretic Concepts in Computer Science,
Montpellier, France, June 24-26, 2009.
- GRAAL 06/2009: Meeting on "Graph Decompositions and Algorithms",
Montpellier, France, June 22-23, 2009.
-
AGAPE 2009: Spring School on Fixed Parameter and Exact Algorithms,
Ile Rousse, Corsica, France, May 25-29, 2009.
-
JCALM 05/2009: Journée Combinatoire et Algorithmes du Littoral Méditerranéen,
Laboratoire d'Informatique Fondamentale de Marseille, Marseille, France, May 7, 2009.
-
SODA 2009: 20th Annual ACM-SIAM Symposium on Discrete Algorithms,
New York, New York, USA, January 4-6, 2009.
-
Dagstuhl Seminar on Moderately Exponential Time Algorithms,
Schloss Dagstuhl, Germany, October 19-24, 2008.
-
MFCS 2008: 33rd International Symposium on Mathematical Foundations of Computer Science,
Torún, Poland, August 25-29, 2008.
-
ICALP 2008: 35th International Colloquium on Automata, Languages and Programming,
Reykjavik, Iceland, July 6-13, 2008.
-
DYNAMO 2008: 2nd Training School on Algorithmic Aspects of Dynamic Networks,
Reykjavik, Iceland, July 4-6, 2008.
-
WG 2008: 34th International Workshop on Graph-Theoretic Concepts in Computer Science,
Durham, United Kingdom, June 30 - July 2, 2008.
-
ICT Research School Seminar,
Lindås, Norway, May 15-16, 2008.
-
Research visit Martin Fürer, The Pennsylvania State University,
University Park, Pennsylvania, USA, November 4 - December 23, 2007.
-
Research visit Richard J. Nowakowski, Dalhousie University,
Halifax, Nova Scotia, Canada, September 15 - November 4, 2007.
-
Research visit Gregory Sorkin, IBM Watson Research Center,
Yorktown, New York, USA, July 20 - September 15, 2007.
-
COCOON 2007: 13th Annual International Computing and Combinatorics Conference,
Banff, Alberta, Canada, July 16-19, 2007.
-
WG 2007: 33rd International Workshop on Graph-Theoretic Concepts in Computer Science,
Jena, Germany, June 21-23, 2007.
-
SADA 2007: Summer School on Algorithmic Data Analysis,
Helsinki, Finland, May 28 - June 1, 2007.
-
Dagstuhl Seminar on Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes,
Schloss Dagstuhl, Germany, May 20-25, 2007.
-
ICT Research School Seminar,
Ulvik, Norway, May 3-4, 2007.
-
6th Annual Winter School in Algorithms, Graph Theory and Combinatorics 2007,
Finse, Norway, March 5-7, 2007.
-
ISAAC 2006: 17th International Symposium on Algorithms and Computation,
Kolkata, India, December 18-20, 2006.
-
IWPEC 2006 / ALGO 2006: 2nd International Workshop on Parameterized and Exact Computation,
Zürich, Switzerland, September 11-15, 2006.
-
SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory,
Riga, Latvia, July 6-8, 2006.
-
WG 2006: 32nd International Workshop on Graph-Theoretic Concepts in Computer Science,
Bergen, Norway, June 22-24, 2006.
-
ICT Research School Seminar,
Vatnahalsen, Norway, June 8-9, 2006.
-
5th Annual Winter School in Algorithms, Graph Theory and Combinatorics 2006,
Finse, Norway, February 12-14, 2006.
-
WG 2005: 31st International Workshop on Graph-Theoretic Concepts in Computer Science,
Metz, France, June 23-25, 2005.