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
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
Sizes of DFAs, NFAs, DPDAs, UCFG, CFGs, CSLs.
If A is a decider (e.g, DFA) or generator (e.g., CFG) then L(A) is the language that it decides or generates. The following are well known: L(DFA) = L(NDFA)...
From Computational Complexity
Advice on running a theory day
Last semester I ran a THEORY DAY AT UMCP. Below I have ADVICE for people running theory days. Some I did, some I didn't do but wish I did, and some are just questions...
From Computational Complexity
The New Oracle Result! The new circuit result! which do you care about?
You have likely heard of the new result by Ben Roco, and Li-Yang on random oracles (see here for preprint) from either Lance or Scott or some other source: Lance's...
From Computational Complexity
Two cutoffs about Warings problem for cubes
Known: All numbers except 23 can be written as the sum of 8 cubes All but a finite number of numbers can be written as the sum of 7 cubes There are an infinite...
From Computational Complexity