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
Learning from teaching a HS student Schur's theorem on change
(All the math this post refers to is in my manuscript which is here.) Recall Schur's theorem on making change as stated in wikipedia and other source: Let a1...
From Computational Complexity
First issue of SIGACT news where I wasn't the editor. But...
I posted at some earlier time that I was resigning from the editorship of SIGACT NEWS book review column, and handing the reins over to Fred Green (who is older...
From Computational Complexity
The city where the book publishers resides is Funkytown!
A while back when I got back the galleys for a paper the publisher wanted to know the complete postal address of one of the co-authors and also the city where...
From Computational Complexity
Langs with provably bigger CFG's then CSG's
In a prior blog entry HERE I discussed very large differences in the size of machines. I didn't discuss CFG vs CSG so I'll do that now. We assume that the CFGs...
From Computational Complexity
Who wins this bet?
Alice and Bob are at an auction and Alice wants to buy an encyclopedia set from 1980. Bob says don't buy that, you'll never use it. In this age of Wikipedia and...
From Computational Complexity
An Intentional and an Unintentional teaching experiment regarding proving the number of primes is infinite.
I taught Discrete Math Honors this semester. Two of the days were cancelled entirely because of snow (the entire school was closed) and four more I couldn't make...
From Computational Complexity
The law of the excluded middle of the road republicans
In the book Hail to the Chiefs about the presidents, when pointing to a race between two people who had no business being president (I think it was Franklin Pierce...
From Computational Complexity
Sizes of DFAs, NFAs, DPDAs, UCFG, CFGs, CSLs.
If A is a decider (e.g, DFA) or generator (e.g., CFG) then L(A) is the language that it decides or generates. The following are well known: L(DFA) = L(NDFA)...
From Computational Complexity
Advice on running a theory day
Last semester I ran a THEORY DAY AT UMCP. Below I have ADVICE for people running theory days. Some I did, some I didn't do but wish I did, and some are just questions...
From Computational Complexity
The New Oracle Result! The new circuit result! which do you care about?
You have likely heard of the new result by Ben Roco, and Li-Yang on random oracles (see here for preprint) from either Lance or Scott or some other source: Lance's...
From Computational Complexity
Two cutoffs about Warings problem for cubes
Known: All numbers except 23 can be written as the sum of 8 cubes All but a finite number of numbers can be written as the sum of 7 cubes There are an infinite...
From Computational Complexity
Which of these stories is false
I would rather challenge you than fool you on April fools day. Below I have some news items. All but one are true. I challenge you to determine which one is false...
From Computational Complexity
Which mathematician had the biggest gap between fame and contribution?
(I was going to call this entry Who was the worst mathematician of all time? but Clyde Kruskal reminded me that its not (say) Goldbach's fault that his conjecture...
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