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
Quetions that arose teaching HS students crypto
I taught a 3-week, 3-hours-a-day course to HS student titled Computer Science: A Hands Off Approach. Given that time constraints and the fact that some already...
From Computational Complexity
The n^{1/3} barrier for 2-server PIR's broken! A lesson for us all!
Recall: PIR stands for Private Information Retrieval. Here is the model: A database is an n-bit string (my wife tells me this is not true). The user wants to find...
From Computational Complexity
How I know Moneyball is a true story. Do we clean up theorems and life too much?
A few years ago I saw the movie Moneyball about how the Oakland A's used intelligent statistics to... win? No, but to do better-than-expected. Even if I didn't...
From Computational Complexity
How NOT to bet
(True Story, but names are changed for no good reason.) Alice, Bob, and Carol are betting on who will be the Republican Nominee in 2016. Alice bets on Jeb Bush...
From Computational Complexity
The Change Problem and the Gap between Recreational and Serious Mathematics
In a prior post (here)I discussed the change problem: given a dollar, how many ways can you make change using pennies, nickels, dimes, and quarters (and generalize...
From Computational Complexity
Need some book reviewed- faster than usual
I have been the SIGACT NEWS book review editor since 1997. I have tried to get about 10 books reviewed per column. I have succeeded- perhaps too well! I have gotten...
From Computational Complexity
What to call the top and bottom part of (n choose k)
In my last post I asked for candidates for names for the top and bottom part of (n choose k) . Here are the candidates and my comments on them and ... the winner...
From Computational Complexity
Is there a word for the top part of a binomial coefficient?
Consider the sequence: x/y, (x+1)/y, (x+2)/y, ..., (x+z)/y one could say in this sequence of fractions the numerators goes through z-1 consecutive numbers. ...
From Computational Complexity
3000 lunches
Last week fortune smiled on two of my friends: Ken Regan made the cover of Chess Life for his work on catching chess cheaters. (See here.) Jacob Lurie who I mentored...
From Computational Complexity
How many ways can you make change of n cents?
(For a related post see my post on Schur's theorem. The paper THIS post refers to is here.) (ADDED LATER: A commenter pointed to Graham-Knuth-Patashnik forhere...
From Computational Complexity
Ref/info request for an obvious approach to GI
Talking about Graphi Isom with some students they came up with the following idea which is certainly not new; however, I couldn't quite find much about it on the...
From Computational Complexity
Fair question? Trick question?
The following problem was on my final for Formal Lang theory (Reg, P, NP, Dec, c.e.) For this problem you may assume P\ne NP and NP\ne coNP. For each of the following...
From Computational Complexity
Do you support CCC's declaration of Ind? If so...
The steering committee for the CCC recently announced its decision to be independent of IEEE. Here is their open letter to that effect. If you agree with thishere...
From Computational Complexity
Law of small numbers and letters
The law of small numbers is that there are not enough small numbers for all of the tasks that are assigned to them. That makes some math cranks find patterns which...
From Computational Complexity
Review of People, Problems and Proofs By Lipton and Regan
(A version of this either already has or well appear in SIGACT NEWS book rev column.) A review of the blog-book PEOPLE, PROBLEMS, AND PROOFS by Richard Lipton...
From Computational Complexity
''4col \le 3col is counter-intuitive and makes me sad'' NOT ANYMORE!
In my ugrad theory class (reg,P,NP,Dec,c.e) I proved that SAT is NP-complete. In the next lecture I proved that SAT \le 3-col, so 3-col is NP-complete. I thenLeast...
From Computational Complexity
How should qualifying exams and courses work
In my last post about what Every Theory Grad Student Should know some more general questions were raised: Qualifying exams vs Course Requirements. Why do we have...
From Computational Complexity
Every Theory Grad Student should know...
This semester my Graduate Complexity Course has nine students in it. It had not been offered for two years (when it had around 20) so the demand, such as it is,...
From Computational Complexity
The Big bang Theory hits close to home
On a recent episode of The Big Bang Theory Sheldon gives up String theory because, after working on it for 20 years, he has nothing to show for his efforts. Icompactify...
From Computational Complexity