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...
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...
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...
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...
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. -- ...
(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...
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...
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...
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...
(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)...
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...
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...
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...
(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...
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...
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...
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...
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...
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...
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...
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,...
The great logician Stephen Kleene was born one hundred years ago today in Hartford, Connecticut. No single person affected a typical introductory theoretical...
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...
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...
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...
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...
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...
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?...
- 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...
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...
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.
