Hubie (Hubert) Chen

Department of Informatics
King’s College London
London, United Kingdom

E-mail address: (five-letter first name)(dot)(last name) plus (at)(kcl)(dot)(ac)(dot)(uk)

Book

Computability and Complexity, by Hubie Chen. MIT Press, 2023.
MIT Press website for book

Reception

“A beautifully comprehensive introduction to automata, computability, and complexity theory …” – Ryan Williams, MIT

“… discusses the landmark theorems very carefully. The definitions are clear and well-motivated, while the results and full formal proofs are illustrated by well-chosen examples. Students, instructors, and computer scientists will surely love this fascinating book.” – Georg Gottlob, University of Oxford

“The subject is built up very carefully … This is a very complete treatment of the standard subject.” – MAA Reviews

“The physical book is attractively constructed, with beautiful and informative illustrations. … The explanation of fixed-parameter tractability (FPT) in Chen’s book is the best I have seen. … I am glad that Chen has brought [FPT] to the standard curriculum with his well-crafted textbook.” – Bulletin of Symbolic Logic

“… deserving of a place on the bookshelf of anyone planning to do research in theory of computation.” – SIGACT News

Description

This initiation to the theory of computation has been praised as a “beautifully comprehensive introduction to automata, computability, and complexity theory” that “discusses the landmark theorems very carefully” and is “presented with a high level of mathematical rigor.” This book combines intuitive discussion—backed by numerous diagrams and examples—with a precise mathematical treatment that includes comprehensive proofs.

Topics covered by this book include:

• Automata theory – deterministic and nondeterministic finite automata, regular expressions, proving non-regularity via Myhill-Nerode theory, DFA minimization;

• Computability theory – deterministic and nondeterministic Turing machines, universal Turing machines, diagonalization and non-computable languages, reductions, Rice’s theorem;

• Complexity theory – time complexity classes (P, NP, and coNP), the P versus NP question, the theories of NP-completeness and of coNP-completeness, numerous completeness proofs, the space complexity class PSPACE, hierarchy theorems, parameterized complexity.

Numerous exercises and notes expand upon the main presentation and cover topics such as Gödel incompleteness, counting complexity, logarithmic space complexity, and treewidth.

An excerpt of this book is freely useable and freely distributable under a Creative Commons CC-BY-NC-ND license.

Selected articles

• Mahmoud Abo Khamis and Hubie Chen.
  Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time.
  PODS 2026.

• Hubie Chen and Stefan Mengel.
  Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity.
  ICDT 2024. Invited to LMCS special issue of ICDT 2024.

• Hubie Chen, Gianluigi Greco, Stefan Mengel, and Francesco Scarcello.
  Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability.
  arXiv:2311.14579.

• Hubie Chen.
  Algebraic Global Gadgetry for Surjective Constraint Satisfaction.
  Computational Complexity (33) 7, 2024.

• Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski.
  Sparsification Lower Bounds for List H-Coloring.
  ACM Transactions on Computation Theory (15) 3-4: 8:1-8:23, 2023.

• Hubie Chen, Georg Gottlob, Matthias Lanzinger, and Reinhard Pichler.
  Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems.
  International Joint Conference on Artificial Intelligence (IJCAI), pp 1726–1733, 2020.

• Hubie Chen and Yuichi Yoshida.
  Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory.
  Symposium on Principles of Database Systems (PODS), Amsterdam, The Netherlands, pp 365–382, 2019.

• Hubie Chen.
  The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems.
  Symposium on Principles of Database Systems (PODS), Amsterdam, The Netherlands, pp 383–398, 2019.

• Christoph Berkholz and Hubie Chen.
  Compiling Existential Positive Queries to Bounded-Variable Fragments.
  Symposium on Principles of Database Systems (PODS), Amsterdam, The Netherlands, pp 353–364, 2019.

• Simone Bova and Hubie Chen.
  How Many Variables are Needed to Express an Existential Positive Query?.
  Theory of Computing Systems 63(7): 1573–1594, 2019. Conference version appeared in: International Conference on Database Theory (ICDT), Venice, Italy, pp 9:1–9:16, 2017. ICDT 2017 Best Paper Award.

  Note: H. Andréka, J. van Benthem, and I. Németi point out (in their Section 2) that this article settles a “long-standing open problem”.

• Hubie Chen and Matthew Valeriote.
  Learnability of Solutions to Conjunctive Queries.
  Journal of Machine Learning Research 20: 67:1–67:28, 2019. Conference version appeared in: Conference on Learning Theory (COLT), Paris, France, pp 326–337, 2015.

• Hubie Chen and Stefan Mengel.
  The logic of counting query answers.
  Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, pp 1–12, 2017.

• Hubie Chen and Benoît Larose.
  Asking the Metaquestions in Constraint Tractability.
  ACM Transactions on Computation Theory 9(3): 11:1–11:27, 2017.

• Hubie Chen and Stefan Mengel.
  Counting Answers to Existential Positive Queries: A Complexity Classification.
  Symposium on Principles of Database Systems (PODS), San Francisco, USA, pp 315–326, 2016.

• Hubie Chen, Matthew Valeriote, and Yuichi Yoshida.
  Testing Assignments to Constraint Satisfaction Problems.
  Symposium on Foundations of Computer Science (FOCS), New Brunswick, New Jersey, USA, pp 525–534, 2016.