In December of 1994 I presented My Favorite Ten Complexity Theorems of the Past Decade , a paper where I chose ten theorems representing different areas in...
Peter Freeman, Assistant Director of NSF for CISE, has an " important message " on the recent reorganization. Good to see he's finally acknowledging the...
The October 2003 BEATCS has two articles discussing the Church-Turing thesis, Beyond Turing Machines by Eugene Eberbach and Peter Wegner (I can't find this...
I grew up as an information hound. Lacking the internet in my high school days I would often hang out in the library looking things up. One day I found a...
I posted the latest BEATCS Complexity Column, A Survey on Private Information Retrieval by Bill Gasarch. With this article I am retiring as editor of the...
Some interesting science policy quotes courtesy of the American Institute of Physics. Where have the Americans gone? - DOE Office of Science Director Ray...
I off on vacation next week and you will have a guest weblogger, Scott Aaronson, while I am gone. I have confidence Scott will keep you all entertained and...
Thanks to Scott Aaronson for covering for me last week. If you've enjoyed the last week, check out more of his writings . Maybe the weblog bug has bit him and...
On my vacation I read Dan Brown's The Da Vinci Code , a very popular book I received recently as a gift. Warning: Minor spoilers follow. I always enjoy a novel...
[From Chris Fuchs] Dear friends in the quantum information and foundations communities, Many of you may not know it, but the concept of a generalized quantum ...
[From Chris Fuchs] Dear friends in the quantum information and foundations communities, Many of you may not know it, but the concept of a generalized quantum ...
You've taken your classes, passed your preliminary/qualifying exams, done your research and written your thesis. What stands between you and the Ph.D.--the...
A couple of quick notes. The list of accepted papers for the upcoming STOC conference has been posted. The most intriguing looking paper in complexity is...
A couple of quick notes. The list of accepted papers for the upcoming STOC conference has been posted. The most intriguing looking paper in complexity is...
I have returned to Amsterdam for the week. I did my sabbatical in Amsterdam seven years ago and I always enjoy the visit. Yesterday I saw the soccer team...
Hein Rhrig successfully defended his Ph.D. thesis at the University of Amsterdam yesterday. The Dutch thesis defense reminds me most of a traditional American...
Here's a simple result I have seen several times recently, a bit surprising when you first see it. Theorem: co-NEXP is in NEXP/poly. NEXP are the languages...
Here's a simple result I have seen several times recently, a bit surprising when you first see it. Theorem: co-NEXP is in NEXP/poly. NEXP are the languages...
Dear friends and colleagues, We would like to encourage you to submit suitable papers to the journal Computational Complexity (cc). We believe that cc should...
An interesting NSF press release describes the importance of the layout of offices to the productivity of a research group: Clustering items like refrigerator,...
Dear friends and colleagues, We would like to encourage you to submit suitable papers to the journal Computational Complexity (cc). We believe that cc should...
Editor's Note: I don't plan to be an announcement server but this theory day deserves some extra publicity. Despite the self-aggrandizing it looks like quite...
An interesting NSF press release describes the importance of the layout of offices to the productivity of a research group: Clustering items like refrigerator,...
Editor's Note: I don't plan to be an announcement server but this theory day deserves some extra publicity. Despite the self-aggrandizing it looks like quite...
I spent a considerable part of yesterday looking at applications for our Ph.D. program in theoretical computer science. Some of you readers might have an...
"I like everybody in this field" Berkeley professor Christos Papadimitriou said during his acceptance speech of the Knuth Award at the 2002 STOC conference. He...
"I like everybody in this field" Berkeley professor Christos Papadimitriou said during his acceptance speech of the Knuth Award at the 2002 STOC conference. He...
Let's look at some interesting questions about the set of smallest programs. This post relates more to recursion theory than complexity theory. No time bounds...
Michael Nielsen has a post linking to a post linking to a post noting that the editorial board of the Journal of Algorithms (published by Elsevier) resigned en...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
