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
Math questions that come out of the Iowa Caucus
http://www.foxnews.com/politics/elections/2016/primary-caucus-results/iowa Jim Gilmore, republican, has 0% of the vote. Does that mean that literally NOBODY voted...
From Computational Complexity
When do we stop giving the original reference?
I was preparing a talk which included my result that there is a sane reduction 4-COL \le 3-COL (the paper is here) when I realized that if I am going to claim...
From Computational Complexity
Is it okay to praise an article or book in an article or book?
I recently had a paper accepted (YEAH!). The referees had some good corrections and one that puzzled me. you wrote ``our proof is similar to the one in the wonderful...
From Computational Complexity
A limit on the DFA-CFG divide for finite sets
It is easy to see that for Ln = {a,b}*a{a,b}2n There IS a CFG of size O(n) ANY DFA is of size double-exp-in-n I was wondering if we can increase this gap. That...
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