Computational Complexity

(Thanks to Timothy Chow for inspiring this post.) My survey on Hilbert's Tenth Problem(see  here ) is about variants of the problem. One...

As we come out of a pandemic with online teaching and research collaborations, how much do we actually need the university? Theoretical rese...

The City of Chicago yesterday agreed with the latest CDC guidelines that those of us fully vaccinated no longer have to wear masks in most s...

 There have been some recent blog posts by Scott (see  here ) and Lance (see  here )  about the hype for SHORT TERM APPLICATIONS of Quantum ...

 I first wrote about bitcoin in this blog ten years ago  after I gave a lecture in a cryptography class I taught at Northwestern. Two years ...

 I care about the Facebook decision to ban Trump, but I do not have a strong opinion about it. I have heard arguments on both sides now, fro...

So you got an offer to be an assistant professor in the computer science department at Prestigious U. Congratulations!  Time to negotiate yo...

 ( Added later: Fred Brooks passed away on November 7, 2022, at the age of 90.) The Mythical Man-Month is a great book which talks about the...

1978: I took an excellent  ugrad course in combinatorics from James C Frauenthal (he sometimes wrote his name as the biniomial cofficient (J...

Illinois Tech has one of the greatest origin stories for a university. In 1890 Frank Gunsaulus, a pastor on the south side of Chicago, gave ...

 This is a Guest Post by David Marcus. He gives a puzzle and its solution, which is interesting, and then speculates as to why some people g...

First, congratulations to fellow complexity theorist and  blogger Scott Aaronson for receiving the 2020 ACM Prize in Computing for "g...

 Alice works at a charity that puts together bag and box lunches for children. They all wear masks and they are 12 feet apart and very caref...

Scott Aaronson  wrote last month about the hype over quantum computing. I'd thought I'd drop a few stories. I was once asked to rev...

BILL: Lets say we didn't know that FACTORING NPC --> NP=coNP. then what direction would we think Factoring in P or NPC?  STUDENT: In ...

This is embarrassing to admit but after a few badly timed trades on GameStop options I find myself a bit tight on money. To raise some cash,...

Here's a neat result I heard about at virtual Dagstuhl last week, a new lower bound on the number of hyperplanes that cuts all the edge...

 In my last blog post I posed a question about finding the coeff of x^100 in a particular Taylor Series. The question and answer are given  ...

 I post a problem today and its solution on Thursday. Comments are fine, though if you don't want to get a hint, don't read them.  F...

I'm absolutely elated that  Lázló Lovász and Avi Wigderson won the Abel Prize . More from the New York Times , Quanta Magazine and Gil ...