Sign In

Communications of the ACM

Blogroll



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

From Computational Complexity

Turing to be on the Bank of England 50 pound note, giving me an excuse to talk about Turing

BILL: Darling, guess who is soon going to be on the Bank of England 50 pound note? DARLING: Alan Turing. BILL: How did you deduce that? (She is right, see here...

From Computational Complexity

Answer to both Infinite Hats Problems from the last post

(This is a joint post with David Marcus. You'll see why later.) In a prior I posed two infinite hat problems. Today I post the solutions. Actually this is a....

From Computational Complexity

Guest post by Samir Khuller on attending The TCS Women 2019 meeting

(I will post the solution to the problem in the last blog later in the week---probably Thursday. Meanwhile, enjoy these thoughts from Samir Khuller on the TCShere...

From Computational Complexity

Two infinite hat problem and a question about what is ``well known''

This is a joint post with David Marcus. You will see how he is involved in my next post. Two infinite hat problems based on one scenario. I am also curious if...

From Computational Complexity

Fortran is underated!

(Joint Post with David Marcus who was a classmate of mine at SUNY Stony Brook [now called Stony Brook University]. I was class of 1980, he was class of 1979. We...

From Computational Complexity

A proof that 22/7 - pi > 0 and more

My father was a High School English teacher who did not know much math. As I was going off to college, intending to major in math, he gave me the following sage...

From Computational Complexity

Are you smarter than a 5th grade amoeba?

(title of this blog is due to Henry Baker who posted an article about this elsewhere) Amoeba finds approx solution to TSP in linear time:here. Over the yearshere...

From Computational Complexity

Why does the Nevalina Prize (now Abacus) got to Algorithms/Complexity people

In my post about the Nevanlinna prize  name change (see here) one of my readers raised a different question about the prize: BEGIN QUOTE So there's one of...

From Computational Complexity

Ray Miller, one of our founders, Passes away at the age of 90

Ray Miller, one of the founders of our field, passed away recently at the age of 90. He has associations with both GA Tech and The University of Maryland, so both...

From Computational Complexity

IMU's non-controversial changing the name of the Nevanlinna Prize

(I want to thank Alexander Soifer for supplying me with some of the documents I point to in this post. We should all thank him for getting the ball rolling on changing...

From Computational Complexity

separating fact from fiction with the 56% of Americans say Arabic Numerals should not be taught in school

On the excellent TV show Veep there was a subplot about a political candidate (who himself had failed algebra in HS) objecting to Algebra since it was invented...

From Computational Complexity

Notorious L.A.H or Notorious LAH? OR You always need one more proofread

I noticed a while back that even on the nth proofread of a document there are still corrections. So I decided to keep track of how many corrections there are in...

From Computational Complexity

Ronald Graham's other large number. Well---- it was large in 1964 anyway.

Graham's number (see here) was at one time the largest number to appear in a math proof. a) GN was an upper bound on a problem in Ramsey theory. There are nowhere...

From Computational Complexity

Thoughts on the recent Jeopardy streak (SPOILERS)

James Holzhauer  has won 22 consecutive games of Jeopardy and has made around 1.6 million dollars. Nice work if you can get it. Here are some thoughts no this 1)...

From Computational Complexity

x3 + y3 + z3 = 33 has a solution in Z. And its big!

Consider the following problem: Given k, a natural number, determine if there exists x,y,z INTEGERS such that x3+y3+z3=k. It is not obvious that this problemHuisman...

From Computational Complexity

Quiz Show Scandals/Admissions Scandal/Stormy Daniels/Beer names:being a lawyer would drive me nuts!!!!!!

0) Charles van Doren (see here) passed away recently. For those who don't know he he was (prob most of you) he was one of the contestants involved in RIGGED quiz...

From Computational Complexity

Good article, terrible headline

About a month ago (after my P NP poll appeared) I got email from Jacob Aron asking me some questions about it. One thing he was excited about was that the number...

From Computational Complexity

Elwyn Berlekamp Died April 9, 2019

Elwyn R. Berlekamp entered this world on Sept 6, 1940, and left it on April 9, 2019.  Wikipedia calls him An American Mathematician which seems to narrow to me....

From Computational Complexity

Problems with a point- NOT a plug, just some thoughts on books and book writing

Problems with a Point: Exploring Math and Computer Science by Gasarch and Kruskal, available on amazon here, came out a while back  and I plugged it in my  blog...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account