Sign In

Communications of the ACM

Blogroll



From Computational Complexity

Do any NP-reductions use deep mathematics? Non-rhetically

BILL: Lets say we didn't know that FACTORING NPC --> NP=coNP.then what direction would we think Factoring in P or NPC?  STUDENT: In P. After all, Number Theory...

From Computational Complexity

The key to my Taylor series problem: Buddy can you spare a penny, nickel, dime, or quarter

 In my last blog post I posed a question about finding the coeff of x^100 in a particular Taylor Series. The question and answer are given  here:The key to the...

From Computational Complexity

A Taylor Series Problem

 I post a problem today and its solution on Thursday.Comments are fine, though if you don't want to get a hint, don't read them. Find the coefficient of x100 in...

From Computational Complexity

I didn't understand The Art Market before the NFT sale, and I understand it less now

 (This post is a sequel to my post from Feb 13, 2007 which you can find here. While the gap from 2007 until 2021 seems large, its not as long as the gap between...

From Computational Complexity

When do I need to warn about Spoilers?

In a recent post here I mentioned in passing a plot point from the last season of The Big Bang Theory. Note that the last season was in 2019.  WARNING- do not read...

From Computational Complexity

Using number-of-PhD's as a measure of smartness is stupid.

In Thor:Ragnorak Bruce Banner mentions that he has 7 PhDs. Gee, I wonder how he managed to slip that into a conversation casually.  Later in the movie:Bruce: IDouble...

From Computational Complexity

Good Names and Bad Names of Game Shows and theorems

 In my post on Alex Trebek, see here, I noted that Jeopardy! is not a good name for the game show since it doesn't tell you much about the show. Perhaps Answers...

From Computational Complexity

Two examples of Journalists being... Wrong. One BIG one small

 Journalists sometimes get things wrong.This is not news, but it is interesting when you KNOW they are wrong. 1) Scott Aaronson has a GREAT example regarding an...

From Computational Complexity

The Victoria Delfino Problems: an example of math problems named after a non-mathematician

 If you Google Victoria Delfino you will find that she is a real estate agent in LA (well, one of the Victoria Delfino's you find is such).  After this blog isVictoria...

From Computational Complexity

Grading policies during Covid-No easy answers

 Because of COVID  (my spellecheck says covid and Covid are not works, but COVID is) various schools have done various things to make school less traumatic. Students...

From Computational Complexity

Answers to the Prez Quiz, and some interesting history

I posted a presidential quiz (that is, a quiz about presidents, not a quiz that is so majestic it can be called presidential) on Thursday Jan 21.Here is the link...

From Computational Complexity

Presidential Quiz: Three ways to take it

 Every four years around the time of the inaugural I post a presidential Quiz! I do that today, and I will post the answers on Monday.  I am tempted to joke that...

From Computational Complexity

The ACM History Committee call for proposals looks wrong

 In November I (and prob everyone in the ACM) got an email that was a call for proposal from the ACM History committee. Here is a pointer to it. One of the passages...

From Computational Complexity

My Survey on Hilbert's 10th for particular (d,n) is ready for you to help me on!

 Hilbert's 10th problem is  (in modern terminology) to find an algorithm that will, given a poly p(x1,...,xn) in Z[x1,...,xn], determine if it has a solution in...

From Computational Complexity

Dr Jill Biden

(I was helped on this post by Gorjan Alagic, Andrew Childs,  Tom Goldstein, Daniel Gottsman, Clyde Kruskal,  Jon Katz. I emailed them for their thoughts on thehere...

From Computational Complexity

Quarterly Th. Wksp `at' Northwestern, and thoughts inspired by it

 On the Northwestern CS Theory Group there is a set of Quarterly Theory Workshops. There is one coming up on Dec 17-18, 2020, called the Junior Theorists Workshop...

From Computational Complexity

In 1974 Planarity was O(V) time and could do 900 node graphs in 12 seconds! Fast then...

In 1974  Hopcroft and Tarjan showed that Planarity is in polynomial time. That is an understatement- they actually have an O(V) algorithm which one can actually...

From Computational Complexity

James Randi, Magicians-Author-Skeptic, passed away at the age of 92

James The Amazing Randi died on October 20, 2020, at the age of 92. He is survived byhis husband Jose Alvarez.  His Wikipedia page is here A few Randi Points: 0)...

From Computational Complexity

Fun with birthdays, inspired by Nov 20

 On Nov 20, 2020  the Google Doodle was of Benoit Mandelbrot for his 96th birthday. Why have a Doodle on his 96th bday? Anyway, the Doodle is here.  On Nov 20,here...

From Computational Complexity

Alex Trebek/What is today's post about?

 Alex Trebek, long time host of the TV show Jeopardy! (the exclamation point is part of the name, though I will omit it for the rest of the post), passed away in...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account