Computational Complexity

H. Venkateswaran, a much loved professor in the School of Computer Science at Georgia Tech and a fellow computational complexity theorist, i...

There is a quote I recall but not who said it.  I have not been able to find it on the web. If you think a theorem is true then spend hal...

Since I am teaching Cryptography this semester I am teaching things people REALLY REALLY REALLY (RRR) use. For some topics this is RRR true,...

I'm spending this week at the Simons Institute in smokey Berkeley, California. This fall Simons has a program in Lower Bounds in Computa...

I had meant to post this before the election but I didn't quite time it right. Oh well. It has been said that this midterm election (m...

With all the news about elections, caravans, shootings and attorney generals, maybe you missed the various stories about real transformation...

Darling: Bill, help me with this crossword puzzle. 6 letter word that begins with N, clue is log man Bill: Napier Darling : Who was th...

In Bill's post earlier this week, he asks if there is a fixed algorithm such that if P = NP, this algorithm will correctly compute sati...

I am writing up the result of my survey of peoples opinion of P vs NP (it will be in a SIGACT News, in Lane's Complexity Column, in 2019...

Sometimes you see a beautiful theorem A that you love to talk about. Then another beautiful theorem B comes around, making the first one mea...

As I mentor many HS students I was recently in email contact with the HS contact for projects and I noticed that the sign off was Allie Do...

Imagine the following not-so-unrealistic scenario: The US-China trade war deepens leading to a cold war . The US blocks all Chinese citizens...

When it seemed like Riemann Hypothesis (RH) might be solved (see Lipton-Regan blog entry on RH   here  and what it points to for more info) ...

As we do every year at this time, we help you find that perfect academic job. So who's hiring in CS this year? Perhaps we should instead...

Guest Post by Vijay Vazirani                                                           A New ACO Center! Last week, I helped launch an  ...

John Sidles, Mike Roman, Matt Howell : please email me. at gasarch@cs.umd.edu (my usual email) I need to ask you about some comments you l...

If you google gasarch you used to  get the following:    here Please go there and notice how old they say I am. Okay, you are back. ...

Lance: It's Friday afternoon and the Dagstuhl workshop has ended. We have some time before we need take off so how about one final typec...

Lance: Bill, in our typecast earlier this week I said you were older than me. But 68? You don't look day over 66. Bill: Neither do yo...

Lance: Welcome to our typecast directly from Dagstuhl in Southwestern Germany for the 2018 edition of the seminar on Algebraic Methods in Co...