Computational Complexity

(June 29th, co-located with STOC, will be a workshop to celebrate  Vijay Vazarani's 60th birthday. As computer scientists shouldn't ...

A good number of the faculty candidates interviewing at Georgia Tech have a common theme: Memory. Memory connected to databases, to progra...

(STOC 2018 will offer child care for the first time. I was emailed the following and asked to pass it on: We are pleased to announce that...

Every two years in Atlanta, recreational mathematicians gather to honor Martin Gardner, whose Scientific American column Mathematical Games ...

(An exposition of Nash-Williams's proof of  the Kruskal Tree Theorem is  here ) Andrew Vazsonyi (the mathematician, see  here , not th...

Recall that in a prior post I asked Is there an NFA for  { a y : y ≠ 1000 } with substantially less than 1000 states. I will now show ...

(Added later- a reader left a comment pointing to a paper with the answer and saying that the problem is not original. My apologies-  upon ...

I have been playing with a new complexity class AFQP, defined in a yet-to-be-published manuscript by Alagna and Fleming. A language L is in ...

A Turing machine has an extremely simple instruction set: Move left, move right, read and write. If you want to do real programming, you...