A commenter yesterday asked about a Crooked Timber post arguing that many strong departments place an emphasis on hiring students from other strong departments...
Consider the following paragraphs from Tom Clancy's novel Rainbow Six . The phone they spoke over was the Russian version of the American STU-3, the technology...
November Edition We started this list of favorite theorems with derandomization of time classes. Now we end the list by looking at derandomizing space-bounded...
Academic bloggers (like Jeff and Suresh ) are up in arms about a column by Ailee Slater in the University of Oregon student paper. We are currently paying a...
Iowa State graduate student Chad Brewbaker created a graphical map of the complexity classes in the zoo . Who says you can't have fun with complexity? --...
Volunteer to organize a conference and I guarantee you will get an email like the following I am a computer scientist from Nigeria. I am interested in...
The National Science Foundation rarely gets mentioned in the popular press. After the recent budget cut , the NSF now gets some mention, including a New York...
Birthday Boy Rocco Servedio gave a talk at TTI on Friday on learning random functions over random inputs. John Langford asked about distributions that put more...
Texas student Vladimir Trifonov gives An O(log n log log n) Space Algorithm for Undirected Connectivity . If it came out a few months earlier (assuming the...
In the month of November 44.3% of the hits on this website came from windows machines. If you are in this minority and don't mind a small amount of hacking,...
A program committee member who asked me to review a paper pointed me to Oded Goldreich's Suggestions to Program Committees , one of his Essays and Opinions ....
A program committee member who asked me to review a paper pointed me to Oded Goldreich's Suggestions to Program Committees , one of his Essays and Opinions ....
While we have seen a increase in computer science funding over the past few decades, it has not kept up with the great increase in the number of researchers in...
Yesterday a program committee member sent one of my submissions to one of my current students to review. Heh Heh. I'll make sure he gives an unbiased positive...
The US House Appropriations committee has passed the NSF budget at a 2% ($111 Million) cut. There are still many more phases in the budget process to go but...
You just submitted your paper, working hard right up to the final deadline hour. Congratulations! Now what? Forget about it. Oh you should distribute the...
The Zig-Zag Graph Product (Reingold-Vadhan-Wigderson) gave a new way to create expander graphs, graphs on n vertices with constant degree such that for some >0...
Google has just launched a new search engine for academic papers scholar.google.com . Google has received permission from some publishers to allow searching...
A dinner conversation with my daughters. Annie (age 9): How many computer scientists are there in the world? Me (Wildly Guessing): About 100,000. Molly (age...
I went with my family to see the movie The Polar Express . This movie blurs the line between between acting and animation. Tom Hanks played several characters...
The search wars are brewing. Microsoft starts a beta test of their new search engine . Yahoo keeps improving their searching as well and Google does not stand...
Omer Reingold has shown Undirected s-t Connectivity in Deterministic Log-Space . This settles a long-standing open question for a problem previously known to...
A grad student asked me how we managed before the internet specifically in relation to submitting to conferences? I cannot completely answer that question as I...
October Edition Alice and Bob have subsets of {1,,n}. How much communication do Alice and Bob need to determine if their subsets have a empty intersection. In...
Our department, like many other academic departments, felt a strong sense of depression today. Just remember there are still theorems to prove, papers to...
Complexity theorists have an important choice to make this week. That's right, I'm talking about whether to send your papers to STOC or Complexity . So let me...
A true story on Election Day 2000: An Israeli postdoc in the US came to work and said "I have watched the conventions and seen the debates. I have studied the...
In theoretical computer science we traditionally list the co-authors of our papers alphabetically. Done this way for "fairness"; it leads to a binary notion of...
