I have tried to keep politics out of this weblog with the exception of issues related to science, in particular science funding and immigration. To celebrate...
105
Lance Fortnow
fortnow
Oct 3, 2003 1:53 pm
The Nobel science prizes will be awarded next week: Medicine on Monday, Physics on Tuesday and Chemistry and Economics on Wednesday. Nothing against the Turing...
106
Lance Fortnow
fortnow
Oct 5, 2003 12:58 pm
While on the topic of awards, we have a new "genius" in the theoretical computer science community. Computational geometer Erik Demaine just received a...
107
Lance Fortnow
fortnow
Oct 8, 2003 2:38 pm
Next week is the 44th FOCS Conference in Boston. FOCS, the Symposium on the Foundations of Computer Science is, with STOC, one of the two major American ...
108
Lance Fortnow
fortnow
Oct 10, 2003 1:45 pm
With FOCS starting this weekend, here is some advice for students attending a conference. What is the purpose of a conference? Disseminating information is the...
109
Lance Fortnow
fortnow
Oct 13, 2003 1:46 pm
Today is Columbus Day, a minor holiday in the states. There is a great saying about Columbus: He is not famous for being the first person to discover America,...
110
Lance Fortnow
fortnow
Oct 15, 2003 8:24 pm
Just prior to the FOCS conference, Avrim Blum gave a tutorial on machine learning and Dana Randall gave a tutorial on mixing. As the talks were computerized,...
111
Lance Fortnow
fortnow
Oct 16, 2003 1:58 pm
This is for my friends in Boston who suggested I do a sports post. One of the great parts of my job is working with people from around the world. I was working...
112
Lance Fortnow
fortnow
Oct 17, 2003 2:45 pm
There are two computer science departments on the University of Chicago campus. The one I belong to, a department in the physical sciences division of the...
113
Lance Fortnow
fortnow
Oct 20, 2003 11:45 pm
There is a big reorganization in the CISE directorate of NSF. To understand what's happening, let's review the previous structure.. The National Science...
114
Lance Fortnow
fortnow
Oct 22, 2003 3:36 pm
How has the internet most affected the study of science? In one word: communication: the ability for scientists to discuss and share their research with each...
115
Lance Fortnow
fortnow
Oct 24, 2003 2:01 pm
Here is one of my favorite examples of a bad proof for what turns out to be a correct theorem. Theorem: If NP is in BPP then the whole polynomial-time ...
116
Lance Fortnow
fortnow
Oct 27, 2003 3:14 pm
A quantum computing graduate student sent me email over the weekend. He had thought he had proven some surprising results about the class PP and was wondering...
117
Lance Fortnow
fortnow
Oct 29, 2003 3:29 pm
Let f be a function that maps n to n . Let U represent the uniform distribution on n and D be the distribution that one gets by applying f to a string drawn...
118
Lance Fortnow
fortnow
Oct 31, 2003 3:16 pm
Last week I started an experiment using instant messaging. I thank the many of you who sent me IMs, a great way for me to meet you, the readers of this weblog....
119
Lance Fortnow
fortnow
Nov 3, 2003 3:06 pm
The NEC Research Institute (NECI) died just over a year ago. I didn't feel comfortable talking about it then so let me say a few words now. I joined NECI in...
120
Lance Fortnow
fortnow
Nov 5, 2003 3:23 pm
This week I started teaching the PCP theorem: Every language in NP has a proof that can be probabilistically checked with only O(log n) random coins and a...
121
Lance Fortnow
fortnow
Nov 7, 2003 4:33 pm
I received the following email from David Molnar, a Berkeley graduate student. He asks some interesting questions about the use of the web and research....
122
Lance Fortnow
fortnow
Nov 10, 2003 2:03 am
The Computer and Information Science and Engineering Directorate of the NSF has completed it reorganization. The CISE web site details the new structure. CISE...
123
Lance Fortnow
fortnow
Nov 11, 2003 1:08 pm
It happened right after I started high school in suburban New Jersey, the start of the Science Times section in Tuesday's New York Times. The Science Times not...
124
Lance Fortnow
fortnow
Nov 12, 2003 10:02 pm
[I will do this just once. Feel free to use the comments link to mention your own institution.] We are seeking theory graduate students and faculty (all ranks)...
125
Lance Fortnow
fortnow
Nov 14, 2003 3:18 pm
Here's a problem from Janos Simon. For a set A, let L(A)={x | for some m0, x m is in A} Simon asked, as a homework problem, to show that if A is regular then ...
126
Lance Fortnow
fortnow
Nov 17, 2003 3:31 pm
Back in my science-fiction reading days, I particularly remember one editorial written in one of those anthology magazines about 1980: In the near future, you...
127
Lance Fortnow
fortnow
Nov 19, 2003 3:03 pm
Over the years a number of localized theory workshops have developed which bring together researchers from around the area to mingle and learn about some of...
128
Lance Fortnow
fortnow
Nov 21, 2003 2:44 pm
I thought I should mention some of my favorite and most frustrating open questions over the years. Here's one of them: Let f:{0,1} n {0,1}. Let h and g be...
129
Lance Fortnow
fortnow
Nov 24, 2003 3:50 pm
XML (eXtensible Markup Language) has become quite a popular data format in recent years. XML roughly corresponds to a tree. For example, ...
130
Lance Fortnow
fortnow
Nov 26, 2003 2:57 pm
In the left column of this weblog's homepage, I've added a new "weblogs" section to list the academic weblogs that I have been following. Not very long right...
131
Lance Fortnow
fortnow
Dec 1, 2003 2:49 pm
I hope you all got your Complexity submissions in on time last week. Now let the rest of the world see your work. Make them into technical reports, put them on...
132
Lance Fortnow
fortnow
Dec 2, 2003 12:28 pm
First an update on NSF program solicitations: The Formal and Mathematical Foundations cluster has posted its solicitation which includes computational...
133
Lance Fortnow
fortnow
Dec 3, 2003 3:24 pm
The Cornell University Library has announced it will drop a substantial number of their Elsevier subscriptions, part of a general problem Cornell and other...
