Refine your search:

From Computational Complexity
#### Awesome Video from Women In Theory!

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 Theory Workshop that was...

From Computational Complexity
#### Why is there no (d,n) grid for Hilbert's Tenth Problem?

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

From Computational Complexity
#### A Guest Blog on the Pandemic's affect on disability students

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, with the intend of making...

From Computational Complexity
#### John Conway Dies of Coronvirus

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 of it. I suspect this is...

From Computational Complexity
#### Length of Descriptions for DFA, NFA, CFG

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 in Chomsky Normal Form. Sohere...

From Computational Complexity
#### What do do while ``stuck'' at home/Other thoughts on the virus

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 here.
I will add to it, and...

From Computational Complexity
#### Richard Guy passed away at the age of 103

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 list of centenarians who...

From Computational Complexity
#### Theorist Paul R Young passed away

In the early days of theoretical computer science, say 1960-1990 the main tools used were logic.
This made sense since, early on:
a) Some of the basic notionspassed...

From Computational Complexity
#### Logic examples for your Discrete Math class

(I injured my hand about a month ago so I have had a hard time typing. That is why
I have not blogged for a while. I'm better now but still slow. This is a post...

From Computational Complexity
#### What would you do if you showed P=NP? I would reread Factor Man by Matt Ginsberg

Lance has often said (and also in this) that if P=NP that would be great for the world: much more efficient ways to build things, science could be done better,Factor...

From Computational Complexity
#### The Wikipedia Entry on NP-Intermediary Problems lists one of mine! I'm not bragging about it.

I recently needed to look at what NP problems were possibly intermediary (neither in P nor NP-complete). So I went to Wikipedia and found this.
They had many problems...

From Computational Complexity
#### Why is there no all-encompassing term for a course on Models of Computation?

In my last blog post I asked my readers to leave comments saying what the name of the course that has some of Regular Languages, Context Free Languages Decideability...

From Computational Complexity
#### What do you call your ugrad non-algorithms theory course?

I am in the process of reviewing What can be computed: A Practical Guide to the Theory of Computation by John MacCormick and I need YOUR help for the first SENTENCE...

From Computational Complexity
#### Julia Robinson's 100th birthday

On Dec 8, 1919 Julia Robinson was born, so today is here 100th birthday (she passed away at
the age of 65 on July 30, 1985).
So time for some facts about her...

From Computational Complexity
#### Fields used to be closer together than they are now. Good? Bad?

There was a retired software Eng professor that I had heard two very non-controversial rumors about:
1) He got his PhD in Numerical Analysis
2) He got his PhD...

From Computational Complexity
#### A non-moral dilemma about cheating, but it brings up some points

I often give two versions of an exam and TELL THE STUDENTS I am doing this so that they don't even try to cheat. I've even had two different classes take the midterm...

From Computational Complexity
#### Differentiation and Integration

Recently there was an excellent xkcd about differentiation and integration, see here.
This brings up thoughts on diff and int:
1) For some students Integration...

From Computational Complexity
#### The Sheldon Conjecture (too late for Problems with a Point)

Chapter 5 of Problems with a Point (by Gasarch and Kruskal) is about how mathematical objects get their names. If it was an e-book that I could edit and add to...

From Computational Complexity
#### William Kruskal's 100th birthday

Today, Oct 10, 2019 is William Kruskal's 100th birthday (he's dead, so no cake. Oh well.) William Kruskal was a great statistician. To honor him we have a guest...

From Computational Complexity
#### What comes first theory or practice? Its Complicated!

Having majored in pure math I had the impression that usually the theory comes first and then someone works out something to work in practice. While this is true...