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
Factorization in coNP- in other domains?
I had on an exam in my grad complexity course to show that the following set is in coNP FACT = { (n,m) : there is a factor y of n with 2 \le y \le m } The answer...
From Computational Complexity
How free is Randomness?
Matthew Green had a great post on the topic how do you know a random number generator is working. Gee, I just look at the sequence and see if it LOOKS random. ...
From Computational Complexity
How I learn a result
There is a theorem I want to learn. How do I go about it? (How do YOU go about it?) I give an example here which also leads to pointers to some mathematics ofhere...
From Computational Complexity
The answer is either 0,1, or on the board
I have heard (and later told people) that the in a math course if you don't know the answer you should guess either 0 or 1 or something on the board. This works...
From Computational Complexity
Leslie Lamport wins Turing Award!
Leslie Lamport wins Turing Award! See here for more details. Leslie did work on reliability of systems and security that (according to the article) is ACTUALLY...
From Computational Complexity
Why do we think P NE NP? (inspired by Scott's post)
Recently Scott Posted an excellent essay on reasons to think that P NE NP. This inspired me to post on the same topic. Inspired is probably the right word. Some...
From Computational Complexity
Why are there so few intemediary problems in Complexity? In Computability?
There are thousands of natural PC problems. Assuming P NE NP how many natural problems are there that are in NP-P but are NOT NPC? Some candidates are Factoring...
From Computational Complexity
When is a paper public? When is anything public?
A while back I had a paper in an intermediary stage. The version posted to my Ramsey Theory Course Website was not final. Is the paper public? I didn't think about...
From Computational Complexity
Maryland looking for a Lecturer/Who teachers your intro courses?
My chairman, Samir Khuller, asked me to post our job posting for a lecturer to my blog, so I and doing it right now. I think he overestimates the power of this...
From Computational Complexity
Superbowl underdogs and overdogs
(Stephen Colbert tells me that NFL guards their copyright of the name of the game they played on Sunday, which is why stores say they have a `big game sale on beer'...
From Computational Complexity
Contribute to the Martin Gardner Centennial
Dana Richards emailed us about a place to write how Martin Gardner influenced you. You can leave such comments here. I left a comment there, but I expand it for...
From Computational Complexity
Fermat's Last Theorem and Large Cardinals. Really!
A brilliant math ugrad at UMCP, Doug, is also a creative writer who wants to work on large cardinals. His creative writing may help him there. We had the following...
From Computational Complexity
We don't care about Ballroom Dancing. Should we?
YOU got into your undergrad school because not only were you good at Math but you were on the Fencing Team and in the Latin Club (so you could taunt your opponents...
From Computational Complexity
A short History of Crypto
I taught a 3-week summer course to High School Students called Computer Science: A Hands Off Approach which did some theory. One thing I did was the following...
From Computational Complexity
Tell me more about Alice and Bob
A while back my parents were in town on a weekend when I was scheduled to give a talk to HS students who had done well on the Maryland math competition. Logistics...
From Computational Complexity
Two cheers for the Pardon ot Turing. But not three.
As I am sure readers of this blog know Alan Turing was prosecuted for homosexuality in 1952, forced into hormone treatment, and committed suicide in 1954 (I had...
From Computational Complexity
Our Journal is 99 44/100 percent pure!!
Sometimes we are asked to evaluate how good a journal or conference formally(Excellent, Very Good, Good, Fair, Better-than-being-poked-by-a-stick,pass the stick)...
From Computational Complexity
Analogs between Quantum Computng and Parallelism
(Jon Katz wanted me to mention this: A wise man once noted that there are fewer quantum algorithms than thereare quantum-algorithms textbooks! But there is still...
From Computational Complexity
Inventions are Non-Communative: Amarzon vs Amarzon
(Tal Rabin, Shubhangi Saraf and Lisa Zhang asked me to remind you to publicize this: the bi-annual Women in theory (WIT workshop), NYC, May 28-30, 2014. Apps due...
From Computational Complexity