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
Has anything interesting every come out of a claimed proof that P=NP or P ≠ NP?
When I was young and foolish and I heard that someone thinks they proven P=NP or P ≠ NP I would think Wow- maybe they did!. Then my adviser, who was on the FOCS...
From Computational Complexity
Guest Post by Thomas Zeume on App of Ramsey Thy to Dyn Desc Comp.
Guest Post by Thomas Zeume on Lower Bounds for Dynamic Descriptive Complexity (A result that uses Ramsey Theory!) In a previous blog post Bill mentioned his...
From Computational Complexity
(1/2)! = sqrt(pi) and other conventions
(This post is inspired by the book The cult of Pythagoras: Math and Myths which I recently read and reviewed. See here for my review.) STUDENT: The factorial...
From Computational Complexity
Stephan Colbert, Jon Stewart, Andrew Sullivan, William Gasarch
Stephan Colbert is leaving the Colbert Report Jon Stewart is leaving the Daily Show Andrew Sullivan is no longer blogging Bill Gasarch has resigned as SIGACT...
From Computational Complexity
Pros and Cons of students being wikiheads
A wikihead is someone who learns things from the web (not necc. Wikipedia) but either learns things that are not correct or misinterprets them. I've also heard...
From Computational Complexity
Less elegant proofs that (2n)!/n!n! is an integer
(A conversation between Bill (the writer of this post) and Olivia (14-year old daughter of a friend.) All of the math involved is here. Bill: Do you know what...
From Computational Complexity
A nice problem from a Romanian Math Problem Book
(All of the math for this problem is here)My Discrete Math Honors TA Ioana showed me a Romanian Math Problem book(She is Romanian) and told the following problem...
From Computational Complexity
The two defintions of Chomsky Normal Form
I have eight textbooks on Formal Lang Theory on my desk. Six of them define a CFG to be in Chomsky Normal Form if every production is of the form either A-->BC...
From Computational Complexity
Barrier's for Matrx Mult Lower bound
Matrix Mult: The usual algorithm is O(n^3). Strassen surprised people by showing an O(n^{2.81}) algorithm. (Now its so well known that its not surprising. IFast...
From Computational Complexity
Why do students do this?
Before my midterm in ugrad Theory of Computation I gave the students a sheet of practice problems to do that I would go over before the midterm. One of them...
From Computational Complexity
Joint Center for Quantum Information and Computer Science
(Guest post by Andrew Childs who is now at the Univ of MD at College Park) We have recently launched a new Joint Center for Quantum Information and ComputerScience...
From Computational Complexity
Godel and Knuth Prize Nominations due soon. Which would you rather win? Or ...
(Alg Decision Theory conference in Kentucky: here.) Knuth Prize Nominations are due Jan 20, 2015. For info on the prize see here, if you want to nominate someone...
From Computational Complexity
Cliques are nasty but Cliques are nastier
BILL: Today we will show that finding large cliques is likely a nasty problem STUDENT: Yes! In my High School the Cliques were usually at most six people and they...
From Computational Complexity
Guest Post about Barbie `I can be an engineer' -- Sounds good but its not.
There is now a I can be an engineer Barbie. That sounds good! It's not. Imagine how this could be turned around and made sexist. What you are imagining might not...
From Computational Complexity
A Fly on the wall for a Harvard Faculty meeting: Not interesting for Gossip but interesting for a more important reason
I was recently in Boston for Mikefest (which Lance talked about here) and found time to talk to my adviser Harry Lewis at Harvard (adviser? Gee, I already finished...
From Computational Complexity
Non controversial thoughts on rankings
US News has a ranking of CS depts and various subcategories. Recently MohammadTaghi Hajiaghay and Luca Trevisan have suggested alternative rankings here (Moh) and...
From Computational Complexity
A few more notes about Sipser and Sipser-60th
While Lance was AT Mikefest (Sipser's 60th Bday conference), helping to organize it, emceeing the personal statements, I was... also there. A few notes Aside...
From Computational Complexity
Guest Post by Dr. Hajiaghayi: A new way to rank departments
(This is a guest post by MohammadTaghi Hajiaghayi. His name is not a typo- the first name really is MohammadTaghi.) Due to our belief in the lack of transparency...
From Computational Complexity
Martin Gardner Centennial
Martin Gardner was born on October 21, 1914, so today is his Centennial (he died on May 22, 2010, at the age of 95). We've mentioned him in the blog before: ...
From Computational Complexity