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
Goodstein Sequences (Its his 100th birthday!)
LANCE: Bill, on Dec 15, 2012 it will be Reuben Goodstein's 100th birthday. BILL: Is he still alive? Will there be a conference in his honor? Free Food? Cake? ...
From Computational Complexity
Book review column
(I am a bit behind on posting links to my book review column- this blog post is about the Third (of four) for the year 2012, and the fourth of four has alreadyhere...
From Computational Complexity
Where is the youth of TCS/questions on Nash Eq (guest post by VJ)
(Guest post by Vijay Vazirani.) On Theory Day on Nov 30, 2012 Vijay Vazarani gave a talk: New (Practical) Complementary Pivot Algorithms for Market Equilibrium...
From Computational Complexity
Inverse Closure Problem
In the undergraduate complexity course we spend some time on closure properties such as (1) REG closed under UNION, INTER, COMP and (2) R.E. closed under UNION...
From Computational Complexity
If GASARCH Tweeted what would he tweet?
If I tweeted this is what I would tweet: The problem with trying to predict who will win the election. Prez election thought: if you run as yourself and lose (Stevenson...
From Computational Complexity
Andrew Goldberg guest blog on new max flow result
Guest Blog by Andrew Goldberg on the recent Max Flow in O(nm) time algorithm. Maximum Flow in O(nm) Time Recently, Jim Orlin published an O(nm) maximum flow algorithm...
From Computational Complexity
Random thoughts on the election
Neither Lance and I have commented much on the Prez election. I only found one post from 2012 that mentioned Romney: Romney vs Aaronson. A few mentioned Obama but...
From Computational Complexity
Planarizing Gadgets for Perfect Matching do not Exist!
At Dagstuhl I was delighted when I saw the title of a talk to be given Planarizing Gadgets for Perfect Matching do not Exist because I had asked the question about...
From Computational Complexity
Theory Day. How to get the word out on this and other events?
Aravind asked me to post on this again (NOTE- registration-for-free deadline is TOMMOROW!!!!!) The University of Maryland at College park is having a Theory Day...
From Computational Complexity
Cruel XOR unusual Punishment
(This post was done with the help of Lane Hemaspaandra and John Purtilo.) The 8th amendment of the US Constitution states Excessive bail shall not be required...
From Computational Complexity
Quantum Workshop
I went to the QIS workshop on quantum computing which was on the College Park Campus. I went Thursday (reception- free food!) and Friday (free lunch!) but had...
From Computational Complexity
A new kind of Spam
(In this post I quote attempted posts to the blog. I transcribe them as they are, so if you see a missing period or awkward language, its not me (this time) its...
From Computational Complexity
Imagining Imaginary Probabilities
In the year 4000BC my great-great-...-great grandmother tried to solve (in today's terms) the equation x2 + 2x + 2 = 0 She discovered that if it had a solution...
From Computational Complexity
Some quantum Stuff
Two quantum announcements (emailed to me by Umesh Vazirani, and produced here almost exactly) and then some thoughts of mine quantum computing. Announcement one...
From Computational Complexity
Theory Day at UMCP Oct 24
The University of Maryland at College park is having a Theory Day on Wed Oct 24! Come hear Distinguished talks by Julia Chuzhoy and Venkataesan Guruswami! Short...
From Computational Complexity
Should we learn from the Masters or from the Pupils?
The following is a paraphrase of a comment at the end of the Suggested Readings section of Spivak's calculus book: Abel remarked that he attributed his profound...
From Computational Complexity
Neil Armstrong, Ray Bradbury: The future is not what we thought it would be
Neil Armstrong died on August 25, 2012. He was the first man to walk on the moon. (Since they always say this I wonder if Women walked on the moon earlierRay ...
From Computational Complexity
Fellow blogger Abie Flaxma named Top Innovator!
(Guest post from William Heisel, Assistant Director for External Relations, Institute for Health Metrics and Evaluation, University of Washington, 2301 5th Avenue...
From Computational Complexity
Book Review Column (a bit late)
I try to post my book review column when it comes out but I am behind on that. This is the one that came out a few months ago. The column is here though I have...
From Computational Complexity