# Wei-Lin Wu's Homepage

### First-year Ph.D student in Computer Science, UCSC

Wir müssen wissen, wir werden wissen. (German for We must know, we will know. A quote from the great mathematician David Hilbert.)

I'm from Tainan City, Taiwan.

My Resume  ## Research Interests

Below are my interested areas:

• Mathematical logic, finite model theory
• Computation theory
• Design of algorithms
• Programming language theory

Quite a few years of my life have been devoted to the study of pure mathematics. I was particularly interested in the construction of number systems when I was a university student, fascinated by proofs and rational thinking. The essence of mathematical proofs, at least in my opinion, is the simple logic that even governs our rational thoughts. That's why I specialized in logic.

My interest in logic was even reinforced upon knowing the famous Gödel's Incompleteness Theorems, which say that any consistent axiomatization of arithemtics developed in the framework of first-order logic that includes Peano's arithmetics has an unprovable true statement and that an instance of this statement is, quite intriguingly, the consistency which asserts the whole system of (first-order) arithmetic itself contains no contradiction. (For a more detailed description, see Wikipedia.) The theorems are often regarded as a definitive refutation to Hilbert's Program.

What's even more interesting is that the theorems are closely related to the well-known Undecidability of the Halting Problem in computation theory. This shouldn't be so surprising as, from the hindsight, the concept of a (formal) mathematical proof is essentially that of a computation/program, which is manifested in that the technique of encoding as natural numbers (a technique known as Gödel numbering) is utilized in both Gödel's results (proofs as numbers) and the undecidability of the Halting Problem (programs as numbers).

In fact, the idea of identifying programs as proofs is formulated as Curry-Howard Isomorphism, the fundamental of the area Automated Theorem-Proving. An implementation for this is the functional programming language, Agda.

On the other hand, the study of mathematical logic is traditionally divided into 4 subfields, Proof Theory, Model Theory, Computability Theory (also termed Recursion Theory) and Set Theory. While model theory is concerned with all mathematical structures in general (and infinite structures in particular), a specialized area Finite Model Theory is limited to the investigation of finite structures and thus has many applications in the research of Theoretical Computer Science, Database Theory and Combinatorics.

There have been a wide range of open problems in finite model theory, and I'm particularly interested in the so-called Dichotomy Conjecture (assuming PNP):

For every relational structure B, CSP(B) is either in P or NP-complete,

where the computational problem CSP(B) --- CSP stands for non-uniform constraint satisfaction problem --- in which B is a fixed relational structure (a structure where only relations are concerned and there are no designated constants or functions) asks whether, given a relational structure A as input, there is homomorphism between A and B.

So far, only some special cases of this conjecture have been settled. I hope that, under the guidance of my advisor, Professor Phokion Kolaitis, I can make some satisfying contributions to the solution of the conjecture.

Articles and papers concerning finite model theory can be found at LICS Conference (ACM/IEEE Symposium on Logic in Computer Science).

## Skills

• Operating Systems: Mac OS X, Unix, Windows
• Languages: C/C++, Objective-C, Java, Haskell, Agda, LaTeX

## Education Record

• B.S., Electrical Engineering, National Cheng-Kung University, Taiwan (R.O.C)
• M.S., Computer Science and Information Engineering, National Taiwan University, Taiwan (R.O.C)

## Achievements

As mentioned above, I was specialized in the field of mathematical logic. The material I used to teach myself logic is the textbook Mathematical Logic, 2nd edition, by H.-D. Ebbinghaus, J. Flum and W. Thomas (see Amazon). I have attempted all exercises in this book and included the solutions as well as some notes and ideas in a PDF document. If you are also interested in this material or in my document, please send me an email. (This PDF document is going to be submitted to my GitHub, though.)

## Hobbies

I like biking and swimming for sports and listening to popular music to relax in my leisure time. I also love traveling during longer vacations. In addition to the US, I have been to Hong Kong and Japan. I'm particularly fascinated by Japanese culture, although regrettably I cannot speak Japanese. :-P      