Computational Complexity

 Nikola Tesla, famous inventor, who lived 1856--1943 said the following: When wireless is perfectly applied the whole earth will be converte...

FOCS 2000 took place in Redondo Beach, just south of Los Angeles, November 12-14. Certainly some great results such as the Reingold-Vadhan-...

 Most games have some way to make sure they cannot go on forever. 1) Chess: I had thought there was a 50-move rule and a 3-times-same-positi...

 Last seek I blogged about two math problems of interest to me  here . One of them two people posted answers, which was great since I didn...

 In my last post (see  here ) I asked two math questions. In this post I discuss one of them. (I will discuss the other one later, probably ...

 I will give two math problems that are of interest to me. These are not new problems, however you will have more fun if you work on them yo...

(The two proofs that CLIQ is #P-complete that I discuss in this blog are written up by Lance and myself and are  here . I think both are wel...

 #P was defined by Valiant as a way to pin down that the PERMANENT of a matrix is hard to compute. The definition I give is equivalent to th...

In my poll of P vs NP and other issues, one of the questions was                               Is factoring in P? One of the most inter...

  Great news out of the Simons Institute. The Simons Foundation has ensured a second decade of research and innovation for the Simons Insti...

  1) Contrast the following two points and, if you have an intelligent way to fill-in-the-blank for the second one, please comment. a) When ...

This is a non-partisan post. Even so:  I plan to vote for Joe Biden. (Lance says that whenever I write `this is a non-partisan post'  it...

When teaching discrete math a while back I told the following story which some had already heard in High School:  When Gauss was in 1st g...

Norbert Weiner wrote a paper  Some Moral and Technical Consequences of Automation  in 1960. It warns of the dangers of computers in two ways...

The Complexity Complexity Conference , the conference that shares its name and URL with this blog, originally scheduled for Saarbrücken will...

(All of the math in this post is summarized (without proofs) in a writeup by Erik Metz and myself which you can find  here . It is a pdf fil...

To Honor Ronald Graham I summarize the blog posts we had about his work. 1) Blog post  New Ramsey Result that will be hard to verify but R...

Ronald Graham passed away on July 6 at the age of 84. We present reflections on Ronald Graham by  Steve Butler. Getting to work with...

In  this post  I speculated on why I could not find anywhere a table of which cases of Hilbert's 10th problem were solvable, unsolvable,...

I was re-watching the  Greatest-of-all-time Jeopardy championship and the following happen (I paraphrase) ---------------------- Alex Tr...