Publications of Hubie Chen

• Simone Bova, Hubie Chen, and Matthew Valeriote.
  On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas.
  Theory of Computing Systems, Volume 50, Number 2 (2012), 329-353.
  An earlier version appeared in: Dagstuhl Seminar Proceedings, Seminar 09441 -- The Constraint Satisfaction Problem: Complexity and Approximability, 2010.
  

• Manuel Bodirsky, Hubie Chen, and Michael Pinsker.
  The reducts of equality up to primitive positive interdefinability.
  Journal of Symbolic Logic, Volume 75, Issue 4 (2010), 1249-1292.
  A version appears as arXiv:0810.2270.
  

• Manuel Bodirsky and Hubie Chen.
  Quantified Equality Constraints.
  SIAM Journal on Computing 39(8): 3682-3699, 2010.
  Conference version appeared in: Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS), 2007, Wroclaw, Poland.
  

• Hubie Chen and Martin Grohe.
  Constraint Satisfaction with Succinctly Specified Relations.
  Journal of Computer and System Sciences, Volume 76, Issue 8, December 2010, Pages 847-860.
  

• Hubie Chen and Omer Gimenez.
  Causal Graphs and Structurally Restricted Planning.
  Journal of Computer and System Sciences, Volume 76, Issue 7, November 2010, Pages 579-592.
  Conference version appeared in: International Conference on Automated Planning & Scheduling (ICAPS), 2008, Sydney, Australia.
  

• Manuel Bodirsky and Hubie Chen.
  Peek Arc Consistency.
  Theoretical Computer Science, Volume 411, Issue 2, January 2010, Pages 445-453.
  

• Manuel Bodirsky and Hubie Chen.
  Qualitative Temporal and Spatial Reasoning Revisited.
  Journal of Logic and Computation, 19(6):1359-1383, 2009.
  Conference version appeared in: Computer Science Logic (CSL), 2007, Lausanne, Switzerland.
  

• Hubie Chen and Omer Gimenez.
  On-the-fly Macros.
  16th Workshop on Logic, Language, Information and Computation (WOLLIC), 2009, Tokyo, Japan.
  

• Hubie Chen.
  A Rendezvous of Logic, Complexity, and Algebra.
  ACM Computing Surveys, Volume 42, Issue 1, December 2009.
  Earlier version appeared as: SIGACT News Logic Column, December 2006. (See Errata.)
  

• Manuel Bodirsky, Hubie Chen, Jan Kara, and Timo von Oertzen.
  Maximal Infinite-Valued Constraint Languages.
  Theoretical Computer Science 410 (2009), pp. 1684-1693.
  Conference version appeared in: 34th International Colloquium on Automata, Languages and Programming (ICALP), 2007, Wroclaw, Poland.

• Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, and Andrei A. Krokhin.
  The complexity of constraint satisfaction games and QCSP.
  Information and Computation, Volume 207, Issue 9, Pages 923-944, September 2009.

• Hubie Chen.
  Existentially Restricted Quantified Constraint Satisfaction.
  Information and Computation, Volume 207, Issue 3, Pages 369-388, March 2009.
  Interesting open questions: What is the exact complexity of extended quantified 2-SAT formulas (under unbounded alternation)? And what about the complexity of extended quantified affine-SAT formulas (under unbounded alternation)?

• Manuel Bodirsky and Hubie Chen.
  Relatively Quantified Constraint Satisfaction.
  Constraints, Volume 14, Issue 1, 2009.
  
• Hubie Chen, Florent Madelaine, and Barnaby Martin.
  Quantified Constraints and Containment Problems.
  Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS), 2008, Pittsburgh, Pennsylvania, USA.
  

• Hubie Chen.
  Inverse NP Problems.
  Computational Complexity, Volume 17, Number 1, Pages 94-118, April 2008.
  Conference version appeared in: 28th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2003, Bratislava, Slovak Republic.
  

• Hubie Chen.
  The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case.
  SIAM Journal on Computing, volume 37, issue 5, pages 1674-1701, 2008.
  Preliminary version.

• Andrei Bulatov, Hubie Chen, and Victor Dalmau.
  Learning Intersection-closed Classes with Signatures.
  Theoretical Computer Science, 382(3), pages 209-220, 2007.
  

• Hubie Chen and Omer Gimenez.
  Act Local, Think Global: Width Notions for Tractable Planning.
  International Conference on Automated Planning & Scheduling (ICAPS), 2007, Providence, Rhode Island, USA.
  

• Manuel Bodirsky and Hubie Chen.
  Oligomorphic Clones.
  Algebra Universalis, Volume 57, Number 1, Pages 109-125, August 2007.

• Manuel Bodirsky and Hubie Chen.
  Collapsibility in Infinite-Domain Quantified Constraint Satisfaction.
  Computer Science Logic (CSL), 2006, Szeged, Hungary.

• Hubie Chen and Victor Dalmau.
  Beyond Hypertree Width: Decomposition Methods Without Decompositions.
  Eleventh International Conference on Principles and Practice of Constraint Programming, 2005, Sitges, Spain.

• Hubie Chen and Victor Dalmau.
  From Pebble Games to Tractability: An Ambidextrous Consistency Algorithm for Quantified Constraint Satisfaction.
  Computer Science Logic (CSL), 2005, Oxford, England.

• Hubie Chen.
  The Expressive Rate of Constraints.
  Annals of Mathematics and Artificial Intelligence, volume 44, number 4, pages 341-352, August 2005.
  Conference version appeared in: Eighth International Symposium on Artificial Intelligence and Mathematics, 2004, Fort Lauderdale, Florida, USA.
  

• Hubie Chen.
  Periodic Constraint Satisfaction Problems: Tractable Subclasses.
  Constraints, volume 10, number 2, pages 97-113, 2005.
  Conference version appeared in: Ninth International Conference on Principles and Practice of Constraint Programming, 2003, Kinsale, County Cork, Ireland.
• Hubie Chen and Yannet Interian.
  A Model for Generating Random Quantified Boolean Formulas.
  Nineteenth International Joint Conference on Artificial Intelligence (IJCAI), 2005, Edinburgh, Scotland.

• Hubie Chen.
  Parameterized Compilability.
  Nineteenth International Joint Conference on Artificial Intelligence (IJCAI), 2005, Edinburgh, Scotland.

• Hubie Chen.
  Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms.
  22nd International Symposium on Theoretical Aspects of Computer Science (STACS), 2005, Stuttgart, Germany.

• Hubie Chen and Riccardo Pucella.
  A Coalgebraic Approach to Kleene Algebra with Tests.
  Theoretical Computer Science, 327(1-2), pages 23-44, 2004.
  Conference version appeared in: Coalgebraic Methods in Computer Science (CMCS), 2003, Warsaw, Poland.
• Andrei Bulatov, Hubie Chen, and Victor Dalmau.
  Learnability of Relatively Quantified Generalized Formulas.
  The 15th International Conference on Algorithmic Learning Theory (ALT), 2004, Padova, Italy.
  E.M. Gold Award.

• Hubie Chen.
  Quantified Constraint Satisfaction and 2-Semilattice Polymorphisms.
  Tenth International Conference on Principles and Practice of Constraint Programming, 2004, Toronto, Canada.

• Hubie Chen and Victor Dalmau.
  (Smart) Look-Ahead Arc Consistency and the Pursuit of CSP Tractability.
  Tenth International Conference on Principles and Practice of Constraint Programming, 2004, Toronto, Canada.

• Hubie Chen.
  Quantified Constraint Satisfaction and Bounded Treewidth.
  16th European Conference on Artificial Intelligence (ECAI), 2004, Valencia, Spain.

• Hubie Chen and Martin Pál.
  Optimization, Games, and Quantified Constraint Satisfaction.
  29th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2004, Prague, Czech Republic.
  EATCS Best Student Paper Award.
  Interesting open question: Can a classification result be proved for the maximization problems defined analogously to the minimization problems studied in this paper? In particular, for maximization, are affine constraints constant-factor approximable (in the sense defined in the paper)?

• Hubie Chen.
  Collapsibility and Consistency in Quantified Constraint Satisfaction.
  Nineteenth National Conference on Artificial Intelligence (AAAI), 2004, San Jose, California, USA.

• Hubie Chen and Stephen Chong.
  Owned Policies for Information Security.
  17th IEEE Computer Security Foundations Workshop (CSFW), 2004, Pacific Grove, California, USA.

• Hubie Chen.
  The Computational Complexity of Quantified Constraint Satisfaction.
  Ph.D. Thesis, Cornell University, August 2004.
  Note.

• Hubie Chen and Victor Dalmau.
  Looking Algebraically at Tractable Quantified Boolean Formulas.
  Seventh International Conference on Theory and Applications of Satisfiability Testing, 2004, Vancouver, British Columbia, Canada.

• Hubie Chen.
  Arithmetic Constant-Depth Circuit Complexity Classes.
  28th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2003, Bratislava, Slovak Republic.
  Conference version.
• Hubie Chen.
  A Theory of Average-Case Compilability in Knowledge Representation.
  Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), 2003, Acapulco, Mexico.
• Hubie Chen.
  Inverse Circumscription.
  Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), 2003, Acapulco, Mexico.
• Hubie Chen.
  An Algorithm for SAT Above the Threshold.
  Sixth International Conference on Theory and Applications of Satisfiability Testing, 2003, S. Margherita Ligure - Portofino, Italy.
• Hubie Chen, Carla Gomes, and Bart Selman.
  Formal Models of Heavy-Tailed Behavior in Combinatorial Search.
  Seventh International Conference on Principles and Practice of Constraint Programming, 2001, Paphos, Cyprus.