Computational Complexity

This is an ANON guest post. Even I don't know who it is! They emailed me asking if they could post on this topic, I said I would need ...

Glencora Borradaile wrote a blog post in June about how conferences discriminate. Let me spell it out. In order to really succeed in most...

On Aug 16, 2018 Aretha Franklin died. A famous singer. On Aug 18 2018 Kofi Anan died. A famous politician. On Aug 25, 2018 John McCain d...

The Simons Institute at Berkeley has two semester long programs this fall, Lower Bounds on Computational Complexity and Foundations of Dat...

This Fall I am teaching the senior course in Crypto at UMCP. Its a nice change of pace for me since REAL people REALLY use this stuff! Contr...

Katherine Johnson is celebrating her 100th birthday today. This is the first centenary post we've done for a living person. The movie...

A couple of years ago , Rossman, Servedio and Tan showed that the polynomial-time hierarchy is infinite relative to a random oracle. That is...

Some graphs are 2-colorable, some graphs are 3-colorable, some graphs are...Does it make sense to say that a graph is 2.1-colorable? It does...

(Johan Hastad won the Knuth Prize! The below post was written before I knew that but has a mild connection to it. See  here  for more info o...

After the Oxford Workshop I enjoyed a two-week family vacation in Spain, where there was no rain in the plain, just very hot up to 106℉. T...

On June 29, 2018, a workshop was held, in conjunction with STOC 2018, to celebrate the accomplishments of Vijay Vazirani on the   occasion...

There are three questions I ask in my Formal Lang Theory class that even the very best students get wrong. Two I knew were trick quesions, t...

Oxford, England is in the middle of a heat wave and it handles high temperatures about as well as Atlanta handles snow. But that can't s...

Teaching crypto for the first time next semester I am looking into lots of stuff I always meant to look into but now I have to. NOT a compla...

Marios Papaefthymiou (UC Irvine), Michael Franklin (U. Chicago), Larry Birnbaum (Northwestern) and me. This week I attended the 2018 Co...

You just can't watch a movie these days without being inundated with trailers. First came Axl , a movie about a boys love for a military...

 A long long time ago  a HS student, Justin Kruskal (Clyde's  son)  was working with me on upper bounds on some Poly VDW numbers (see he...

I have done two surveys for SIGACT NEWS Complextiy Column (edited by Lane Hemaspaandra) on P vs NP and related topics.  Lane has asked me...

Juris Hartmanis turns 90 today. Hartmanis with Richard Stearns received the 1993 Turing Award for their seminar work  On the Computationa...

(The new SIGACT News chair wnated me to post a letter he send to all SIGACT members on my blog in case you are not in SIGACT. He thinks you ...