Computational Complexity

CSP stands for COMPUTER SAVY PERSON. 25 years ago the following happened: BILL: I can't get my computer to work. CSP: Just push t...

The comments on both Vijay's guest post and Lance's post brought out many comments about FOCS/STOC. People seem to have strong fee...

(Guest Post by Vijay Vazirani!) The processes of submitting FOCS/STOC abstracts and conducting PC meetings have undergone numerous change...

I recently visited my nephew and his five kids and tried to get my 8-year-old great nephew Justin interested in some math. I told him that I...

The Knuth Prize for 2007 was announced: Nancy Lynch. The formal announcement is here . The Knuth Prize is awarded for a lifetime of work in...

The website for Complexity 2007 is up now (its been up for while) CCC08 . In 2007 it is part of FCRC, a set of conference including STOC. ...

Dave Barrington suggested I blog about Paul Cohen since he just died. Scotts Blog already reported on Paul Cohen's death, and there wer...

Various people have urged Lance to keep the Blog going, perhaps under new management. Some have suggested Bill Gasarch (me) . Some have sugg...

After 4 1/2 years and 958 posts I have decided to retire from blogging. No weblog can go on forever and I would rather end on my own terms t...

Today a new Teenage Mutant Ninja Turtles movie opens. The turtles were quite popular back in the late 80's and early 90's, somehow...

So if I get a number of P=NP and P≠NP "proofs" what do the law professors get? A long email argument that most income tax is illeg...

The Federated Computing Research Conference (FCRC) has opened registration and housing . FCRC, held June 8-16 in San Diego, is a mega-conf...

The NSF has posted a search for a new theory program director to take over after Bill Steiger's term expires this summer. The program d...

The long-running Jeopardy television game show had a first on Friday, when all three players ended up tied for the first time . The three ...

A readers asks where he can put his open problem on the web. Back in the late 80's we had three Theorynet mailing lists. Theorynt-A ann...

I just returned from visiting the University of Toronto, my first visit to the campus in 18 years. I spent much of my time talking to the sa...

My 6th grade daughter takes the ISATS (Illinois Standard Achievement Tests) this week, tests meant more to evaluate the school than the stud...

A reader asks how the tenure process works in US universities. I will describe a typical case but the system works differently depending on ...

A conversation I had with a graduate student, maybe ten years ago. Student: I hear Bill Gates wants "P ≠ NP" proven at Microsoft...

The Electronic Commerce accepted papers have been posted. EC will be held as part of the FCRC in San Diego in June. EC has also announced ...