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
A question in Formal Lang Theory about Size of Desc of Languages.
(This post is inspired by me thinking more about this blog entry and this paper.) Upper bounds on n are really O(n). Lower bounds of f(n) are really Omega(f(n))...
From Computational Complexity
Predictions for 2016
This is the first post of 2016! (that is not a factorial). Hence I will make some predictions and at the end of the year I'll see how I did 1) The USA Prez election...
From Computational Complexity
crank math and crank people
In the same week I got email claming: 1) Babai had shown that GI is in quasipoly time. 2) Opeyemi Enoch, a Nigerian Mathematician, solved the Riemann hypothesis...
From Computational Complexity
One more sign that a Journal is bogus. Or are they?
I went to an AMS conference with my High School Student Naveen (who presented this paper) and an ugrad from my REU program Nichole (who presented this paper)....
From Computational Complexity
Is the word Quantum being used properly by civilians? Understood by them? You know the answer.
I've seen the word `civilians' expanded in use from non-military to non-X for some X. Not sure I've ever seen `civilians' mean `people who don't do math stuff'...
From Computational Complexity
Looking forward to the GI result
As you all know Laszlo Babai will give a talk Tuesday Nov 10 on a result: GI in quasipolynomial time (2 to a polylog). Other theory blogs have already commented...
From Computational Complexity
Computation and Journalism Part 2
The theory blogosphere is atwitter with an announcement of a talk next Tuesday at Chicago by László Babai Graph Isomorphism in Quasipolynomial Time. Luca will blog...
From Computational Complexity
Conference on Computation and Journalism (Part I)
(In honor of Boole's Birthday yesterday see this.) I recently (Oct 2 and 3 2015) went to a conference on Computation and Journalism (see here for their schedule)...
From Computational Complexity
A human-readable proof that every planar graph is 4.5-colorable
About 20 years ago I went to a talk by Jim Propp on the fractional chromatic number of a graph. (Here is a link to a free legal copy of the book on fractional graph...
From Computational Complexity
Amazon going after fake reviews but mine is still posted
I have always wondered why YELP and Amazon Reviews and other review sites work as well as they do since a company COULD flood one with false reviews (high marks...
From Computational Complexity
Moore's Law of Code Optimization
An early version of Moore's law is as follows: HARDWARE: The number of transistors on an integrated circuits doubles every 18 MONTHS. Moore's law is often used...
From Computational Complexity
Is Kim Davis also against Nonconstrutive proofs?
Recall that Kim Davis is the Kentucky clerk who refused to issue marriage licenses for same-sex couples and was cheered on by Mike Huckabee and other Republican...
From Computational Complexity
Venn Diagrams are used (yeah) but abused (boo)
In a prior blog entry I speculated about which math phrases will enter the English Language and will they be used correctly. I thought Prisoner's Dilemma would...
From Computational Complexity
When did Mathematicians realize that Fermat did not have a proof of FLT?
I recently came across the following passage which is about Fermat's Last Theorem (FLT). Pierre de Fermat had found a proof, but he did not bother to write it...
From Computational Complexity
An Open(?) Question about Prime Producting Polynomials Part II in 3-D!
(Apologies- No, this post is not in 3-D) I posted last week about An Open(?) Question about Prime Producing Polynomails I got several emails about the post with...
From Computational Complexity
An Open(?) question about prime-producing-polynomials
Known Theorem: If f(x)∈ Z[x] is prime for all nat number inputs then f(x) is a constant. NOTE- Recall that if p is a prime then so is -p. Known Proof: Assume...
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