Computational Complexity

At Dagstuhl I got a few ideas for future posts but then... We had some discussions about STOC allowing program committee members to submit...

In light of the recent academic scandal I am going to list ways I've heard to help get your kid into college and thoughts on how ethical...

Participants and Their Research Interests This week I'm in Germany for the Dagstuhl workshop on  Computational Complexity of Disc...

I took a poll of the theory community (and others) about P vs NP and related issues in 2002, 2012, and 2019 (sorry its not an arithmetic  s...

If the president of the United States uses "complexity" in a tweet, I can't leave it alone. Airplanes are becoming far too ...

When I first saw the definition of NP-Complete I first thought if there are NP-complete problems I suspect they are contrived. When I saw t...

Via Scott , John Horgan wrote a blog post  following on his 1993 Scientific American article The Death of Proof . The article talked about c...

(This is about my book PROBLEMS WITH A POINT: exploring Math and computer science by Gasarch and Kruskal,  here . This post is NOT a plug.)...

Take a moment and imagine a flying pig. Do you see a pig with tiny wings lazily guiding along. But pigs are not particularly slow animals as...

As you can see from Lance's tweet                Problems with a Point: Exploring Math and Computer Science                by Gasar...

Last weekend I saw the documentary Joseph Pulitzer: Voice of the People . Pulitzer, as you probably know from the prize named after him, was...

I recently read an absurd article that speculated on who the Democratic VICE prez nominees will be. Yes, you read that right, VICE Prez. Gee...

So you've got an iPhone XS in Space Grey. Congrats, so do 20 million other people. Maybe you have different cases but otherwise the hard...

You've probably heard the following:                At first I didn't want to get an X but now that I have it, I can't imagin...

As a grad student in the late 80's I had the opportunity to witness many great and often surprising theorems in computational complexity...

(Superb Owl is not a typo. I've heard (and it could be wrong) that the  NFL guards their copyright so you can't even say `Buy Beer ...

The Chronicle of Higher Education recently published a story  Phishing Scheme Targets Professors’ Desire to Please Their Deans — All for $50...

The Paradigm Shift in FinTech Computation and the need for a Computational Toolkit (Guest Post by Evangelos Georgiadis ) We are experien...

My daughter Molly spent six weeks on an environmental program in China last summer. When she got back she had to do a report on machine l...

(ADDED LATER: deadlines for some of these awards have passed but here are ones coming up soon: Godel Prize: Feb 15 Knuth Prize: Feb 15 ...