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...
145
Lance Fortnow
fortnow
Jan 5, 2004 10:17 pm
Peter Freeman, Assistant Director of NSF for CISE, has an " important message " on the recent reorganization. Good to see he's finally acknowledging the...
146
Lance Fortnow
fortnow
Jan 6, 2004 9:17 pm
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...
147
Lance Fortnow
fortnow
Jan 7, 2004 3:22 pm
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...
148
Lance Fortnow
fortnow
Jan 7, 2004 9:39 pm
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...
149
Lance Fortnow
fortnow
Jan 9, 2004 4:00 pm
Some interesting science policy quotes courtesy of the American Institute of Physics. Where have the Americans gone? - DOE Office of Science Director Ray...
150
Lance Fortnow
fortnow
Jan 9, 2004 5:28 pm
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...
151
Lance Fortnow
fortnow
Jan 10, 2004 12:07 am
For various reasons, the posts made by Scott Aaronson are not getting posted to this list. To see them you'll have to go to the weblog main page: ...
152
Lance Fortnow
fortnow
Jan 20, 2004 2:49 am
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...
153
Lance Fortnow
fortnow
Jan 21, 2004 4:03 pm
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...
154
Lance Fortnow
fortnow
Jan 22, 2004 2:06 pm
[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 ...
155
Lance Fortnow
fortnow
Jan 23, 2004 3:18 pm
[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 ...
156
Lance Fortnow
fortnow
Jan 23, 2004 3:18 pm
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...
157
Lance Fortnow
fortnow
Jan 23, 2004 3:56 pm
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...
158
Lance Fortnow
fortnow
Jan 24, 2004 12:53 pm
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...
159
Lance Fortnow
fortnow
Jan 26, 2004 5:26 pm
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...
160
Lance Fortnow
fortnow
Jan 28, 2004 8:54 am
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...
161
Lance Fortnow
fortnow
Jan 30, 2004 10:14 am
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...
162
Lance Fortnow
fortnow
Jan 30, 2004 1:32 pm
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...
163
Lance Fortnow
fortnow
Feb 2, 2004 4:48 pm
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...
164
Lance Fortnow
fortnow
Feb 3, 2004 1:01 pm
An interesting NSF press release describes the importance of the layout of offices to the productivity of a research group: Clustering items like refrigerator,...
165
Lance Fortnow
fortnow
Feb 3, 2004 1:03 pm
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...
166
Lance Fortnow
fortnow
Feb 4, 2004 11:44 am
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...
167
Lance Fortnow
fortnow
Feb 4, 2004 11:45 am
An interesting NSF press release describes the importance of the layout of offices to the productivity of a research group: Clustering items like refrigerator,...
168
Lance Fortnow
fortnow
Feb 7, 2004 12:48 pm
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...
169
Lance Fortnow
fortnow
Feb 7, 2004 12:49 pm
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...
170
Lance Fortnow
fortnow
Feb 9, 2004 2:58 pm
"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...
171
Lance Fortnow
fortnow
Feb 9, 2004 10:08 pm
"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...
172
Lance Fortnow
fortnow
Feb 11, 2004 1:07 am
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...
173
Lance Fortnow
fortnow
Feb 12, 2004 11:26 pm
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...
