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,...
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...
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...
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...
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...
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? --...
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...
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...
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...
A commenter yesterday asked about a Crooked Timber post arguing that many strong departments place an emphasis on hiring students from other strong departments...
One of my Indian graduate students mentioned the university yookla and gets confused when I talk about Texas (not UTA) or Illinois (as opposed to UIUC which is...
Coming in January to the American television network CBS, a series about a FBI agent who recruits his brother, a math genius, to help solve crimes. I don't...
In 1994, I listed My Favorite Ten Complexity Theorems of the Past Decade in conjunction with an invited talk at that year's FST&TCS conference. Over this past...
By Prahladh Harsha and Jaikumar Radhakrishnan It was nice to be back in Madras after a long time and even nicer to meet friends from MIT and elsewhere during...
Chennai, the location of the recent FSTTCS conference reviewed in the last post , was one of the areas hit hard by today's earthquake caused tsunami . The...
Fred Roberts, Rakesh Vohra and myself are co-charing the DIMACS Special Focus on Computation and the Socio-Economic Sciences , a series of workshops and other...
A guest post from Alan Selman It is a common and acceptable practice to present a preliminary version of a paper at a conference and then to submit the full...
Theorem of the year goes to Omer Reingold who shows Undirected Connectivity in Logarithmic Space , settling the long-standing open problem. Also of note, Ran ...
We talked about embarrassing moments in our careers recently. I've had talks gone bad and conversations with person A thinking they were person B. And once I...
By Netanel Lindner, Petra Scudo and Danny Terno via Christopher Fuchs Quantum information science lost one of its founding fathers. Asher Peres died on Sunday,...
We define big-oh notation by saying f(n)=O(g(n)) if there exists some constant c such that for all large enough n, f(n) c g(n). If the same holds for all c>0,...
A few years ago an undergrad in my class did his programming project based on the movie Monty Python and the Holy Grail . He attached a note to the project...
I'm off the net next week. My student Rahul Santhanam will guest post in my absence. Enjoy! -- Posted by Lance to Computational Complexity at 1/8/2005 07:01:30...
Thanks to Rahul Santhanam for covering for me last week. If you are looking for a smart hard-working postdoc in complexity take a look at Rahul. On the plane...
A few random comments as I read and write recommendation letters for various academic positions: Back in the old days, a candidate would send a department a...
I have listed my favorite theorems for the first and second decades of my research career corresponding roughly to the third and fourth decades of research in...
A non-CS Chicago Alum asked me a question about free will and computation. I passed the question to David McAllester, an AI professor at TTI, and he gave the...
John Langford starts a new weblog Machine Learning & Theory . 2004 Year End Awards from Chris Masse's Predictions Market Digest (from David Pennock) Is love ...
Feel free to comment on last night's premier of Numb3rs , a show that has seemed to capture the interest of this community. For good reason as apparently the P...
A publisher sent me a copy of Blink a new book by Malcolm Gladwell. Gladwell wrote the very popular Tipping Point about phase transitions which I haven't read....
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.
