Computational Complexity

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 ...

On Wednesday, STOC had a great complexity session and the best complexity paper of the conference, Cody Murray and Ryan Williams extending ...

This week I'm in Los Angeles attending the 50th Symposium on the Theory of Computing. Most attendees weren't even born before the fi...

I've been meaning to post on THE MUFFIN PROBLEM for at least a year. Its a project I've been working on for two years, but every tim...

When I taught  ugrad  Elementary Theory of Computation (Reg, CFL, P, NP, Dec, c.e.) I made 5% of the grade be MEET THE PROF- come to my of...

Thanks to Grigory Yaroslavtsev for taking over the Theory Jobs Spreadsheet . Details on Grigory's blog . Check out who is going where...

(This post overlaps a prior one  here . The paper I am blogging about was also blogged about by Lipton  here . The paper itself is on arxiv ...

When teaching P vs NP  the questions arises (and if not then I bring it up) what if you have algorithm in P that takes n^{100} time?. Or eve...

The quantum complexity world is a rocking with the paper released yesterday by Ran Raz and Avishay Tal,  Oracle Separation of BQP and PH , r...

I stumbled upon an old blog post on the Lesswrong weblog that quotes several famous mathematicians  on the connections, or lack thereof, be...

I recently go the following email (I blocked out identifying information of who send it and what college is involved. I doubt I needed to le...

I got an interesting email question. Suppose I give you a set of points S of the form (x,y). He suggested ideally they would be pairs o...

Quad VDW Theorem: For all c there exists W=W(c) such that for all c-colorings of {1,...,W} there exists a,d such that a and a+d 2 are the s...