Computational Complexity

CMU's Jeannette Wing named head of the CISE directorate. Hopefully she can put some of that Computational Thinking into the NSF.

Having looked at the applications of several theoretical computer science job candidates, I notice some interesting differences from even on...

A 6% increase for the National Science Foundation for the current fiscal year (via the CRA Blog ). Now go write those proposals .

Life is just a big Markov chain, whose stationary distribution is death.

Suzanne Zeitman, associate editor of AMS Mathematical Reviews (and on the web ), would like to get suggestions from the TCS community on ho...

A conversation I heard about several years ago. Physicist: Computer scientists have done nothing for quantum computing. Computer Scientist...

Hanging in the Indiana University Mathematics Lounge is a letter dated November 16, 1948 written to Max Zorn from Nicolas Bourbaki and cc...

Last week Chicago Cosmologist Michael Turner gave a talk "Trends in Science Funding: From NSF to the ACI". Turner was head of the ...

A reader asks What are currently considered to be the best textbooks for complexity? I know the choice is small ( Papadimitriou is probabl...

Grant Schoenebeck asked this question for the Q&A Podcast but we didn't get to it. In proceedings, papers are printed in a hard-to...

Jason Teutsch is an Indiana Math Ph.D. student who has been working with me via the CIC Traveling Scholars program. Tomorrow he defends his...

My daughter learned about square roots and she did her homework taking those roots using a calculator. She asked me how to compute the squar...

It is a conference ritual as far back as I remember. Your arrive at the conference and receive the proceedings, all the papers to be present...

Richard Ladner wants me to remind my readers about the SIGACT student research competition. From his chair letter in the last SIGACT news. ...

A cute problem that I got off Steve Fenner's door that he got from FOM . Let x and y be two integers with 1<x<y and x+y≤100. Sal...

While Luca suffers in Hong Kong, I am visiting beautiful Columbia, South Carolina. (The ribs are better here) Next week a day in Bloomingto...

Why do so many scientists wear glasses? Thirty years ago this question was essentially equivalent to "Why so many scientists have bad e...

Suresh and Jeff cover the SODA Conference currently meeting in New Orleans. Suresh talked about a lecture given by Luc Devroye giving te...

A graduate student asks What should I wear for an academic job interview? Most computer scientists won't notice and will completely fo...

Jan van Leeuwen runs down many of the anniversaries coming up this year. Reading your post 2006 Year in Review , I was reminded of a numbe...