Communications of the ACM
Refine your search:
How the “Frontier” Became the Slogan of Uncontrolled AI
Artificial intelligence (AI) has been billed as the next frontier of humanity: the newly available expanse whose exploration …
From Computational Complexity
Juris Hartmanis passed away on July 29 at the age of 94
Juris Hartmanis, one of the founders of Complexity Theory, passed away on July 29 at the age of 94. The Gödel's Last Letter blog has an obit posted here. When...
From Computational Complexity
100 Best Number Theory books of all Time---except many are not on Number Theory
I was recently emailed this link: 100 Best Number Theory books of all Time That sounds like a good list to have! But then I looked at it. The issue IS NOT that...
From Computational Complexity
What is known about that sequence
In my last post I wrote:---------------------------Consider the recurrencea_1=1for all n\ge 2, a_n = a_{n-1} + a_{n/2}.For which M does this recurrence have infinitely...
From Computational Complexity
An open question about a sequence mod M.
In this post n/2 means floor{n/2}Consider the recurrencea_1=1for all n\ge 2, a_n = a_{n-1} + a_{n/2}.For which M does this recurrence have infinitely many n such...
From Computational Complexity
Review of The Engines of Cognition: Essays From the LessWrong Forum/Meta question about posts
A while back I reviewed A Map that Reflects the Territory which is a collection of essays posted on the lesswrong forum. My review is here. I posted it to both...
From Computational Complexity
Counting the Number of 3-colorings of a graph is Sharp-P complete. This should be better known.
BILL: Lance, is #3COL #P complete? (#3COL is: Given a graph G, return the number of different 3-colorings it has.) LANCE: Surely you know that for all naturalnatural...
From Computational Complexity
Guest post by Prahalad Rajkumar: advice for grad students
I suspect that Lance and/or I have had blogs giving advice to grad students. I won't point to any particular posts since that's a hard thing to search for. However...
From Computational Complexity
I am surprised that the Shortest Vector Problem is not known to be NP-hard, but perhaps I am wrong
A lattice L in R^n is a discrete subgroup of R^n. Let p IN [1,infinty)The p-norm of a vector x=(x_1,...,x_n) IN R^n is here...
From Computational Complexity
Does the Social Media Law in Texas affect theory bloggers?
A new law in Texas states that any social media sites that has at least 50 million subscribers a month cannot ban anyone (its more nuanced than that, but that's...
From Computational Complexity
Discussions I wish we were having
1) Democrats think the best way to avoid school shootings (and other problems with guns) is to have regulations on Guns. They have proposed legislation. The Republicans...
From Computational Complexity
In the 1960's students protested the Vietnam war!/In 1830 students protested... Math?
I was at SUNY Stonybrook for college 1976-1980. I remember one student protest about a change to the calendar that (I think) would have us go home for winter break...
From Computational Complexity
Is Kamala Harris our first female PREZ? No. Do I have a theorem named after me. No. But in both cases...
On Nov 19, 2021 Joe Biden got a colonoscopy and hence the 25th amendment was used to make Kamala Harris the president temporarily (this source: here says 85 minutes...
From Computational Complexity
Queen Elizabeth is the 3rd longest reigning monarch; The problem with definitions
A few days ago Queen Elizabeth passed Johann II of Liechtenstein to be the third longest reigning monarch (see here). A summary of the top 4:4) Johann II, Liechtenstein...
From Computational Complexity
Elon Musk To Buy Complexityblog
Elon Musk has offered to buy out Complexityblog. The money is too good to turn down. As part of the contract we can't say how much or in what cryptocurrency, but...
From Computational Complexity
The Roeder Problem was Solved Before I Posed it (how we missed it)
(This is a joint post with David and Tomas Harris.)In my an earlier post (see here) I discussed the MATH behind a problem that I worked on, with David and Tomas...
From Computational Complexity
1-week long Summer School for Ugrads Interested in Theory, and my comments on it
Recently a grad student in CS at UMCP emailed me the following email he got, thinking (correctly) that I should forward it to interested ugrads. --------------...
From Computational Complexity
The Roeder Seq Problems was Solved Before I Posed it (Math)
(Joint Post by Bill Gasarch, David Harris, and Tomas Harris) The divisor graph D(n) is an undirected graph withvertex set V={1,...,n}$ andedge set E={(a,b) : here...
From Computational Complexity
A Ramsey Theory Podcast: No Strangers at this Party
BILL: Lance, I am going to blog about the Ramsey Theory Podcast called No strangers at this partyLANCE: Oh, so that will be your April...
From Computational Complexity
I don't care about Ketanji Brown Jackson's LSAT scores and she does not care about my GRE scores
Tucker Carlson has asked to see Ketanji Brown Jacksons's LSATs. When I applied to College they (not sure who they are) wanted to see my SAT scores. Putting aside...
From Computational Complexity