I had my Graduate Class in Communication Complexity VOTE FOR PREZ in a secret ballot. The rules were: They could vote for anyone on the ballot in Maryland, (I...
I made a snapshot of the electoral markets map at 5 PM Central time Monday to compare to the actual votes. Meanwhile you can continue to watch the markets...
Random comments on the election. - John McCain gave a nice concession speech and was excellent on SNL on Saturday. If he was that way the entire time he might...
Michael Crichton passed away yesterday. His early novels and movies showing the potential dark sides of technology had a strong impact on me in my youth. The...
Those of us who have taught logic to students are familiar with some of the fallacies they make: (1) confusing OR with XOR (reasonable given English Lang use),...
TWO ACCOUNCEMENTS I) Reminder: STOC submission abstracts due today. = 3. Joint work with Subhash Khot. ... Prof. Joe Mitchell (Stony Brook University)...
TWO ITEMS: I) Reminder: STOC submission abstracts due today. II) New York Area Theory Day Organized by: NYU/IBM/Columbia External sponsorship by: Google...
A few weeks ago Bill complained about how hard it is to get an electronic journal version of Barrington's theorem. Though Barrington's theorem was brand...
Recently the Kakeya Conjecture over finite fields (henceforth Kakeya) was resolved. For information on what Kakeya is and how it was solved see Dvir's paper On...
My younger daughter was deeply moved by An Inconvenient Truth and has become a staunch environmentalist ever since. She pushed me to change our lightbulbs as...
Sometimes the literature gives a proof, and then a reference, but the reference is not really to that proof. Here is an example. The theorem in question is the...
In the excellent paper On the power of two, three, and four probes It is well known that every graph with s vertices and at least 2s edges contains a cycle of...
One of my crypto students pointed me to the "Nerdcore Hip-Hop" group MC Frontalot. Here's a trailer for their tribute film, Nerdcore Rising. You can download...
Guest Blog by Joe Kruskal. He is the Kruskal that did the MST algorithm, the Kruskal Tree Theorem and work on multidimensional scaling. However, this post is...
Guest Blog by Joe Kruskal. He is the Kruskal that did the MST algorithm, the Kruskal Tree Theorem and work on multidimensional scaling. However, this post is...
Do you care about fonts? In other words do you care about how your paper looks? Not the details of the proofs or the quality of the exposition but how the...
I sometimes ask people What is your best paper? This question is actually ambigous. Here are criteria that you can use. - Most important to the public. E.g., a...
In Yao's paper Should tables be sorted he did the following (I am paraphrasing alot). A (U,n;q)-WPDS (Word Probe Data Structure) for MEM is the following; - A...
I deposited a check today at a new Chase ATM. You just put the check directly into the machine, the check gets scanned and the amount verified. Saves me a...
We are looking for a postdoc to join the new CS Theory and Economics groups at Northwestern. We'll consider any theory candidates though prefer candidates with...
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)...
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.
