Papers of Yijia Chen


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-1400, 2011. (pdf)

Consistency and optimality (with Jörg Flum and Moritz Müller).
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.(pdf)

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.(pdf)

Hard instances of algorithms and proof systems (with Jörg Flum and Moritz Müller).
Electronic Colloquium on Computational Complexity, Report TR11-085, 2011.(pdf)

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. (pdf)
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).
In Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL'10), Lecture Notes in Computer Science 6247, pp. 200-214, 2010.(pdf)

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.(pdf)

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

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. (pdf)

Subexponential time and fixed-parameter tractability: exploiting the miniaturization mapping (with Jörg Flum).
Journal of Logic and Computation, 19(1):89-122, 2009. (pdf)
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.

Understand 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. (pdf)
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. (pdf)
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. (pdf)
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. (pdf)
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. (pdf)

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

On miniaturized problems in parameterized complexity theory (with Jörg Flum).
Theoretical Computer Science, 351(3): 314-336, 2006. (pdf)
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. (pdf)

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. (pdf)

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. (pdf)

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. (pdf)

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

Back

Yijia Chen, last modified: 09. 11. 2011