Computationalcomplexity - blog.computationalcomplexity.org - Computational Complexity
General Information:
Latest News:
What are Galois Games? 26 Aug 2013 | 06:07 pm
How are math concepts named? After the people who was involved with it. Examples: The Cook-Levin Theorem, Goldbach Conjecture, Ehrenfeucht-Fraisse games, Banach-Tarski Paradox. A descriptive name: ...
P = NP and the Weather 22 Aug 2013 | 05:13 pm
In the Beautiful World, my science fiction chapter of The Golden Ticket where P = NP in a strong way, I predicted that we could predict weather accurately enough to know whether it will rain about a y...
When Lance was 10 years old.. 19 Aug 2013 | 10:29 pm
In honor of Lance's 50th birthday I ask the following: When Lance was 10 years old which of the following were true? (Disclosure- some of the below are from a birthday card.) A REMOTE meant a seclud...
Flash Gordon 15 Aug 2013 | 05:06 pm
We watched the movie Ted last week but this post isn't about that movie. The movie has several references to the 1980 movie Flash Gordon including an extended cameo by Sam Jones who played Flash. Fla...
How much Trig does your governor know? 12 Aug 2013 | 06:17 pm
How much math should our public officials know? Basic probability and statistics so they can follow the arguments that their science advisers give them. And they should hire good objective science adv...
Don't Have an End Game 9 Aug 2013 | 06:52 pm
As a young professor, I wrote a grant proposal and took it to a senior theory professor for comments. He told me to take out the line "The ultimate goal of computational complexity is to settle the P ...
Longest time between posing a math problem and it being answered? 5 Aug 2013 | 08:15 pm
(We were asked to remind you: ITCS 2014 Call for papers: call for papers.) What problem in math had the longest time between POSING IT and SOLVING it? This might not be a well defined question since ...
Why is Multiplication Hard? 1 Aug 2013 | 10:45 pm
Quick. What is 879544 * 528045? Unless you used a calculator or was some sort of savant you it would take you a couple of minutes to figure out a solution. Of course a computer can calculate this very...
Certifying primality in a CONSTANT number of operations 29 Jul 2013 | 07:58 pm
For this post I will only count the operations PLUS, MINUS, MULT. They may be done on rather large numbers. Recall that from the work coming out of Hilberts 10th problem we know the following: For ev...
Ph.D. Attrition 26 Jul 2013 | 12:02 am
Leonard Cassuto writes in the Chronicle an article Ph.D. Attrition: How Much Is Too Much? He presupposes the answer with the subtitle "A disturbing 50 percent of doctoral students leave graduate schoo...
