Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

Thursday, September 29, 2016

Give a second order statement true in (R,+) but false in (Q,+) or show there isn't one

›
Here is a logic question I will ask today and answer next week. Feel free to leave comments with the answer- you may come up with a differe...
18 comments:
Tuesday, September 27, 2016

Who's Afraid

›
The playwright  Edward Albee passed away earlier this month at the age of 88. I had never actually seen any of his plays so I took the oppo...
1 comment:
Thursday, September 22, 2016

Boris Trakhtenbrot (1921-2016)

›
I woke up this morning to two pieces of news. Subhash Khot has just been named a MacArthur Fellow, the "genius" award, for his wo...
1 comment:
Wednesday, September 14, 2016

Academic Rankings Foster Competition

›
This week US News and World Report released their undergraduate rankings  earlier this week. A time for schools to brag . US News and World ...
22 comments:
Saturday, September 10, 2016

Noam Nisan wins the Knuth Prize

›
Noam Nisan will receive the 2016 Donald E. Knuth Prize , the highest honor in theoretical computer science, for his work in computational ...
1 comment:
Wednesday, September 07, 2016

Why I Don't Believe in ET

›
Is there life on other planets? The naive answer is "of course, why should Earth be special." What makes a lottery winner special?...
13 comments:
Tuesday, August 30, 2016

I have consulted four times. Really!

›
Those who know me know that I work on stuff that is not readily applied. Or perhaps not applied at all. Certainly my current state of knowle...
6 comments:
Thursday, August 25, 2016

1956 Was a Fine Vintage

›
Bill sends me an email last week with the subject "Our field is getting old!" and talks about upcoming 60th birthday/retirement co...
6 comments:
Monday, August 22, 2016

Chrisitan Comment on the Jesus Wife Thing misses the important point

›
In 2012 a Professor of Divisinity at Harvard, Karen King, announced that she had a fragment that seemed to indicate that Jesus had a wife. I...
7 comments:
Thursday, August 18, 2016

Predicting in Changing Environments

›
The New York Times yesterday ran a story connecting climate change to the Louisiana flooding. The National Weather Service reports that ...
1 comment:
Monday, August 15, 2016

Is the examiner being pedantic? Whats really going on here?

›
The following are two real conversations.  For each one: (1) Is the examiner correct?, and (2) Where and when do you think this conversatio...
9 comments:
Thursday, August 11, 2016

Robin Hanson's Ems

›
Robin Hanson an economist at George Mason and author of the Overcoming Bias blog, has a new book The Age of Em: Work, Love and Life when Ro...
3 comments:
Sunday, August 07, 2016

A Game Theory Conference! That sounds like fun!

›
Bill: Lance just came back from  Games , a conference on Game Theory. Darling: That sound like fun! From what you tell me there is some n...
4 comments:
Wednesday, August 03, 2016

Seymour Papert (1928-2016)

›
Seymour Papert, the great AI pioneer, passed away Sunday at the age of 88. In the theory community we best know him for his 1969 book Per...
2 comments:
Thursday, July 28, 2016

GAMES/EC 2016

›
This week I report from Maastricht in the Netherlands from the GAMES 2016 , the 5th World Congress of the Game Theory Society. By having the...
Sunday, July 24, 2016

The College Issues that are talked about/College issues that are important

›
The following college issues get lots of attention: Admissions-  high school students PLAN to do things JUST to get them into an elite col...
5 comments:
Thursday, July 21, 2016

Snowbird 2016

›
Earlier this week I attended the 2016 CRA Snowbird Conference , a biennial meeting of CS chairs and other leaders in the the computing commu...
2 comments:
Monday, July 18, 2016

Solution to the Alice-Bob-Box problem.

›
In my  last blog  I solved one problem and asked another (when will it end!).  Damien Roberts provided an answer in the comments to the last...
10 comments:
Thursday, July 14, 2016

Solution to the infinite hat problem/a point/a new problem

›
In my last post  I asked the following question (I've shortened it here but its the same really.) An infinite number of people, labell...
18 comments:
Sunday, July 10, 2016

An infinite hat problem and later a point

›
Problem : There are an infinite number of people. They are labelled 1,2,3,... ( I am not a number, I am a free man !) There is the Master ...
16 comments:
‹
›
Home
View web version
Powered by Blogger.