Wei-Lin Wu's Homepage

Ph.D candidate in Computer Science at University of California Santa Cruz

Wir müssen wissen, wir werden wissen.   (English translation: We must know, we will know.)   This is a quote from the great mathematician David Hilbert.

I'm from Tainan, Taiwan. Here's my resume for your reference. I'm very honored to be advised by Professor Phokion G. Kolaitis.


Research

I'm generally interested in theoretical computer science including the study of algorithms and computational models, and I have particular attention to:

I taught myself mathematical logic using the excellent textbook Mathematical Logic, 2nd edition by H.-D. Ebbinghaus, J. Flum and W. Thomas. The specific results that brought me to this area are the famous Gödel's Incompleteness Theorems, which assert that any axiomatization of first-order arithemtics (involving +, ×, 0, 1) that is consistent, decidable and allows every computable function ƒ over the set N of natural numbers to be represented by a first-order formula δƒ must be incomplete (first incompleteness), i.e., there is a statement true of N yet unprovable in that axiomatization, and that the consistency of such an axiomatization - when formalized as a first-order sentence - is an instance of such a statement if the axiomatization subsumes first-order Peano arithmetics (second incompleteness). The first incompleteness is closely related to the undecidable Halting Problem.

In recent years, I have developed interests in finite model theory, a field in the research of logic in computer science where the themes include

I study finite model theory in connection to the expressive power of homomorphism counts. It is known that a relational structure can be characterized up to isomorphism by homomorphism counts. More precisely, given two relational structures A and B, they are isomorphic if and only if hom(C, A) = hom(C, B) for every relational structure C, where hom(C, A) denotes the number of homomorphisms from C to A (likewise for hom(C, B)). This result is known as Lovász's Theorem (by L. Lovász). A parallel result, due to S. Chaudhuri and M. Y. Vardi, says that A and B are isomorphic if and only if hom(A, C) = hom(B, C) for every relational structure C. These results have motivated the following directions: I'm active in the research of these topics, see the following publications section for more details. As for a reference textbook I highly recommend Graphs and Homomorphisms by P. Hell and J. Nešetřil.

References

[1] Yijia Chen, Jörg Flum, Mingjun Liu, and Zhiyang Xun. On algorithms based on finitely many homomorphism counts. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.

[2] Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets Weisfeiler and Leman. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 40:1-40:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.

Publications

Talks

Teaching Experiences

I have served as a teaching assistant for the courses offered at UC Santa Cruz:

Programming

Besides these, I use LaTeX on a daily basis for typesetting research documents, and Bash script and AppleScript (as well as Automator) occasionally for automating things. Yes, I'm a Mac user.

Past Education

Family, Lab Members and Friends