Hubie (Hubert) Chen

 

Selected publications


  • Hubie Chen.
    Algebraic Global Gadgetry for Surjective Constraint Satisfaction.
    arXiv:2005.11307

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

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

  • Christoph Berkholz and Hubie Chen.
    Compiling Existential Positive Queries to Bounded-Variable Fragments.
    38th Symposium on Principles of Database Systems (PODS), 2019, Amsterdam, The Netherlands.
    ​
  • Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse.
    Best-case and Worst-case Sparsifiability of Boolean CSPs.
    13th International Symposium on Parameterized and Exact Computation (IPEC), 2018, Helsinki, Finland.
    arXiv:1809.06171

  • Hubie Chen and Stefan Mengel.
    The Logic of Counting Query Answers.
    32nd ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017, Reykjavik, Iceland.​
    arXiv:1501.07195
    Video of talk at Simons Institute (youtube)

  • Hubie Chen.
    The Tractability Frontier of Graph-Like First-Order Query Sets.
    Journal of the ACM, Volume 64, Issue 4, Article number 26, September 2017.
    Conference version appeared in: Joint Meeting of 23rd EACSL Annual Conference on Computer Science Logic (CSL) and 29th ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014, Vienna, Austria.
    arXiv:1407.3429
    ​
  • Simone Bova and Hubie Chen.
    How many variables are needed to express an existential positive query?
    20th International Conference on Database Theory (ICDT), 2017, Venice, Italy. 
    ICDT 2017 Best Paper Award.

  • Hubie Chen, Matthew Valeriote, and Yuichi Yoshida.
    Testing assignments to constraint satisfaction problems.
    57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016, New Brunswick, USA.
    arXiv:1608.03017
    ​
  • Hubie Chen and Peter Mayr.
    Quantified Constraint Satisfaction on Monoids.
    25th EACSL Annual Conference on Computer Science Logic (CSL), 2016, ​Marseille, France.

  • Hubie Chen.
    Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness.
    43rd International Colloquium on Automata, Languages, and Programming (ICALP), 2016, Rome, Italy. 
    arXiv:1410.5369
    ​
  • Hubie Chen and Stefan Mengel.
    Counting Answers to Existential Positive Queries: A Complexity Classification.
    35th ACM SIGMOD–SIGACT–SIGART Symposium on Principles of Database Systems (PODS), 2016, San Francisco, USA.
    arXiv:1601.03240

  • Hubie Chen and Benoit Larose.
    Asking the metaquestions in constraint tractability.
    arXiv:1604.00932

  • Hubie Chen.
    Parameter Compilation.
    International Symposium on Parameterized and Exact Computation (IPEC), 2015, Patras, Greece.
    arXiv:1503.00260

  • Hubie Chen and Matthew Valeriote.
    Learnability of Solutions to Conjunctive Queries: The Full Dichotomy.
    Conference On Learning Theory (COLT), 2015, Paris, France.

  • Hubie Chen and Stefan Mengel.
    A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries.
    18th International Conference on Database Theory (ICDT), pp 110-126, 2015, Brussels, Belgium. 
    arXiv:1408.0890
    ​
  • Hubie Chen.
    Beyond Q-Resolution and Prenex Form: A Proof System for Quantified Constraint Satisfaction.
    Logical Methods in Computer Science,     Vol. 10 (4:14), 2014, pp. 1-21.
    arXiv:1403.0222.

  • Hubie Chen.
    An Algebraic Hardness Criterion for Surjective Constraint Satisfaction.
    Algebra Universalis, Volume 72, Issue 4, pp 393-401, December 2014.
    arXiv:1405.4917.

  • Hubie Chen and Moritz Müller. 
    One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries.
    Joint Meeting of 23rd EACSL Annual Conference on Computer Science Logic (CSL) and 29th ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014, Vienna, Austria.

  • Simone Bova and Hubie Chen.
    The Complexity of Width Minimization for Existential Positive Queries.
    17th International Conference on Database Theory (ICDT), 2014, Athens, Greece.

  • Hubie Chen and Moritz Müller. 
    The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity.
    ACM Transactions on Computation Theory, Volume 7, Number 2, May 2015.
    arXiv:1306.5424.
    Conference version appeared in: 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), 2013, New York, USA.

  • Hubie Chen and Dániel Marx.
    Block-Sorted Quantified Conjunctive Queries.
    40th International Colloquium on Automata, Languages, and Programming (ICALP), 2013, Riga, Latvia.

  • Hubie Chen.
    On the Complexity of Existential Positive Queries.
    ACM Transactions on Computational Logic, Volume 15, Number 1, 2014.
    A version appears as arXiv:1206.3902.

  • Hubie Chen.
    Meditations on Quantified Constraint Satisfaction.
    Logic and Program Semantics - Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday, Lecture Notes in Computer Science 7230, Springer, 2012.
    arXiv:1201.6306.

  • Hubie Chen and Moritz Müller. 
    An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction.
    Logical Methods in Computer Science, Volume 9 (1:15), 2013.
    Conference version appeared in: Twenty-Seventh Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2012, Dubrovnik, Croatia. 
    arXiv:1207.6696.

  • Simone Bova, Hubie Chen, and Matt Valeriote.
    Generic Expression Hardness Results for Primitive Positive Formula Comparison.
    Information and Computation (invited; ICALP '11 special issue).
    Conference version appeared in: 38th International Colloquium on Automata, Languages and Programming (ICALP), 2011, Zürich, Switzerland.
    arXiv:1205.5745

Other publications

Talks

Meditations on Quantified Constraint Satisfaction, Dagstuhl '12 version.

Miscellaneous