Wei-Lin Wu's Homepage

Ph.D. 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 are my resume and LinkedIn profile for your reference. I'm very fortunate to have Professor Phokion G. Kolaitis as my advisor.


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.

Research

I'm generally interested in theoretical computer science including algorithm design, theory of formal languages, computability theory, computational complexity, graph theory and database theory. I have particular attention to the following fields:

My research results mainly involve combinatorial techniques. Check out this video for a brief explanation of my study.

Many years ago, 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 fact, (theoretical) computer science grew out of mathematical logic as a spin-off in a quest for a solution to the foundational crisis of mathematics.

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 topics: 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:

Past Education

Hobbies

Hiking, biking, swimming, photography, language learning (human languages or programming languages), linguistics, etymology.