Home » forums » LtU Forum

Open problems in category theory and computing science

I am a graduate student that is interested in logic and theoretical computer science. I have a pretty good background in modern algebra, as well as a beginning background in logic, category theory, and algebraic topology. I am looking to apply these things to problems in computing science for a master's thesis.

In short, I'm looking for open problems that would be amenable for the level of master's work. I've been studying these topics on my own, with the aid of excellent books, but it would be good to have something to focus on "getting to", I suppose.

By Dustin Mulcahey at 2005-03-04 19:29 | LtU Forum | previous forum topic | next forum topic | other blogs | 10191 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

About open problems

As a reason why you might get an underwhelming response to your appeal, it's not so easy for outsiders to obtain lists of good, solvable, open problems, since these are jealously guarded hints about how best to go about one's own research. Luca Aceto wrote about this in his process algebra diary: On the Dissemination of Open Problems.

A good reason to publish open problems (and Luca has done so with his open problems in process algebra page), is to try and grow a research area. My colleague, Alessio Guglielmi, put up a list of open problems in deep inference and the calculus of structures: if you are interested in proof theory, then there are some topics applying algebra and category theory you might be interested in. Contact me if you are interested in finding out more.

By Charles A Stewart at Wed, 2005-03-09 00:57 | login or register to post comments

Compared to open programs

I always have a lot more ideas for programs than time to write them, but I try to keep quiet about them anyway. That's because it's more fun to show off an idea and its implementation at the same time. If you let the idea out by itself then the would-be program loses hack value and in consequence it might not actually get written.

I'm not terribly good at keeping quiet about ideas yet, but these days when I say "I'm going to wite a program that ..." then a little voice in my head says "Luke, you will never write that program." This is sad because I've talked about a lot of programs that I'd really like to have written. Tough lesson: Hack first and talk later!

My only comment on Dustin's question is that there's no shortage of interesting problems in the related field of random hacking.

By Luke Gorrie at Wed, 2005-03-09 13:16 | login or register to post comments

Thanks

Thanks, these pages are very helpful.

I don't know whether or not I will actually be doing a Master's thesis in computing science, as my future is still up in the air (dependant on acceptance/rejection letters in the mail). I am in a BS/MS program in CS (that I am trying to flee to do grad work in logic), and if all else fails, I want to do a thesis related to what I am interested in. The school that I attend does not do much in this area, and it is probably not the best of ideas to deviate completely from the department's strong areas.

Still, I want to see what is reachable from where I am, and perhaps start to pick at some problems over the summer. If anything, I'll get a good idea of exactly where I stand, approximately where I need to get to, and whether or not it is all feasible.

This is all contingent, which makes it rather frustrating. However, thank you again for the resources and insight.

By Dustin Mulcahey at Wed, 2005-03-09 16:25 | login or register to post comments

I don't know if I fully agree

I don't know if I fully agree with that. When I was an outsider, I found that people were usually pretty happy to talk to me when I emailed them. They were sometimes surprised that a random programmer was interested in their ideas, but always in a happy way.

However, I think that what a "solvable open problem" is also depends on the people you are around, and can have conversations with. Now that I'm a grad student, I can approach much hairier problems with confidence because I can talk to people who can point out flaws in my thinking and suggest alternatives when I get stuck.

I have trouble thinking of a good problem to suggest, because I don't know who Dustin has to talk with! For example, I'd suggest looking into looking at the categorical semantics of equational logic, and a) finding proof terms for them, and b) adding an equational logic to a lambda calculus/CCC. But this makes sense only if he has someone he can talk categorical logic with.

By neelk at Wed, 2005-03-09 20:08 | login or register to post comments

Researchers

You need to narrow your field of interest before you pick a problem. Once you get interested in something, you will become aware of the open problems. I don't think good work results from simply "letting students loose" in problem domains they aren't familiar with and interested in already.

That said, you might look through the work of (and eventually contact) the following researchers, who are active in applying category theory and proof theory to PLT: Neil Ghani, Thorsten Altenkirch, Peter Dybjer, Marcelo Fiore, Eike Ritter and David Naumann.

By Frank Atanassow at Wed, 2005-03-09 13:45 | login or register to post comments