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
Two candidates that I want to see run for Democratic Nomination
It has been noted that while there are 17 Republican candidates for the nomination, of which 10 have been declared serious by FOX News via the first debate, there...
From Computational Complexity
Interesting properties of the number 24 on someone's 24th wedding anniversary
The story you are about to read is true. Only the names have been changed to protect the innocent. The Alice and Bob below are not the crypto Alice and Bob. -...
From Computational Complexity
Have we made Progress on P vs NP?
While teaching P vs NP in my class Elementary Theory of Computation (Finite Automata, CFG's, P-NP, Dec-undecid) I was asked What progress has been made on P vs...
From Computational Complexity
Ways to deal with the growing number of CS majors.
(Univ of MD at College Park is looking to hire a Comp Sci Lecturer. Here is the link: HERE) Univ of MD at College Park will have 2100 students in the CS program...
From Computational Complexity
How hard would this cipher be for Eve to crack?
I've been looking at old ciphers since I am teaching a HS course on Crypto. We've done shift, affine, matrix, Playfair, 1-time pad, Vigenere, and then noting that...
From Computational Complexity
17 candidates, only 10 in the debate- what to do?
On Thursday Aug 6 there will be Republican debate among 10 of the 17 (yes 17) candidates for the republican nomination.1) There are 17 candidates. Here is how I...
From Computational Complexity
Explain this Scenario in Jeapardy and some more thoughts
In the last post I had the following scenario: Larry, Moe, and Curly are on Jeopardy. Going into Final Jeopardy: Larry has $50,000, Moe has $10,000, Curly has...
From Computational Complexity
Explain this Scenario on Jeapardy
Ponder the following: Larry, Moe, and Curly are on Jeapardy. Going into Final Jeapardy: Larry has $50,000, Moe has $10,000, Curly has $10,000 Larry bets $29...
From Computational Complexity
Hartley Rogers, Author of the first Textbook on Recursion Theory, passes away
Hartley Rogers Jr passed away on July 17, 2015 (last week Friday as I write this).He was 89 and passed peacefully.For our community Rogers is probably best known...
From Computational Complexity
Is there an easier proof? A less messy proof?
Consider the following statement: BEGIN STATEMENT: For all a,b,c, the equations x + y + z = a x2 +y2 + z2 = b x3 + y3 + z3 = c has a unique solution (uphere...
From Computational Complexity
Does Bob Deserve the lavish acknowledgement: A problem in Logic
Alice and Carol are real mathematicians. Bob is an English major who does not know any mathematics. (This story is based on a true incident.) Alice writesI...
From Computational Complexity
When do we care about small improvements?
A while back complexity blog, Shtetl-optimized , and GLL all blogged about the improved matrix mult algorithms (Complexityblog: here, Shtetl-optimized: here,here...
From Computational Complexity
Learning from teaching a HS student Schur's theorem on change
(All the math this post refers to is in my manuscript which is here.) Recall Schur's theorem on making change as stated in wikipedia and other source: Let a1...
From Computational Complexity
First issue of SIGACT news where I wasn't the editor. But...
I posted at some earlier time that I was resigning from the editorship of SIGACT NEWS book review column, and handing the reins over to Fred Green (who is older...
From Computational Complexity
The city where the book publishers resides is Funkytown!
A while back when I got back the galleys for a paper the publisher wanted to know the complete postal address of one of the co-authors and also the city where...
From Computational Complexity
Langs with provably bigger CFG's then CSG's
In a prior blog entry HERE I discussed very large differences in the size of machines. I didn't discuss CFG vs CSG so I'll do that now. We assume that the CFGs...
From Computational Complexity
Who wins this bet?
Alice and Bob are at an auction and Alice wants to buy an encyclopedia set from 1980. Bob says don't buy that, you'll never use it. In this age of Wikipedia and...
From Computational Complexity
An Intentional and an Unintentional teaching experiment regarding proving the number of primes is infinite.
I taught Discrete Math Honors this semester. Two of the days were cancelled entirely because of snow (the entire school was closed) and four more I couldn't make...
From Computational Complexity
The law of the excluded middle of the road republicans
In the book Hail to the Chiefs about the presidents, when pointing to a race between two people who had no business being president (I think it was Franklin Pierce...
From Computational Complexity