Computational Complexity

In one of the hallway discussions of last week's Dagstuhl I learned about an upcoming STOC paper Deciding Parity Games in Quasipolynomia...

This week I'm at the Dagstuhl workshop on Computational Complexity of Discrete Problems . As you long time readers know Dagstuhl is a ...

1) When I was a grad student TAing Formal Lang Theory we had a final ready to give out but noticed that one problem was too hard. So we cha...

If NP is in ZPP is the entire polynomial-time hierarchy in ZPP? I saw this result used in an old TCS Stackexchange post  but I couldn't...

Before FLT was solved did some people prove theorems like: FLT cannot be proven using techniques BLAH. This is important since all current...

Lisa Randall wrote a New York Times book review of Carlo Rovelli's  Reality Is Not What It Seems  with some interesting responses . I ...

BILL: The best way to prove closure properties of regular languages is to first prove  the equiv of DFA's, NDFA's and Reg Expressio...

I did some counting and the 35 academic faculty members in the Georgia Tech School of Computer Science come from 14 different countries. My ...

A while back I had a blog entry Should we learn from the Masters of the Pupils?  The Masters may have more insights but he Pupils may have ...

Kenneth Arrow, the Nobel Prize winning economist known for his work on social choice and general equilibrium, passed away Tuesday at the ag...

Why study Recreational Mathematics? Why do recreational Mathematics? 1)  The line between recreational and serious mathematics is thin. ...

Tuomas Sandholm (center) and Ph.D. student Noam Brown (via CMU ) Congratulations to Liberatus the new poker champ . Liberatus, an AI pro...

Raymond Smullyan was born on May 25 1919 and passed away recently at the age of 97.  He was a logician (PhD from Princeton under Alonzo Chur...

Note (8/19/17): The authors have retracted their claim  following the discovery of a counterexample by Ross Willard. However, there has been...

In my last post ( here ) I defined the following hierarchy (which I am sure is not original- if someone has a source please leave a comment ...

A solidarity rally held at Georgia Tech today There are ten Iranian members of my department, the School of Computer Science at Georgia...

Let Z_d[x] be the set of polynomials of degree d over the integers. Let ALG_d be the set of roots of polys in Z_d. One can easily show t...

As I checked in at the Holiday Inn in New Brunswick Wednesday night, they asked me if I had stayed there before. I said it has been a whi...

Every four years I post a PRESIDENTIAL QUIZ which I must update based on new information since we have a new prez and veep. The questions a...

There's a wonderful new series of math videos PBS Infinite Series hosted by Cornell Math Phd student Kelsey Houston-Edwards. Check out ...