acm-header
Sign In

Communications of the ACM

Blogroll


bg-corner

From Computational Complexity

My comments on Lance's Favorite Theorems

In Lance's last post (see here) he listed his favorite theorems from 1965 to 2024.There are roughly 60 Theorems. I mostly agree with his choices and omissions.here...

From Computational Complexity

Conway's Trick for Divisibility. Asking its complexity is an odd question.

 (I got this material from a nice article by Arthur Benjamin here.)  Conway suggested the following trick to determine if a number is divisible by each of the following...

From Computational Complexity

For what d is the following true: For all 2-colorings of \(R^d\) has a mono unit square (Answering(?) the Question)

 In my last post (see here) I invited you to work on the following question:Find a \(d\) such that--There is a 2-coloring of \(R^d\) with no mono unit square.--For...

From Computational Complexity

For what d is the following true: for all 2-colorings of \(R^d\) there is a mono unit square (Asking the Question)

 In this post I give a question for you to think about. My next post will have the answer and the proof. 1) The following are known and I have a set of slides about...

From Computational Complexity

A new Mersenne Prime Has Been Found. When will we find the next one?

  (Lance posted on the search for Mersenne primes in 2006 after a new one was discovered. I will comment on his post later.) A Mersenne Prime is a prime of thehere...

From Computational Complexity

Random Thoughts on the Election

 Here are my random thoughts on the election:1) Here is a list of things I DONT care about a) Candidates Gender or Race. The people who say its about time we had...

From Computational Complexity

Contrast an Episode of Columbo with the recent Nobel Prizes

 I quote Lance's blog post (here) about Computing and the Nobelsa) On Wednesday October 9th half of the Chemistry Nobel was awarded to computer scientists Demis...

From Computational Complexity

A Trip Down Memory Lane: Desc comp, Constant Round Sorting, Division Breakthrough, Derandomization.

I  came across (by accident) the link to all of the BEATCS complexity columns from 1987 to the 2016. See HERE. (If you know a link to a more recent webpage then...

From Computational Complexity

Emil Post Anticipated (more than anticipated) Godel and Turing

 (Thanks to James De Santis for pointing the article that inspired this post on Post. The article is pointed to in this post.) What is Emil Post known for? I know...

From Computational Complexity

Progress on R(5). Will there be more?

 (I had a post a while back requesting people to submit open problems in Luca Trevisan's honor with deadline Oct 1. I am extending that to Oct 14, but that is a...

From Computational Complexity

I thought I knew what pizza was...

 On Page 75 of The Existential Theory of the Reals as a Complexity Class: A Compendiumby Marcus Schaefer, Jean Cardinal, Tillmann Mitzow(see here for the paper)...

From Computational Complexity

How will chatGPT affect Homework?

LANCE: I gave my final exam for my ugrad theory course (regular, Context Free, P, NP, Decidable, Undecidable) to the new ChatGPT o1 that claims to reason aboutdo...

From Computational Complexity

Very few problems are in NP intersect coNP but not known to be in P. What to make of that?

Someone once told me: I was not surprised when Linear Programming was in P since it was already in \(  NP \cap  coNP  \), and problems in that intersection tend...

From Computational Complexity

Six degrees of separation has been proven. Really?

There is a paper (see here for an article about the paper, the link to the paper itself is later) that claims to PROVE that, on average, the distance (for someMy...

From Computational Complexity

Whats worse for a company: being hacked or having technical difficulties? I would have thought being hacked but...

At the Trump-Musk interview:1) There were technical difficulties which caused it to start late and have some other problems.2) Musk and (I think) Trump claimedhere...

From Computational Complexity

Request open problems in honor of Luca Trevisan

 Request for Open Problems In Memory of Luca TrevisanLuca Trevisan passed away on June 19, 2024 at the age of 52, of cancer.I am putting together an open problems...

From Computational Complexity

The combinatorics of Game Shows

 (Inspired by Pat Sajak stepping down from Wheel of Fortune)How many different game show are there? Many. How many could there be?1) Based on Knowledge or something...

From Computational Complexity

Determing which math problems are hard is a hard problem

 I was wondering what the hardest math problems were, and how to define it. So I googled Hardest Math ProblemsThe first hit is here. The 10 problems given there...

From Computational Complexity

In the future we will all have songs written about us, and it will be Lance's fault.

In response to my blog post about how its easier to FIND novelty songs (and other things) than it used to be (see here) Lance showed how easy it is to CREATE ahere...

From Computational Complexity

FLT solution annouement had its 31's anniv was about a month ago. Some poems about FLT NOT from ChatGPT

On June 21, 1993, at the Issac Newton Institute for Mathematical Science, Andrew Wiles announced that he had proven Fermat's Last Theorem. That wasn't quite right...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account