research | Serge Gaspers

My research and research interests mainly fall under the following topics.

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

A Piecewise Approach for the Analysis of Exact Algorithms

Katie Clinch, Serge Gaspers, Abdallah Saffidine, and Tiankuang Zhang

arXiv CoRR, 2024

@article{ClinchGSZ24,
  author = {Clinch, Katie and Gaspers, Serge and Saffidine, Abdallah and Zhang, Tiankuang},
  journal = {arXiv CoRR},
  title = {A Piecewise Approach for the Analysis of Exact Algorithms},
  year = {2024},
  volume = {abs/2402.10015}
}

arXiv

Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and Packing Problems

Serge Gaspers, and Jerry Zirui Li

arXiv CoRR, 2023

Bib arXiv

@article{GaspersL23q,
  author = {Gaspers, Serge and Li, Jerry Zirui},
  journal = {arXiv CoRR},
  title = {Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and Packing Problems},
  year = {2023},
  volume = {abs/2311.08042}
}

JACM

Exact Algorithms via Monotone Local Search

Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh

Journal of the ACM, 2019

URL Bib arXiv

@article{FominGLS19,
  author = {Fomin, Fedor V. and Gaspers, Serge and Lokshtanov, Daniel and Saurabh, Saket},
  title = {Exact Algorithms via Monotone Local Search},
  journal = {Journal of the {ACM}},
  volume = {66},
  number = {2},
  pages = {8:1--8:23},
  year = {2019},
  url = {https://doi.org/10.1145/3284176},
  doi = {10.1145/3284176}
}

TALG

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets

Serge Gaspers, and Gregory B. Sorkin

ACM Transactions on Algorithms, 2017

URL Bib arXiv

@article{GaspersS17,
  author = {Gaspers, Serge and Sorkin, Gregory B.},
  title = {Separate, Measure and Conquer: Faster Polynomial-Space Algorithms
                    for Max 2-CSP and Counting Dominating Sets},
  journal = {{ACM} Transactions on Algorithms},
  volume = {13},
  number = {4},
  pages = {44:1--44:36},
  year = {2017},
  url = {https://doi.org/10.1145/3111499},
  doi = {10.1145/3111499}
}

ICALP

Exact Algorithms via Multivariate Subroutines

Serge Gaspers, and Edward J. Lee

In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, 2017

URL Bib arXiv

@inproceedings{GaspersL18,
  author = {Gaspers, Serge and Lee, Edward J.},
  editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  title = {Exact Algorithms via Multivariate Subroutines},
  booktitle = {44th International Colloquium on Automata, Languages, and Programming,
                    {ICALP} 2017, July 10-14, 2017, Warsaw, Poland},
  series = {LIPIcs},
  volume = {80},
  pages = {69:1--69:13},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2017},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.69},
  doi = {10.4230/LIPIcs.ICALP.2017.69}
}

ICALP

The Parameterized Complexity of Positional Games

Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, and Abdallah Saffidine

In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, 2017

URL Bib arXiv

@inproceedings{BonnetGLRS17,
  author = {{\'{E}}douard Bonnet and Gaspers, Serge and Lambilliotte, Antonin and R{\"{u}}mmele, Stefan and Saffidine, Abdallah},
  editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  title = {The Parameterized Complexity of Positional Games},
  booktitle = {44th International Colloquium on Automata, Languages, and Programming,
                    {ICALP} 2017, July 10-14, 2017, Warsaw, Poland},
  series = {LIPIcs},
  volume = {80},
  pages = {90:1--90:14},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2017},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.90},
  doi = {10.4230/LIPIcs.ICALP.2017.90}
}

FOCS

Strong Backdoors to Bounded Treewidth SAT

Serge Gaspers, and Stefan Szeider

In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, 2013

URL Bib arXiv

@inproceedings{GaspersS13,
  author = {Gaspers, Serge and Szeider, Stefan},
  title = {Strong Backdoors to Bounded Treewidth {SAT}},
  booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
                    2013, 26-29 October, 2013, Berkeley, CA, {USA}},
  pages = {489--498},
  publisher = {{IEEE} Computer Society},
  year = {2013},
  url = {https://doi.org/10.1109/FOCS.2013.59},
  doi = {10.1109/FOCS.2013.59}
}

JCSS

A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between

Serge Gaspers, and Gregory B. Sorkin

Journal of Computer and System Sciences, 2012

URL Bib arXiv

@article{GaspersS12,
  author = {Gaspers, Serge and Sorkin, Gregory B.},
  title = {A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything
                    in between},
  journal = {Journal of Computer and System Sciences},
  volume = {78},
  number = {1},
  pages = {305--335},
  year = {2012},
  url = {https://doi.org/10.1016/j.jcss.2011.05.010},
  doi = {10.1016/j.jcss.2011.05.010}
}

Algorithmica

On Two Techniques of Combining Branching and Treewidth

Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov

Algorithmica, 2009

URL Bib

@article{FominGSS09,
  techrep = {http://www.ii.uib.no/publikasjoner/texrap/pdf/2006-337.pdf},
  author = {Fomin, Fedor V. and Gaspers, Serge and Saurabh, Saket and Stepanov, Alexey A.},
  title = {On Two Techniques of Combining Branching and Treewidth},
  journal = {Algorithmica},
  volume = {54},
  number = {2},
  pages = {181--207},
  year = {2009},
  url = {https://doi.org/10.1007/s00453-007-9133-3},
  doi = {10.1007/s00453-007-9133-3}
}

Algorithmica

On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms

Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon

Algorithmica, 2008

URL Bib

@article{FominGPR08,
  author = {Fomin, Fedor V. and Gaspers, Serge and Pyatkin, Artem V. and Razgon, Igor},
  title = {On the Minimum Feedback Vertex Set Problem: Exact and Enumeration
                    Algorithms},
  journal = {Algorithmica},
  volume = {52},
  number = {2},
  pages = {293--307},
  year = {2008},
  url = {https://doi.org/10.1007/s00453-007-9152-0},
  doi = {10.1007/s00453-007-9152-0}
}