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
Are perfect numbers bigger than 6 initial sums of odd cubes?
I pose two questions today (Monday April 4). I will post the answers tomorrow (Tuesday April 5). Feel free to comment about the answers. If you don't want clues...
From Computational Complexity
Hillary Putnam passed away on March 13
Hillary Putnam passed away on March 13, 2016. Some of the obits say he was a philosopher, mathematician, logician, and computer scientist. He is probably best...
From Computational Complexity
On Phillip Rogaway's The Moral Character of Cryptographic Work.
Some people have emailed me asking me to blog about the paper The Moral Character of Cryptographic Work by Phillip Rogaway I urge you to read it, even if you disagree...
From Computational Complexity
When do we care about the constants?
I've been reading two books recently: Asymptopia by Joel Spencer (He turns 70 soon! Workshop for it!. My nephew things that celebrating your bday with a workshop...
From Computational Complexity
It works in practice, but does it work in theory (Pollard's Factorization algorithm)
Throughout this post I ignore polylog factors. It is trivial to factor N in time N1/2. Pollard's rho-algorithm (see my write up here or Wikipedia Entry) for...
From Computational Complexity
What is a `previous publication'?
Here are the guidelines about submission to STOC 2015 with regard to submitting a prior published paper. I assume that most of the Theory Conferences have a similar...
From Computational Complexity
∑{p≤ n} 1/p = ln(ln(n)) + o(1). read it here because....
(Last April fools day I posted four links to stories that seemed absurd and asked which one was false. They all were true. I recently came across five stories...
From Computational Complexity
Test of Time Award- a good idea but...
The ESA Conference (European Symposium on Algorithms) has a test-of-time award which recognizes outstanding papers in algorithms research that were published in...
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