Refine your search:

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...

From Computational Complexity
#### Quantum Supremacy: A Guest Post by Abhinav Deshpande

I am delighted to introduce youto Abhinav Deshpande, who is a graduate student at the University of Maryland, studying Quantum Computing. This will be a guest post...

From Computational Complexity
#### Richard Guy is 102 years old today

Richard Guy is a mathematician. He co-authored the classic book Winning Ways for your Mathematical Plays with Elywn Berlekamp and John Conway.
On Sept 30 (today)...

From Computational Complexity
#### Applicants to Grad School are too good. Here is why this might be a problem.

Sitting around with three faculty we had the following conversation
ALICE: When I applied to grad school in 1980 they saw a strong math major (that is, I had good...

From Computational Complexity
#### this paper from 2015 cracks Diffie-Hellman. What to tell the students?

I am teaching cryptography this semester for the second time (I taught it in Fall 2019) and will soon tell the students about the paper from 2015:
Imperfect Forward...

From Computational Complexity
#### Random non-partisan thoughts on the Prez Election

This post is non-partisan, but in the interest of full disclosure I disclose that I will almost surely be voting for the Democratic Nominee. And I say almost surely...

From Computational Complexity
#### Are there any natural problems complete for NP INTER TALLY? NP INTER SPARSE?

Recall:
A is a tally set if A ⊆ 1*.
A is a sparse set if there is a polynomial p such that the number of strings of length n is ≤ p(n).
If there existsthis...

From Computational Complexity
#### Can Mathematicians Fix Iphones? Can anyone?

In my last post I noted that if I am asked (since I am a CS prof)
Can you fix my iphone
is
No, I work on the math side of CS
Some readers emailed me (I told...

From Computational Complexity
#### `Are you a math genius?' `Can you fix my Iphone?' `What do you think about Facebook and Privacy?'

When I meet non-math people and tell them I am a computer science professor I get a range of responses. Here are some and my responses.
1) Are you a math genius...

From Computational Complexity
#### Obstacles to improving Classical Factoring Algorithms

In Samuel Wagstaff's excellent book The Joy of Factoring (see here for a review) there is a discussion towards the end about why factoring algorithms have not made...