Speaking of space complexity, Adam Kalai, Adam Klivans and Rocco Servedio have extended Reingold's result to show that every language in randomized logarithmic...
When computational complexity gets accused to having no connection to reality, I bring up the story of the PRAM (Parallel Random Access Machines), a complexity...
From a poster in my building: What is the longest song? " 0 bottles of beer on the wall." Happy Mathematics Awareness Month ! April is also National Poetry ...
A perfect spring day in Chicago and all of my afternoon meetings mysteriously canceled so I took visiting Portuguese professor and avid soccer fan Luis Antunes...
A recent conversation with a graduate student. Student: I couldn't find the paper online. Me: So walk over to the library and get the paper there. Student: But...
Little things that annoy me in research papers. Declarative first sentences of the introduction, like "Analyzing Left-Handed 12-SAT is a key approach to...
A guest post by Michael Mitzenmacher Lance nicely invited me to expand on my views on the format for conference submissions. Currently, I am on a PC using the...
A simple trick that every complexity theorist should know but, based on some recent conversations, not every complexity theorist does know. Roughly speaking...
New Balance has been heavily advertising some questions about sports so I'd thought I would give my own discussion questions about academics. You've been...
There is some buzz about a new construction of probabilistically checkable proofs by Irit Dinur. The PCP theorem, first proved by Arora, Lund, Motwani, Sudan...
Haipeng Guo wins the math poetry contest with the poem below. Congratulations and thanks to all that participated. When a P-man loves an NP-woman Been a happy...
You have probably heard this story by now. Some MIT students created a computer-generated paper accepted to a non-reviewed session of the Systemics,...
March Edition This month we honor the papers that gave us the first NP-complete problems and marked the official beginning of the P versus NP question. The P...
My daughters saw the movie Ice Princess over the weekend. Based on what they told me here is the basic story: Casey decides to do a science project on figure...
Around 1980 for fun in New Jersey we would go visit the electronic video arcades to play various games like Asteroids, Pac-Man, Tempest, Missile Command and...
Today is take your daughter (and son) to work day so today's post is written by Annie Fortnow (age 10) on the topic of her choice. This is a Dell Computer. It...
Too often Ph.D. theses in computer science consist of not much more than a couple of "papers stapled together." A shame as one can use the thesis to truly...
Some sad news from Thomas Schwentick. What we have feared during the last weeks and months came true yesterday morning: Clemens Lautemann died at the age of 53...
One of the requirements for a software engineering job at Autodesk. Good knowledge of common algorithms and data structures; understanding of computational...
Leonid Khachiyan passed away Friday at the age of 52. Khachiyan was best known for his 1979 ellipsoid algorithm giving the first polynomial-time algorithm to...
Some interesting game theory and philosophy from the last couple of NUMB3RS episodes. Usual spoiler warnings. In the April 22nd episode Dirty Bomb there were...
While other fields have standardized postdoc programs, computer science still searches for the right approach for postdocs. While we have had postdoc positions...
Science has a special issue on Distributed High Performance Computing including an article Service-Oriented Science by Chicago's own Ian Foster. The must read...
A few years ago, one ranking listed Harvard as the number one engineering school. The schools were ranked by average starting salary of their graduates and...
April Edition If Cook made the P versus NP question interesting to logicians, Karp made the question important to everyone else. Richard Karp, Reducibility...
Deep into the bowels of the Physical Sciences Library I went to retrieve the Proceedings of a Symposium on the Complexity of Computer Computation to track down...
One of our gradate students wanted to define a property P of classes C to hold if we don't know that C has complete sets. Doing so would make the concept time...
The US House Committee on Science held a hearing yesterday on The Future of Computer Science Research in the U.S. You can watch the webcast or read the...
In my last post you can find some links and comments about the tenure system. Let me add a few concerns that don't often get mentioned. Tenure keeps academic...
Guest Post by Boaz Barak The National Science Foundation (NSF) has a program called "Theory of Computing" which is the only program devoted to funding research...
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.
