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

• Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57
• Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Few induced disjoint paths for H-free graphs. In I. Ljubić, F. Barahona, S. S. Dey, & A. Ridha Mahjoub (Eds.), Combinatorial Optimization 7th International Symposium, ISCO 2022 (89-101). https://doi.org/10.1007/978-3-031-18530-4_7
• Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In Graph-Theoretic Concepts in Computer Science. 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers (398-411). https://doi.org/10.1007/978-3-031-15914-5_29
• Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022). The Complexity of L(p,q)-Edge-Labelling. In P. Mutzel, M. . S. Rahman, & Slamin (Eds.), WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings (175-186). https://doi.org/10.1007/978-3-030-96731-4_15
• Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2021). Injective colouring for H-free graphs.
• Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021). QCSP on reflexive tournaments. In P. Mutzel, R. Pagh, & G. Herman (Eds.), . https://doi.org/10.4230/lipics.esa.2021.58
• Martin, B., Paulusma, D., & Smith, S. (2021). Colouring graphs of bounded diameter in the absence of small cycles. In T. Calamoneri, & F. Corò (Eds.), . https://doi.org/10.1007/978-3-030-75242-2_26
• Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2021). Disjoint paths and connected subgraphs for H-free graphs. In P. Flocchini, & L. Moura (Eds.), Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings (414-427). https://doi.org/10.1007/978-3-030-79987-8_29
• Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021). Partitioning H-free graphs of bounded diameter. In H. Ahn, & K. Sadakane (Eds.), . https://doi.org/10.4230/lipics.isaac.2021.21
• Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2021). Acyclic, star and injective colouring: bounding the diameter. In Ł. Kowalik, M. Pilipczuk, & P. Rzążewski (Eds.), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers (336-348). https://doi.org/10.1007/978-3-030-86838-3_26
• Dantchev, S., Ghani, A., & Martin, B. (2020). Sherali-Adams and the binary encoding of combinatorial principles. In Y. Kohayakawa, & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics (336-347). https://doi.org/10.1007/978-3-030-61792-9_27
• Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020). Acyclic, star and injective colouring: a complexity picture for H-free graphs. . https://doi.org/10.4230/lipics.esa.2020.22
• Zhuk, D., & Martin, B. (2020). QCSP monsters and the demise of the chen conjecture. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, & J. Chuzhoy (Eds.), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (91-104). https://doi.org/10.1145/3357713.3384232
• Martin, B., Paulusma, D., & Smith, S. (2019). Colouring H-free graphs of bounded diameter. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (14:1-14:14). https://doi.org/10.4230/lipics.mfcs.2019.14
• Dantchev, S., Galesi, N., & Martin, B. (2019). Resolution and the binary encoding of combinatorial principles. In A. Shpilka (Ed.), 34th Computational Complexity Conference (CCC 2019) (6:1-6:25). https://doi.org/10.4230/lipics.ccc.2019.6
• Bodirsky, M., Mamino, M., Martin, B., & Mottet, A. (2018). The complexity of disjunctive linear Diophantine constraints. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK) (33:1-33:16). https://doi.org/10.4230/lipics.mfcs.2018.33
• Madelaine, F., & Martin, B. (2018). Consistency for counting quantifiers. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK) (11:1-11:13). https://doi.org/10.4230/lipics.mfcs.2018.11
• Bodirsky, M., Jonsson, P., Martin, B., & Mottet, A. (2018). Classification Transfer for Qualitative Reasoning Problems. In J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18) (1256-1262). https://doi.org/10.24963/ijcai.2018/175
• Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over Reflexive Digraphs. In R. Niedermeier, & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France (49:1-49:14). https://doi.org/10.4230/lipics.stacs.2018.49
• Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018). Disconnected Cuts in Claw-free Graphs. In Y. Azar, H. Bast, & G. Herman (Eds.), 26th Annual European Symposium on Algorithms (ESA 2018) (61:1-61:14). https://doi.org/10.4230/lipics.esa.2018.61
• Carvalho, C., Martin, B., Zhuk, D., Larsen, K. G., Bodlaender, H. L., & Raskin, J. (2017). The complexity of quantified constraints using the algebraic formulation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.27
• Bodirsky, M., Martin, B., Pinsker, M., & Pongrácz, A. (2016). Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 12–15, 2016. https://doi.org/10.4230/lipics.icalp.2016.119
• Carvalho, C., Madelaine, F. R., & Martin, B. (2015). From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP. In Proceedings, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015) : 6-10 July 2015, Kyoto, Japan (462-474). https://doi.org/10.1109/lics.2015.50
• Bodirsky, M., Martin, B., & Mottet, A. (2015). Constraint Satisfaction Problems over the Integers with Successor. In M. M. Halldórsson, K. Iwama, N. Kobayashi, & B. Speckmann (Eds.), Automata, languages, and programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015. Proceedings. Part I (256-267). https://doi.org/10.1007/978-3-662-47672-7_21

Journal Article

• 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
• 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
• Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, https://doi.org/10.1007/s00453-023-01120-4
• 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
• 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
• 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
• 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