Computational Complexity

(The Baseball season is delayed or cancelled, so I post about baseball instead.) This post is going to ask a question that you could look ...

Richard M. (Dick) Dudley died on Jan. 19, 2020 (NOT from Coronavirus).You can find obituaries for him   here ,  here , and  here  and an in...

Below is an awesome video made by WIT (Women In Theory) on May 10, 2020 to celebrate the women in our field and in place of the Women in Th...

The Computational Complexity Conference has announced the accepted papers for the 2020 now virtual conference. Check them out! Speaking ...

Bill and Lance have another socially-distanced vidcast , this time with Lance telling the story of two conferences ( ACM Economics and Compu...

Hilbert's 10th problem, in modern language is: Find an algorithm that will, given a poly over Z in many variables, determine if it ha...

As a complexity theorist I often find myself far more intrigued in what we cannot compute than what we can.  In 2009 I posted on some predic...

I asked my Grad Ramsey Theory class to email me about whatever thoughts they have on the pandemic that they want to share with the world, wi...

Bill and Lance aim to talk about the future but can't escape the present.

Both STOC and Complexity have announced they will go virtual for the summer. ICALP moved from Beijing to Saarbrücken to online. I expect ...

Guest post by the TCS4F initiative (Antoine Amarilli, Thomas Colcombet, Hugo Férée, Thomas Schwentick)  TCS4F is an initiative by theoretic...

John Conway passed away on April 11, 2020 of the Coronovirus. He is the first person I knew (for some definition of `know') who has died...

Bill and I just have a discussion , virtually of course.

Since March 19th I have worked out of home. I've had virtual meetings, sometimes seven or eight a day, on Zoom, Bluejeans, Google Hangou...

We will be looking at the size of descriptions  For DFAs and NFAs this is the number of states. For CFG's we will assume they are i...

Graph Theorist and Georgia Tech Math Professor Robin Thomas passed away Thursday after his long battle with ALS. He was one of the giants...

Lance had a great post on what to do while you are stuck at home, which is of course relevant to whats happening now. Lance's post is  h...

First of all both the Turing award and Abel Prize announced yesterday. As we start moving from the panic phase of the coronavirus to the...

Richard Guy passed away on March 9, 2020 at the age of 103. Before he died he was the worlds oldest living mathematician (see  here  for a l...

People skip conferences because of the coronavirus or for global warming or just because conferences are too expensive and time consuming....