Let f(n) be a monotone increasing function from N to N. Consider the following game: Let n be a natural number which we thing of as being large. Mark and Betty...
1630
GASARCH
wgasarch
Aug 4, 2010 5:11 am
RECALL from my last post the following game: Let f(n) be a non-decreasing function from naturals to naturals. Consider the following game: Let n be a large...
1631
GASARCH
wgasarch
Aug 9, 2010 3:41 pm
Let me be he last on the block to tell you that an alleged proof of P ≠NP is out there. NOT posting on it would be absurd; however, I cannot do any better...
1632
GASARCH
wgasarch
Aug 11, 2010 3:04 pm
(Update on alleged P NE NP proof: There are some issues with it. See these posts on Lipton's blog: here and here and also see a Wikipedia site that (I think)...
1633
GASARCH
wgasarch
Aug 13, 2010 2:29 pm
(Update on P vs NP: The proof uses Finite Model Theory which is sometimes called That stuff that Neil Immerman does.. Neil Immerman has found a flaw in it. See...
1634
Lance
fortnow
Aug 16, 2010 12:33 pm
This summer I took a two part vacation: Touring Ireland July 26-August 5, with my wife to celebrate twenty years of marriage and a short trip to Santa Fe,...
1635
GASARCH
wgasarch
Aug 17, 2010 1:52 pm
(This is likely my last post on the alleged P NE NP paper unless more real news on it occurs. The only real news I can see happening at this point is a...
1636
GASARCH
wgasarch
Aug 18, 2010 3:13 pm
The following conversation is a fictional version of a real conversation. Lance: Bill, Wed August 18, 2010 is Paul Turan's 100th birthday. We should post on...
1637
Lance
fortnow
Aug 19, 2010 12:24 pm
Dan Spielman wins the Nevanlinna prize for "smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to...
1638
Lance
fortnow
Aug 20, 2010 12:30 pm
Many changes at the National Science Foundation both in programs and personnel. Some highlights of upcoming CISE programs. - Expeditions is moving to an...
1639
Lance
fortnow
Aug 21, 2010 10:15 pm
Bill and I are strong believers in freedom of speech and have long since had an open comment policy, allowing anonymous comments, no moderation (except old...
1640
GASARCH
wgasarch
Aug 23, 2010 2:02 pm
Is Scheduling a Solved Problem? (Guest Post by Ben Fulton.) "At first glance, scheduling does not seem like a topic that requires much attention from computer...
1641
GASARCH
wgasarch
Aug 23, 2010 2:05 pm
(Guest Post by Ben Fulton.) "At first glance, scheduling does not seem like a topic that requires much attention from computer scientists". This was how I...
1642
GASARCH
wgasarch
Aug 24, 2010 1:41 pm
The Aug 19 episode of Futurama had NEW math in it! It also has some other math refs. - This website claims that Ken Keeler, one of the writers who has a PhD in...
1643
GASARCH
wgasarch
Aug 24, 2010 1:45 pm
The Aug 19, 2010 episode of Futurama had NEW math in it! It also has some other math refs. - This website claims that Ken Keeler, one of the writers who has a...
1644
GASARCH
wgasarch
Aug 25, 2010 4:23 pm
Three annoucements (the last two I was asked to post) ANNOUCEMENT 1: Congrads to fellow blogger ***SORELLE*** who got her PhD recently. I was on her committee....
1645
Lance
fortnow
Aug 26, 2010 1:47 pm
Bill is at Barriers II in Princeton and promises a full report upon his return. Ask many computer scientists what happens if P = NP and you'll get the response...
1646
Lance
fortnow
Aug 27, 2010 10:26 am
I got the following request from a reader. I have a question about TCS journals. As I am trying to follow your advice on being more diligent about journalizing...
1647
Lance
fortnow
Aug 30, 2010 11:11 am
The Simons Foundation has announced a competition to establish a new Institute for the Theory of Computing in the United States. Computation (and its abstract...
1648
GASARCH
wgasarch
Aug 31, 2010 1:39 pm
On Thursday Aug 26 Lance stated Bill is at Barriers II in Princeton and promises a full report upon his return. Not quite sure I promised that, or what a full...
1649
GASARCH
wgasarch
Sep 1, 2010 2:41 pm
People have asked me how much the alleged proof of P NE NP was discussed at Barriers II. Actually, nobody discussed the proof; however, we did discuss the...
1650
Lance
fortnow
Sep 3, 2010 12:47 pm
Yesterday I was at a meeting of the CCC Council, add in a couple of emails and I have lots of short notes on CS stuff. In these meetings I get to hear about CS...
1651
Lance
fortnow
Sep 7, 2010 12:43 pm
First some conference news: FOCS conference and hotel registration available on line, early deadline is September 30. STOC 2011 website is up with the CFP,...
1652
GASARCH
wgasarch
Sep 8, 2010 4:59 pm
In 1994 Fermat's last theorem was proven! In 2003 Poincare's conjecture was proven! In 2010 the Rubik Cube Conjecture was proven! That is, it was shown that...
1653
GASARCH
wgasarch
Sep 10, 2010 1:59 pm
I have heard the following story many times in many versions: A PhD student in Math at PRESTIGIOUS SCHOOL was defending his thesis which was in REALLY ABSTRACT...
1654
Lance
fortnow
Sep 13, 2010 11:13 am
The program for the FOCS 2010 has an excellent set of selected papers and in addition has tutorials on Saturday by Ketan Mulmuley, Mihai Patrascu, and Tim...
1655
Lance
fortnow
Sep 14, 2010 11:28 am
Suppose you happen to have $150 million burning in your pocket that you want to use to help the theoretical computer science community ($150 million endowed...
1656
GASARCH
wgasarch
Sep 16, 2010 4:40 pm
I have mentored many high school students on projects (21 in the past, 6 right now). Is this a good use of ones time? I note my experiences and advice- if you...
1657
GASARCH
wgasarch
Sep 20, 2010 2:48 pm
(Guest post from Clyde Kruskal.) Yesterday (September 19, 2010) my uncle, Joseph B. Kruskal passed away. I just wanted to say a few personal words. Maybe,...
1658
Lance
fortnow
Sep 21, 2010 11:25 am
The New York Times Magazine last Sunday focused on technology on education. Lots of good reads but what caught my eye was an article by Microsoft Research's...
