Papers of Yijia Chen

A parameterized halting problem, Δ₀ truth and the MRDP theorem (with Moritz Müller and Keita Yokoyama).
Preprint, 2022.

A surprising relationship between descriptive complexity and proof complexity (with Jörg Flum and Moritz Müller).
In the logic in computer science column by Yuri Gurevich,
Bulletin of the EATCS, No. 138, October, 2022.

On algorithms based on finitely many homomorphism counts (with Jörg Flum, Mingjun Liu, Zhiyang Xun).
Conference version appeared in Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS'22), 32:1-32:15, 2022.

Forbidden induced subgraphs and the Łoś-Tarski theorem (with Jörg Flum).
Conference version appeared in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'21), 2021.

Parameterized parallel computing and first-order logic (with Jörg Flum).
In Fields of Logic and Computation III - Essays Dedicated to Yuri Gurevich on the Occasion of His 80th Birthday,
Lecture Notes in Computer Science 12180, pp. 57-78, 2020.

FO-definability of shrub-depth (with Jörg Flum).
Conference version appeared in Proceedings of the 28th EACSL Annual Conference on Computer Science Logic (CSL'20), 15:1-15:16, 2020.

The parameterized space complexity of model-checking bounded variable first-order logic (with Michael Elberfeld, and Moritz Müller).
Logical Methods in Computer Science, 15(3): 31:1-31:29, 2019.

The complexity of homomorphism indistinguishability (with Jan Böker, Martin Grohe, and Gaurav Rattan).
Conference version appeared in Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS'19), 54:1-54:13, 2019.

The constant inapproximability of the parameterized dominating set problem (with Bingkai Lin).
SIAM Journal on Computing, 48(2): 513-533, 2019.
Conference version appeared in Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS'16), 505-514, 2016.

Some lower bounds in parameterized AC⁰ (with Jörg Flum).
Information and Computation, 267, 116-134, 2019.
Conference version appeared in Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS'16), 27:1-27:14, 2016.

A parameterized halting problem, the linear time hierarchy, and the MRDP theorem (with Moritz Müller and Keita Yokoyama).
Conference version appeared in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'18), pp. 235-244, 2018.

Tree-depth, quantifier elimination, and quantifier rank (with Jörg Flum).
Conference version appeared in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'18), pp. , 225-234, 2018.

The complexity of limited belief reasoning - the quantifier-free case (with Abdallah Saffidine and Christoph Schwering).
Conference version appeared in Proceedings of the 27th International Joint Conference on Artificial Intelligence(IJCAI'18), pp. 1774-1780, 2018.

Slicewise definability in first-order logic with bounded quantifier rank (with Jörg Flum and Xuangui Huang).
Conference version appeared in Proceedings of the 26th EACSL Annual Conference on Computer Science Logic (CSL'17), 19:1-19:16, 2017.

The hardness of embedding grids and walls (with Martin Grohe and Bingkai Lin).
Conference version appeared in Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'17),
Lecture Notes in Computer Science 10520, pp. 180-192, 2017.

The parameterized complexity of k-edge induced subgraphs (with Bingkai Lin).
Information and Computation, 252, 138-160, 2017.
Conference version appeared in Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP'12, Track A),
Lecture Notes in Computer Science 7391, pp. 641-652, 2012.

The Ehrenfeucht-Fraïssé method and the planted clique conjecture (with Jörg Flum).
In Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday,
Lecture Notes in Computer Science 9300, pp. 87-108, 2015.

Counting problems in parameterized complexity (with Chihao Zhang).
Tsinghua Science and Technology, 19 (04), 410-420, 2014.

Bounded variable logic, parameterized logarithmic space, and Savitch's theorem (with Moritz Müller).
Conference version appeared in Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS'14),
Lecture Notes in Computer Science 8634, pp.183-195, 2014.

Hard instances of algorithms and proof systems (with Jörg Flum and Moritz Müller).
ACM Transactions on Computation Theory , 6(2), article 7, 2014.
Conference version appeared in Proceedings of the 8th Computability in Europe, Mathematical Theory and Computational Practice (CiE'12),
Lecture Notes in Computer Science 7318, pp. 118-128, 2012.
Electronic Colloquium on Computational Complexity, Report TR11-085, 2011.

On optimal inverters (with Jörg Flum).
The Bulletin of Symbolic Logic, 20 (01), 1-23, 2014.

Consistency, optimality, and incompleteness (with Jörg Flum and Moritz Müller).
Annals of Pure and Applied Logic, 164(12), 1224-1235, 2013.
Conference version appeared in Proceedings of the 7th Computability in Europe, Mathematical Theory and Computational Practice (CiE'11),
Lecture Notes in Computer Science 6735, pp. 61-70, 2011.

On limitations of the Ehrenfeucht-Fraïssé-method in descriptive complexity (with Jörg Flum).
Electronic Colloquium on Computational Complexity, Report TR13-065, 2013.

The exponential time hypothesis and the parameterized clique problem (with Jörg Flum and Kord Eickmeyer).
Conference version appeared in Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC'12),
Lecture Notes in Computer Science 7535, pp.13-24, 2012.

From almost optimal algorithms to logics for complexity classes via listings and a halting problem (with Jörg Flum).
Journal of the ACM, 59(4), article 17, 2012.

On the ordered conjecture (with Jörg Flum).
Conference version appeared in Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science (LICS'12), pp.225-234, 2012.

A parameterized halting problem (with Jörg Flum).
In the Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday,
Lecture Notes in Computer Science 7370, pp. 364-397, 2012.

Strong isomorphism reductions in complexity theory (with Sam Buss, Jörg Flum, Sy Friedman, and Moritz Müller).
The Journal of Symbolic Logic, 76(4): 1381-1402, 2011.

Listings and logics (with Jörg Flum).
Conference version appeared in Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS'11), pp.165-174, 2011.
Electronic Colloquium on Computational Complexity, Report TR11-020, 2011.

Lower bounds for kernelizations and other preprocessing procedures (with Jörg Flum and Moritz Müller).
Theory of Computing Systems, 48(4):803-839, 2011.
Conference version appeared in Proceedings of the 5th Computability in Europe, Mathematical Theory and Computational Practice (CiE'09),
Lecture Notes in Computer Science 5635, pp. 118-128, 2009.
Electronic Colloquium on Computational Complexity, Report TR07-137, 2007.

On slicewise monotone parameterized problems and optimal proof Systems for TAUT (with Jörg Flum).
Conference version appeared in Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL'10),
Lecture Notes in Computer Science 6247, pp. 200-214, 2010.

On p-optimal proof systems and logics for PTIME (with Jörg Flum).
Conference version appeared in Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP'10, Track B),
Lecture Notes in Computer Science 6199, pp. 321-332, 2010.
Electronic Colloquium on Computational Complexity, Report TR10-008, 2010.

On the complexity of Gödel's proof predicate (with Jörg Flum).
The Journal of Symbolic Logic, 75(1): 239-254, 2010.

A logic for PTIME and a parameterized halting problem (with Jörg Flum).
Conference version appeared in Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science (LICS'09), pp.397-406, 2009.
Electronic Colloquium on Computational Complexity, Report TR08-083, 2008.

Subexponential time and fixed-parameter tractability: exploiting the miniaturization mapping (with Jörg Flum).
Journal of Logic and Computation, 19(1):89-122, 2009.
Conference version appeared in Proceedings of the 21st International Workshop on Computer Science Logic (CSL'07),
Lecture Notes in Computer Science 4646, pp. 389-404, 2007.

Understanding the complexity of induced subgraph isomorphisms (with Marc Thurley and Mark Weyer).
Conference version appeared in Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08, Track A),
Lecture Notes in Computer Science 5125, pp.587-596,2008.
The slides of my FPT 2008 talk based on this paper.

The parameterized complexity of maximality and minimality problems (with Jörg Flum).
Annals of Pure and Applied Logic, 151(1), 22-61, 2008.
Conference version appeared in Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC'06),
Lecture Notes in Computer Science 4169, pp.25-37, 2006.

An isomorphism between subexponential and parameterized complexity theory (with Martin Grohe).
SIAM Journal on Computing, 37(4), 1228-1258, 2007.
A partial version appeared as Electronic Colloquium on Computational Complexity, Report TR06-011, 2006.
Conference version appeared in Proceedings of the 21st IEEE Conference on Computational Complexity (CCC'06), pp.314-328, 2006.

On parameterized approximability (with Martin Grohe and Magdalena Grüber).
Electronic Colloquium on Computational Complexity, Report TR07-106, 2007.
Conference version appeared in Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC'06),
Lecture Notes in Computer Science 4169, pp.109-120, 2006.

On parameterized path and chordless path problems (with Jörg Flum).
Conference version appeared in Proceedings of the 22nd IEEE Conference on Computational Complexity (CCC'07), pp. 250-263, 2007.

An analysis of the W*-hierarchy (with Jörg Flum and Martin Grohe).
The Journal of Symbolic Logic, 72(2), 513-534, 2007.

On miniaturized problems in parameterized complexity theory (with Jörg Flum).
Theoretical Computer Science, 351(3): 314-336, 2006.
Conference version appeared in Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC'04),
Lecture Notes in Computer Science 3162, pp.108-120, 2004.

Machine-based methods in parameterized complexity (with Jörg Flum and Martin Grohe).
Theoretical Computer Science, 339(2-3):167-199, 2005.

Machine characterizations of the classes of the W-hierarchy (with Jörg Flum).
Conference version appeared in Proceedings of the 17th International Workshop on Computer Science Logic (CSL'03),
Lecture Notes in Computer Science 2803, pp. 114-127, 2003.

Bounded nondeterminism and alternation in parameterized complexity theory (with Jörg Flum and Martin Grohe).
Conference version appeared in Proceedings of the 18th IEEE Conference on Computational Complexity (CCC'03), pp.13-29, 2003.

Capture complexity by partition (with Enshao Shen).
Conference version appeared in Proceedings of the 15th International Workshop on Computer Science Logic (CSL'01),
Lecture Notes in Computer Science 2142, pp. 84-98, 2001.

The downward transfer of elementary satisfiability of partition logics (with Enshao Shen).
Mathematical Logic Quarterly, 46(4):477-487, 2000.

Back

Yijia Chen, last modified: 14. 02. 2023