Computational Complexity

A while back complexity blog,  Shtetl-optimized , and GLL all blogged about the improved matrix mult algorithms (Complexityblog: here , Sht...

At the recently completed STOC and the previous FOCS, much of the discussion revolved around reforming the conferences. You read the discuss...

(All the math this post refers to is in my manuscript which is here.) Recall Schur's theorem on making change as stated in wikipedia ...

On Wednesday at FCRC, the Complexity, STOC and EC (Economics and Computation) conferences all have sessions, a smorgasbord of talks, but tou...

This week I'm at the Federated Computing Research Conference in Portland, a collection of many mostly ACM conferences. Last night was t...

I posted at some earlier time that I was resigning from the editorship of SIGACT NEWS book review column, and handing the reins over to Fre...

A guest post by Dylan McKay, recently graduated from Georgia Tech and soon to be PhD student at Stanford. [Editor's Note: Turns out t...

A while back  when I got back the galleys for a paper the publisher wanted to know the complete postal address of one of the co-authors and ...

In a prior blog entry  HERE I discussed very large differences in the size of machines. I didn't discuss CFG vs CSG so I'll do tha...

László Babai will receive the 2015 Knuth Prize  and Daniel Spielman and Shang-Hua Teng will receive the 2015 Gödel Prize . ACM issued a ...

Alice and Bob are at an auction and Alice wants to buy an encyclopedia set from 1980. Bob says don't buy that, you'll never use it....

John Nash and his wife Alicia died in a taxi accident , returning from the airport after he received the Abel prize in Norway. The public kn...

I taught Discrete Math Honors this semester. Two of the days were cancelled entirely because of snow (the entire school was closed) and fou...

In the fall we list theory jobs , in the spring we see who got them. Like  last year , I created a fully editable Google Spreadsheet to cro...

Juris Hartmanis and Richard Stearns in a photo dated May 1963. The main theorem from their paper is on the board later improved by Hennie ...

In the book Hail to the Chiefs about the presidents, when pointing to a race between two people who had no business being president (I thin...

Last week we have a celebration of the new CS graduates at Georgia Tech where each graduating student says what their plans are for next yea...

If A is a decider (e.g, DFA)  or generator (e.g., CFG) then L(A) is the language  that it decides or generates. The following are well kn...

A Georgia Tech student asked the title question in an introductory theory course. The instructor asked his TA, the TA asked me and I asked t...

Last semester I ran a THEORY DAY AT UMCP. Below I have ADVICE for people running theory days. Some I did, some I didn't do but wish I di...