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

  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

• 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.