Staff profile

I am an Associate Professor at Durham University in the Algorithms and Complexity Group (ACiD) within the Department of Computer Science. I was previously a lecturer in the Foundations of Computing Group at Middlesex University. Before my permanent appointments I undertook a number of post-doctoral positions in Durham and Paris.

My interests include Complexity Theory in general (Proof Complexity as well as Computational Complexity); Finite Model Theory; and the links between logic and complexity. I am mostly working now on forms of Constraint Satisfaction Problem, Proof Complexity and Algorithmic Graph Theory.

Conference Paper

• Lozin, V. V., Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S., & van Leeuwen, E. J. (2024, December). Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs. Presented at ISAAC, ISAAC 2024
• Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. .., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, July). Complexity framework for forbidden subgraphs IV: The Steiner Forest problem. Presented at IWOCA, Ischia, Italy
• Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, June). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. Presented at SWAT 2024, Helsinki, Finland
• Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023, August). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France
• Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
• Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022, May). Few induced disjoint paths for H-free graphs. Presented at ISCO 2022, Online
• Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022, March). The Complexity of L(p,q)-Edge-Labelling. Presented at The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021), University of Jember, East Java
• Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2023, June). Injective colouring for H-free graphs. Presented at CSR 2021, Sochi
• Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. Acyclic, star and injective colouring: bounding the diameter
• Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021, September). QCSP on reflexive tournaments. Presented at The 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon / Online
• Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Disjoint paths and connected subgraphs for H-free graphs
• Martin, B., Paulusma, D., & Smith, S. (2021, May). Colouring graphs of bounded diameter in the absence of small cycles. Presented at CIAC 2021, Virtual Event
• Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021, December). Partitioning H-free graphs of bounded diameter. Presented at 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Fukuoka, Japan
• Dantchev, S., Ghani, A., & Martin, B. (2020, May). Sherali-Adams and the binary encoding of combinatorial principles. Presented at LATIN 2020, São Paulo, Brazil
• Zhuk, D., & Martin, B. (2020, June). QCSP monsters and the demise of the chen conjecture. Presented at 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago
• Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020, September). Acyclic, star and injective colouring: a complexity picture for H-free graphs. Presented at ESA 2020, Pisa, Italy (Virtual Event)
• Martin, B., Paulusma, D., & Smith, S. (2019, August). Colouring H-free graphs of bounded diameter. Presented at MFCS 2019, Aachen, Germany
• Dantchev, S., Galesi, N., & Martin, B. (2019, July). Resolution and the binary encoding of combinatorial principles. Presented at Computational Complexity Conference, New Brunswick, New Jersey, USA
• Madelaine, F., & Martin, B. (2018, August). Consistency for counting quantifiers. Presented at 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK
• Bodirsky, M., Mamino, M., Martin, B., & Mottet, A. (2018, August). The complexity of disjunctive linear Diophantine constraints. Presented at 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK
• Bodirsky, M., Jonsson, P., Martin, B., & Mottet, A. (2018, July). Classification Transfer for Qualitative Reasoning Problems. Presented at IJCAI-ECAI 2018, the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence., Stockholm, Sweden
• Larose, B., Martin, B., & Paulusma, D. (2023, February). Surjective H-Colouring over Reflexive Digraphs. Presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France
• Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018, August). Disconnected Cuts in Claw-free Graphs. Presented at 26th Annual European Symposium on Algorithms (ESA 2018)., Helsinki, Finland
• Carvalho, C., Martin, B., Zhuk, D., Larsen, K. G., Bodlaender, H. L., & Raskin, J.-F. (2017, December). The complexity of quantified constraints using the algebraic formulation. Presented at Mathematical Foundation of Computer Science, Aalborg, Denmark
• Bodirsky, M., Martin, B., Pinsker, M., & Pongrácz, A. (2016, July). Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. Presented at 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, Rome, Italy
• Carvalho, C., Madelaine, F. R., & Martin, B. (2015, July). From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP. Presented at 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, Kyoto, Japan
• Bodirsky, M., Martin, B., & Mottet, A. (2015, July). Constraint Satisfaction Problems over the Integers with Successor. Presented at Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, Kyoto, Japan

Journal Article

• Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs I: The Framework. Algorithmica, 87(3), 429-464. https://doi.org/10.1007/s00453-024-01289-2
• Bodirsky, M., Jonsson, P., Martin, B., Mottet, A., & Semanišinová, Ž. (2024). Complexity Classification Transfer for CSPs via Algebraic Products. SIAM Journal on Computing, 53(5), 1293-1353. https://doi.org/10.1137/22m1534304
• Dantchev, S., Galesi, N., Ghani, A., & Martin, B. (2024). Proof Complexity and the Binary Encoding of Combinatorial Principles. SIAM Journal on Computing, 53(3), 764-802. https://doi.org/10.1137/20m134784x
• Dantchev, S., Galesi, N., Ghani, A., & Martin, B. (2024). Depth lower bounds in Stabbing Planes for combinatorial principles. Logical Methods in Computer Science, 20(1), 1-19. https://doi.org/10.46298/lmcs-20%281%3A1%292024
• Beyersdorff, O., Clymo, J., Dantchev, S., & Martin, B. (2024). The Riis Complexity Gap for QBF Resolution. Journal on Satisfiability, Boolean Modeling and Computation, 15(1), 9-25. https://doi.org/10.3233/sat-231505
• Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, 85(11), 3406-3429. https://doi.org/10.1007/s00453-023-01120-4
• Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2023). Few induced disjoint paths for H-free graphs. Theoretical Computer Science, 939, 182-193. https://doi.org/10.1016/j.tcs.2022.10.024
• Carvalho, C., Madelaine, F., Martin, B., & Zhuk, D. (2023). The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. ACM Transactions on Computational Logic, 24(1), Article 5. https://doi.org/10.1145/3568397
• Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z
• Zhuk, D., & Martin, B. (2022). QCSP Monsters and the Demise of the Chen Conjecture. Journal of the ACM, 69(5), 1-44. https://doi.org/10.1145/3563820
• Martin, B., Paulusma, D., & Smith, S. (2022). Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theoretical Computer Science, 931, 104-116. https://doi.org/10.1016/j.tcs.2022.07.034
• Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2022). Partitioning H-free graphs of bounded diameter. Theoretical Computer Science, 930, 37-52. https://doi.org/10.1016/j.tcs.2022.07.009
• Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), 1-22. https://doi.org/10.1145/3508069
• Martin, B., Paulusma, D., & Smith, S. (2022). Colouring graphs of bounded diameter in the absence of small cycles. Discrete Applied Mathematics, 314, 150-161. https://doi.org/10.1016/j.dam.2022.02.026
• Martin, B., Paulusma, D., & Smith, S. (2022). Hard problems that quickly become very easy. Information Processing Letters, 174, https://doi.org/10.1016/j.ipl.2021.106213
• Carvalho, C., & Martin, B. (2022). The lattice and semigroup structure of multipermutations. International Journal of Algebra and Computation, 32(2), 211-235. https://doi.org/10.1142/s0218196722500096
• Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Disjoint paths and connected subgraphs for H-free graphs. Theoretical Computer Science, 898, 59-68. https://doi.org/10.1016/j.tcs.2021.10.019
• Brause, C., Golovach, P., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2022). Acyclic, Star, and Injective Colouring: Bounding the diameter. Electronic Journal of Combinatorics, 29(2), https://doi.org/10.37236/10738
• Martin, B., Paulusma, D., & van Leeuwen, E. (2020). Disconnected cuts in claw-free graphs. Journal of Computer and System Sciences, 113, 60-75. https://doi.org/10.1016/j.jcss.2020.04.005
• Bodirsky, M., Martin, B., Pinsker, M., & Pongracz, A. (2019). Constraint satisfaction problems for reducts of homogeneous graphs. SIAM Journal on Computing, 48(4), 1224-1264. https://doi.org/10.1137/16m1082974
• Golovach, P., Johnson, M., Martin, B., Paulusma, D., & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability, 8(1), 27-42. https://doi.org/10.3233/com-180084
• Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory, 11(1), Article 3. https://doi.org/10.1145/3282431
• Madelaine, F. R., & Martin, B. D. (2018). On the Complexity of the Model Checking Problem. SIAM Journal on Computing, 47(3), 769-797. https://doi.org/10.1137/140965715
• Bodirsky, M., Martin, B., & Mottet, A. (2018). Discrete Temporal Constraint Satisfaction Problems. Journal of the ACM, 65(2), Article 9. https://doi.org/10.1145/3154832
• Glaßer, C., Jonsson, P., & Martin, B. (2017). Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic. Theoretical Computer Science, 703, 18-36. https://doi.org/10.1016/j.tcs.2017.08.025
• Martin, B., Raimondi, F., Chen, T., & Martin, J. (2017). The packing chromatic number of the infinite square lattice is between 13 and 15. Discrete Applied Mathematics, 225, 136-142. https://doi.org/10.1016/j.dam.2017.03.013
• Đapić, P., Marković, P., & Martin, B. (2017). Quantified Constraint Satisfaction Problem on semicomplete digraphs. ACM Transactions on Computational Logic, 18(1), Article 2. https://doi.org/10.1145/3007899
• Martin, B., Pongrácz, A., & Wrona, M. (2017). The complexity of counting quantifiers on equality languages. Theoretical Computer Science, 670, 56-67. https://doi.org/10.1016/j.tcs.2017.01.022
• Martin, B., & Paulusma, D. (2015). The computational complexity of disconnected cut and 2K2-partition. Journal of Combinatorial Theory, Series B, 111, 17-37. https://doi.org/10.1016/j.jctb.2014.09.002
• Dantchev, S., & Martin, B. (2013). Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. Computational Complexity, 22(1), 191-213. https://doi.org/10.1007/s00037-012-0049-1
• Dantchev, S., Martin, B., & Szeider, S. (2011). Parameterized Proof Complexity. Computational Complexity, 20(1), 51-85. https://doi.org/10.1007/s00037-010-0001-1