5 citations · 15 across the 10 of their papers we have counts for
11 papers
Some remarks on the uncolored versions of the original CFI-graphs
Yijia Chen, Jörg Flum, Mingjun Liu
The CFI-graphs, named after Cai, Fürer, and Immerman, are central to the study of the graph isomorphism testing and of first-order logic with counting. They are colored graphs, and…
Simple Combinatorial Construction of the -Lower Bound for Approximating the Parameterized -Clique
Yijia Chen, Yi Feng, Bundit Laekhanukit +1
In the parameterized -clique problem, or -Clique for short, we are given a graph and a parameter . The goal is to decide whether there exist vertices in t…
On Algorithms Based on Finitely Many Homomorphism Counts
Yijia Chen, Jörg Flum, Mingjun Liu +1
It is well known [Lovász, 67] that up to isomorphism a graph~ is determined by the homomorphism counts , i.e., the number of homomorphisms from to , where …
Game-theoretic analysis of Guts Poker
Luca Castornova, Yijia Chen, Kevin Zumbrun
We carry out a game-theoretic analysis of the recursive game "Guts," a variant of poker featuring repeated play with possibly growing stakes. An interesting aspect of such games is…
The Complexity of Limited Belief Reasoning -- The Quantifier-Free Case
Yijia Chen, Abdallah Saffidine, Christoph Schwering
The classical view of epistemic logic is that an agent knows all the logical consequences of their knowledge base. This assumption of logical omniscience is often unrealistic and m…
Slicewise definability in first-order logic with bounded quantifier rank
Yijia Chen, Joerg Flum, Xuangui Huang
For every let denote the class of sentences of first-order logic FO of quantifier rank at most . If a graph property can be defined in $\textrm{…
The Hardness of Embedding Grids and Walls
Yijia Chen, Martin Grohe, Bingkai Lin
The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graph from some class of "pattern graphs" can be embedd…
The parameterized space complexity of model-checking bounded variable first-order logic
Yijia Chen, Michael Elberfeld, Moritz Müller
The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational stru…
Some lower bounds in parameterized
Yijia Chen, Joerg Flum
We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical . Among others, we derive such a lower bound for al…
The Constant Inapproximability of the Parameterized Dominating Set Problem
Yijia Chen, Bingkai Lin
We prove that there is no fpt-algorithm that can approximate the dominating set problem with any constant ratio, unless FPT= W[1]. Our hardness reduction is built on the second aut…
The parameterized complexity of k-edge induced subgraphs
Bingkai Lin, Yijia Chen
We prove that finding a -edge induced subgraph is fixed-parameter tractable, thereby answering an open problem of Leizhen Cai. Our algorithm is based on several combinatorial ob…