Guest Post from Aaron Sterling) Multi-Agent Biological Systems and the Natural Algorithms Workshop I attended the Natural Algorithms Workshop on November 2nd...
1472
GASARCH
wgasarch
Nov 11, 2009 6:45 pm
IBM-NYU-COLUMBIA theory day on Dec 11 ! Here is pointer to more information: here My advice: If you are able to go (distance, time, money all okay) then you...
1473
Lance
fortnow
Nov 12, 2009 11:36 am
Many of you readers don't remember a time when there were two Germanys or when we didn't think IP = PSPACE. Two walls collapsed in November of 1989 that...
1474
Lance
fortnow
Nov 13, 2009 11:55 am
As many university's still feel the effect of the financial crises, many have limited or no positions to hire new tenure-track faculty so I expect the academic...
1475
GASARCH
wgasarch
Nov 16, 2009 4:39 pm
There are now laws about blogging and twittering that Lance and I (and all the bloggers) will need to be aware of. Here is a short summary: - If a blogger...
1476
Lance
fortnow
Nov 17, 2009 1:10 pm
As a young kid in the Reform Jewish community we used the Union Prayer Book, a traditional book with Hebrew on the right and English on the left with lots of...
1477
Lance
fortnow
Nov 18, 2009 11:38 am
As I tweeted yesterday, the videos of talks from the 2009 FOCS conference are now online. Thanks to FOCS PC chair Daniel Spielman and Georgia Tech's ARC Center...
1478
GASARCH
wgasarch
Nov 19, 2009 4:52 pm
There are now bibles online where you can click for different versions, different translations, different interepretations, historical context, etc. The same...
1479
Lance
fortnow
Nov 20, 2009 12:58 pm
A student asked me which version of a research paper to cite, a journal (the last reviewed version) or a conference (the first reviewed version) of a paper. I...
1480
GASARCH
wgasarch
Nov 23, 2009 6:26 pm
As most of you know there are 7 problems worth $1,000,000 (see here). It may be just 6 since Poincare's conjecture has probably been solved. Why are these...
1481
Lance
fortnow
Nov 24, 2009 2:03 pm
Last Friday DIMACS celebrated its 20th anniversary. Muthu summarizes the event. DIMACS has served the theoretical computer science community well over these...
1482
Lance
fortnow
Nov 25, 2009 11:31 am
First a message from David Johnson for proposals on locations for SODA 2012 both in and outside the US. Here's an interesting approach to the birthday paradox...
1483
GASARCH
wgasarch
Nov 30, 2009 6:16 pm
The 17x17 challenge: worth $289.00. I am not kidding. Definition: The n x m grid is c-colorable if there is a way to c-color the vertices of the n x m grid so...
1484
Lance
fortnow
Dec 1, 2009 2:41 pm
If Professor Alice at Faber College visits Dr. Bob at the University of Southern North Dakota, who should cover Alice's expenses? It depends on who does the...
1485
GASARCH
wgasarch
Dec 2, 2009 4:16 pm
One of the comments on my last post, the 17x17 post, inquired if I am also interested in the other unknown grids (17x18, 18x18, 21x10, 21x11, 21x12, 22x10). I...
1486
GASARCH
wgasarch
Dec 3, 2009 6:29 pm
Congrads to ALL of the ACM Fellows which were annouced here. There are several theorists among them. I could try to list them or count them; however, the term...
1487
Lance
fortnow
Dec 4, 2009 12:26 pm
Dean Foster asked me for a probability that P=NP. Now P=NP is not a probabilistic event, either P=NP or P≠NP (if it's independent it's still equal or unequal...
1488
Lance
fortnow
Dec 7, 2009 12:33 pm
Quick announcement: If you are a student who wants to go to SODA but doesn't have the funds, click here. I had forgotten we did this. Here's a video of my...
1489
Lance
fortnow
Dec 8, 2009 4:06 pm
After a talk on derandomization at Midwest Theory Day, someone asked if those techniques could also be used in quantum computing. In classical randomness under...
1490
GASARCH
wgasarch
Dec 9, 2009 5:08 pm
(The 17x17 problem has gotten far wider attention than I imagined--- Brian Hayes posted it on his website: here, and its also here and here. The last website...
1491
GASARCH
wgasarch
Dec 10, 2009 5:00 pm
BILL: Clyde is teaching a graduate course titled Games, Game Theory, and the Theory of Games. He tells me that there are basically eight kinds of games...
1492
Lance
fortnow
Dec 11, 2009 11:41 am
With the end of the fall quarter I will take a break from the blog for a few months. This is not another End, just a chance to move my creative juices in...
1493
GASARCH
wgasarch
Dec 14, 2009 5:23 pm
Submissions to 25th CCC are due TOMMOROW! (Actually it could be TOMMOROW, TODAY, or IN THE PAST depending on when you read this.) Should you submit? - If you...
1494
GASARCH
wgasarch
Dec 14, 2009 5:25 pm
Submissions to 25th CCC are due TOMORROW! (Actually it could be TOMORROW, TODAY, or IN THE PAST depending on when you read this.) Should you submit? - If you...
1495
GASARCH
wgasarch
Dec 15, 2009 3:37 pm
(Deadline to submit a paper to CCC is Dec 15. Depending on when you read this that could be today or in the past.) As you all know from Lance's last post,...
1496
GASARCH
wgasarch
Dec 16, 2009 4:21 pm
(Tal Rabin requested to post this so I am doing so. This post is essentially her email, so call it a guest post.) There will be a Women In Theory workshop for...
1497
GASARCH
wgasarch
Dec 17, 2009 3:30 pm
The following problem was problem 1 (the easy one) on the Maryland Math Competition 2009 (I will later report on how the students did on it). - Show that for...
1498
GASARCH
wgasarch
Dec 18, 2009 4:36 pm
The Prob method (usually credited to Erdos) was once considered quite novel: You show something exists but you don't show how to construct it! An early example...
1499
GASARCH
wgasarch
Dec 22, 2009 5:03 pm
(This is my last blog of the year. Lance will interupt his blog sabbatical to do an END OF THE YEAR blog later.) The TV show MONK recently finished its 8th and...
1500
Lance
fortnow
Dec 28, 2009 12:15 pm
We go all the way back to January for the paper of the year, Mark Braverman's Poly-logarithmic independence fools AC0 circuits. Runners up include the...
