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
Types of questions for exams
QUESTION: Give as many types of exam questions you can, give examples, and comment on if this is a good type of question. My answer below. A problem that some...
From Computational Complexity
What are Galois Games?
How are math concepts named? After the people who was involved with it. Examples: The Cook-Levin Theorem, Goldbach Conjecture, Ehrenfeucht-Fraisse games, Banach...
From Computational Complexity
When Lance was 10 years old..
In honor of Lance's 50th birthday I ask the following: When Lance was 10 years old which of the following were true? (Disclosure- some of the below are from a birthday...
From Computational Complexity
How much Trig does your governor know?
How much math should our public officials know? Basic probability and statistics so they can follow the arguments that their science advisers give them. And they...
From Computational Complexity
Longest time between posing a math problem and it being answered?
(We were asked to remind you: ITCS 2014 Call for papers: call for papers.) What problem in math had the longest time between POSING IT and SOLVING it? This might...
From Computational Complexity
Certifying primality in a CONSTANT number of operations
For this post I will only count the operations PLUS, MINUS, MULT. They may be done on rather large numbers. Recall that from the work coming out of Hilberts 10th...
From Computational Complexity
I gave a poster session at Erdos 100- so how did it go?
In a a prior post I suggested that STOC perhaps have people give posters instead of talks. While I doubt this will ever happen I think its worth thinking about,...
From Computational Complexity
A(nother) nice use of Gen Functions
In a prior post I tried to give a simple example of a proof that uses Gen Functions where there was no other way to do it. For better or worse, before I posted...
From Computational Complexity
DUMP YOUR TABLES! (the moral of my story that started with a hat problem)
Recall from my last post: PROBLEM 1: There are n people sitting on chairs in a row. Call them p1,...,pn. They will soon have HATS put on their heads, RED or BLUE...
From Computational Complexity
A problem and later a story and a point.
I have (1) a math problem to tell you about (though I suspect many readers already know it), (2) a story about it, and (3) a point to make. TODAY I'll just do the...
From Computational Complexity
Combinatorics use to not get any respect. But because of Erdos...
(This blog is based on things I heard at the Erdos 100th Bday Conference) I have spend the last week at the Erdos 100th bday conference. One point that was made...
From Computational Complexity
Quantum Tecniques/Gen Functions- don't be afraid of new techniques
Ronald de Wolf gave a GREAT talk at CCC on the uses of Quantum techniques to Classical Problems. He made the analogy of using the Prob Method to prove non-prob...
From Computational Complexity
Fraud or not ?
For each of these, are they frauds? The Turk was a chess playing ``computer'' (around 1770) that was later discovered to be cheating--- a human made the moves...
From Computational Complexity
STOC: Some NON-radical ideas
At the STOC business meeting Joan Feigenbaum (PC chair) raised some very good points. There was no real discussion (or perhaps the burning car was the discussion)...
From Computational Complexity
Do you KNOW how you KNOW what you KNOW? I don't KNOW.
When watching Jeopardy with Darling if I get a question correct that is NOT in my usual store of knowledge (that is NOT Ramsey Theory, NOT Vice Presidents, NOTHow...
From Computational Complexity
Mother's Day Math
Problem: On Mothers day (May 12 this year) restaurants are very crowded because many people take their mothers, grandmothers, great-grandmothers, etc out to lunch...
From Computational Complexity
Are you smarter than a fifth grader? I'm not.
My darling sometimes watches TV in the middle of the night when she can't sleep.So I found myself watching (actually listening) to the quiz show Are You Smarter...
From Computational Complexity
Computer Assisted Proofs- still controversial?
Kenneth Appel, of Appel-Haken Four Color Theorem Fame, died recently. See here for an obit. In 1972 I read that the four-color theorem was an open problem.here...
From Computational Complexity
Oh, I remember/recorded/DVRed it well
You can now wear a device, Memoto that will take a picture every 30 seconds. Do you really have a Kodak Moment every 30 seconds? No, but this way when you do have...
From Computational Complexity