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
The 17x17 problem SOLVED! (also 18x18)
THE 17x17 PROBLEM HAS BEEN SOLVED!!!!! On Nov 30, 2009 I posted here the following challenge: If someone emails me a 4-coloring of 17x17 with no monochromatic...
From Computational Complexity
Dusting off my bookshelf I find a book on FORTRAN
The following quote is from the back of a book that I dusted off and took off of my shelf recently: FORTRAN is one of the oldest high-level languages and remains...
From Computational Complexity
A result of Specker in Recursive Combinatorics
Ernst Specker passed away in December. He has 91. He was not the oldest living mathematician. That title likely belongs to Sergey Nikolsky. A former student ofhere...
From Computational Complexity
Guest post on ITCS by Chazelle
(Requested announcement: Calling all Women PhD Students (and a few undergrads) We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton...
From Computational Complexity
Teaching an Honors Section of Discrete Mathematics
A few years ago I was assigned to teach the HONORS section of Discrete Math (a course for sophomores who have had a year of programming and a year a calculus). They...
From Computational Complexity
How important are the Fib numbers in math? in Nature? In History of Math books?
The following quotes is from In the book Algebra in Ancient and Modern Times by V.S. Varadarajan. Fibonacci numbers thus grow very fast with N, indeed in geometric...
From Computational Complexity
The Conjunction Paradox
In Yesterday's post you were told about Susan: Susan is 31 years old, single, outspoken and very bright. She majored in philosophy. As a student she was deeply...
From Computational Complexity
Rank these possibilities by probability
Readers- I want you to answer this question and post your answers as comments. I will tell you WHY I am asking tommorow. Susan is 28 years old, single, outspoken...
From Computational Complexity
Is there a NICE gadget for showing PLANAR HC is NPC?
(I have already posted this question on CS Theory Stack Exchange.) If you know that 3-COL is NPC then you can prove that PLANAR 3-COL is NPC by a NICE gadget...
From Computational Complexity
Romney vs. Aaronson
How are Mitt Romney and Scott Aaronson similar? Different? Similarities: Both live in Massachusetts. Actually, Scott lives there but its not clear where Mitt...
From Computational Complexity
Solution to the reciprocals problem
In my last blog I asked you to look at this problem, try to solve it, and tell me if you think it is too hard for a HS competition. (I meant to post this on WED...
From Computational Complexity
Is this problem too hard for a HS Math Competition
The Univ of MD HS Math Competition has two parts. Part I is 25 multiple choice questions in 2 hours (4 points for a correct answer, -2 for an incorrect answer)....
From Computational Complexity
What is a Breakthrough?
The recent discussion on Matrix Mult inspires the general question of WHAT IS A BREAKTHROUGH? Last year I tried to get an intelligent discussion on this topic but...
From Computational Complexity
Analysis of Boolean Functions blog/book (Guest post by Ryan O'Donnell)
(Guest post by Ryan O'Donnell) Lance and Bill have graciously let me plug my recently begun book/blog project, analysis of boolean functions. I am writingBoolean...
From Computational Complexity
Matrix Mult (you heard it here... third?)
(INNOVATIONS CONFERENCE: here) (While preparing this two other bloggers wrote on the same topic, Scott here and Lipton/Regan here. Our slogan: Complexity Blog...
From Computational Complexity
Are these journals real?
Consider the following email I got: Dear Professor, 1. Antarctica Journal of Mathematics 2. ArchimedesJournal of Mathematics 3. BesselJournal of Mathematics...
From Computational Complexity
My response to the Gasarch P vs NP poll
A while back GASARCH solicited responses to a P vs NP poll and gave Oct 31 as the deadline. Now that the deadline is passed I post my answers. Does P=NP? IIf...
From Computational Complexity
Theorems that are impressive at first but then....
Mission Impossible was my favorite show as a kid. As an adult it would not make my top 20, and I wonder why I liked it so much as a kid. (Actually I do know- at...
From Computational Complexity
If Bill Tweeted what would he tweet (Steve Jobs Edition)
A more nuanced view of Steve Jobs: here. A less nuanced view of Steve Jobs: here. The next Steve Jobs: here A very nice NON-Steve Jobs post here. Is thisAndrew...
From Computational Complexity