Sunday, October 23, 2005

Some links of interests

I have just added some new links to several interesting blogs to my blogroll: David Molnar's blog, Kurt Van Etten's, and Scott Aaronson's (the complexity zoo keeper). It's great to see that the blogging community grows very well. This comes at one price however: there is just no time to visit regularly every single interesting blog there is. There are just too many good ones these days!

Also, I have recently discovered a nice-looking online textbook on 'universal algebra'. I haven't read it yet, though. But, it has some nice applications to computer science (automata theory, rewriting systems, etc.) and model theory. If you are a complexity theorist, a motivation to look at this book may be Straubing's monograph

Finite Automata, Formal Logic, and Circuit Complexity (Progress in Theoretical Computer Science), Springer, 1994.

In this monograph, Straubing demonstrates the possibility of attacking tantalizing open problems in circuit complexity using automata theory, semigroup theory, and finite model theory. In fact, I have heard a rumour that Straubing very recently proved a separation result in complexity theory using this technique ...

5 comments:

Anonymous said...

Visit? Regularly? That's what RSS aggregators are for.

anthonywlin said...

Awesome! Thanks for letting me know. [I am always behind when it comes to this sort of things :-)]

Anonymous said...

Thanks for adding me. Also thanks for the pointer to the Straubing article. Reminds me of a post I've had in the back of my head for a while...

Anonymous said...

Anthony, thanks for the link. This is a great blog you've got. If I had started reading this before beginning my own blog, it would have sped up my learning curve considerably. Somehow this never came up in any of my Google searches--I guess I always forgot to put "descriptive" in front of the word "complexity".

I've had a copy of Neil Immerman's Descriptive Complexity text on my bookshelf for a long time, but haven't had a chance to start digesting it yet. Maybe your blog will help motivate me and get me up to speed on the basics...

anthonywlin said...

Kurt: thanks for your kind words. I certainly hope that my blog will be helpful for people who are interested in logic and complexity, especially those wish to learn finite model theory and descriptive complexity.

Somehow this never came up in any of my Google searches

I don't know. Maybe because I have just recently started this blog ...