Some sad news, complexity theorist Ingo Wegener passed away last Wednesday at the age of 57. We will have a proper obituary soon. My last post LINK asked a...
1223
Lance
fortnow
Dec 2, 2008 12:43 pm
I often get asked various questions about complexity but I now had the same question asked twenty years apart. Are there natural problems in BPP not known to...
1224
GASARCH
wgasarch
Dec 3, 2008 4:49 pm
When the term quantum is used in English it often means large as in the TV show Quantum Leap. The recent James Bond Movie Quantum of Solace seems to use the...
1225
Lance
fortnow
Dec 4, 2008 12:24 pm
Helger Lipmaa points to Justin Beldin's essay on the epistemology of Interactive/Zero-Knowledge proofs and asks my opinion on the general topic. Reminds me of...
1226
Lance
fortnow
Dec 5, 2008 12:14 pm
The Army has a new video The Science of Victory (via the CRA Blog). An impressive argument for basic research though a bit heavy on the scare tactics. -- ...
1227
GASARCH
wgasarch
Dec 8, 2008 3:47 pm
(Guest Post from Anna Gilbert from Univ of Wisconsin. Its actually a pointer to a job posting in theory!) We have an opening for a postdoctoral fellow in...
1228
Lance
fortnow
Dec 9, 2008 12:40 pm
Philipp Woelfel remembers his advisor. "Doktorvater" (doctor father) is the unofficial German term for PhD adviser – from my perspective, I can't think of a...
1229
GASARCH
wgasarch
Dec 10, 2008 3:33 pm
REPORT AND REFLECT ON IBM/NYU/Columbia THEORY DAY Most years in the FALL there is a THEORY DAY at NYU and in the SPRING there is a THEORY DAY at Columbia. They...
1230
Lance
fortnow
Dec 11, 2008 12:29 pm
Bill's post Monday of a Michigan post-doc position garnished quite a few comments, generated by legitimate worries about the academic job market. 1992 was the...
1231
GASARCH
wgasarch
Dec 12, 2008 4:31 pm
(Guest post from Richard Beigel, NSF Program Director for Algorithmic Foundations) In order that proposals from CDI PIs (See below for what the CDI grants are)...
1232
GASARCH
wgasarch
Dec 15, 2008 5:30 pm
I made up the following problem which was on the Univ of MD Math Competition for HS Students Part II. (It was question 3 of 5, indicating intermediary...
1233
GASARCH
wgasarch
Dec 15, 2008 5:30 pm
I made up the following problem which was on the Univ of MD Math Competition for HS Students Part II. (It was question 3 of 5, indicating intermediary...
1234
Lance
fortnow
Dec 16, 2008 2:09 pm
Yesterday the Electoral College delegates voted, 365 for Barack Obama and 173 for John McCain. How did the markets do? To compare, here is my map the night...
1235
GASARCH
wgasarch
Dec 17, 2008 4:44 pm
(Guest Post by Amir Michail) The case for teaching everyone programming If everyone could program, then anyone could more easily and cheaply scale his/her...
1236
Lance
fortnow
Dec 18, 2008 12:27 pm
The amount of spam in my spam folder has dropped below fifty per day down from several hundred a few months ago. The amount of spam that gets through Gmail's...
1237
GASARCH
wgasarch
Dec 19, 2008 12:53 pm
This post was inspired by HALF of the movie FLIGHTPLAN. I have watched HALF of the movie FLIGHTPLAN. In the movie Kyle Pratt (played by Jodie Foster- I didn't...
1238
Lance
fortnow
Dec 22, 2008 7:15 pm
From the Ethicist in yesterday's New York Times Magazine. Another college professor and I wanted a student to work on a project of ours, but she is a Mac user...
1239
Lance
fortnow
Dec 23, 2008 1:02 pm
First some administrative stuff. Posting will be light until the New Years. The comments feed is not working properly—Blogger is working on it. I deleted a...
1240
Lance
fortnow
Dec 24, 2008 1:53 pm
My daughters came up with the following joke. Two roosters sat on on a barn. The first rooster asked the second what time he was supposed to crow. The second...
1241
Lance
fortnow
Dec 31, 2008 1:24 pm
Paper of the year goes to Optimal algorithms and inapproximability results for every CSP? by U. Washington grad student Prasad Raghavendra. The paper gives a...
1242
Lance
fortnow
Jan 2, 2009 3:05 pm
Every voting scheme has the property that in some scenario a change of a single vote can change the outcome. When a major election has a very close result,...
1243
Lance
fortnow
Jan 5, 2009 2:23 pm
The great logician Stephen Kleene was born one hundred years ago today in Hartford, Connecticut. No single person affected a typical introductory theoretical...
1244
GASARCH
wgasarch
Jan 6, 2009 6:52 pm
I just got back from SODA 2009 in New York (Symposium on Discrete Algorithms). In later posts I will describe some of the interesting papers that I saw, Today...
1245
Lance
fortnow
Jan 7, 2009 12:43 pm
There have been 23 IEEE Conferences on Computational Complexity and I have been to all of them. There have been 20 ACM-SIAM Symposiums on Discrete Algorithms...
1246
GASARCH
wgasarch
Jan 8, 2009 4:13 pm
I liked the SODA2009 paper Sorting and Selection in Posets since it makes you look at ordinary sorting in a new way. What does it mean to sort a list? We...
1247
Lance
fortnow
Jan 9, 2009 12:29 pm
Samir Khuller guest posts about having conferences in exotic locations. During the SODA Business Meeting I was a bit alarmed at some of the suggestions made...
1248
GASARCH
wgasarch
Jan 12, 2009 3:50 pm
When you first make a conjecture you don't know if it will be important or interesting or both or neither. In the case below it was solved quickly, the answer...
1249
Lance
fortnow
Jan 13, 2009 4:57 pm
Nicole Immorlica pointed me to a Wall Street Journal article about a ranking of 200 jobs by CareerCast. Number one: Mathematician. So what is a mathematician?...
1250
Lance
fortnow
Jan 14, 2009 12:13 pm
- You are wrong. Figure it out. Sometimes you can still salvage something interesting out of your flawed proof. - You believe the proof is correct. Your belief...
1251
GASARCH
wgasarch
Jan 15, 2009 7:00 pm
Amitabh Varshney (Graphics Faculty at UMCP) emailing me the following: Someone told me a while ago that there are some theory conferences in which members of...
