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
Do we ever NEED the adv pumping lemma for Reg langs?
Recall the Pumping Lemma and the Advanced Pumping Lemma for Regular languages: Pump. Lemma: If L is regular and infinite then there exists n such that for all...
From Computational Complexity
Enos, Oona, sqrt(3), and Aaronson
My darling does crossword puzzles and sometimes asks my help: Darling: Bill, Slaughter in Cooperstown- whats the answer? Bill: Enos. There was a serial murderer...
From Computational Complexity
Are most lower bounds really upper bounds?
Recently Daniel Apon (grad student of Jon Katz at UMCP, but he also hangs out with me) proved a LOWER BOUND by proving an UPPER BOUND. His paper is here. I have...
From Computational Complexity
Proving DFA-langs closed under concat and * without using equiv to NDFA's
While teaching the Equiv of DFA, NDFA, Reg exps, I wanted to impress upon my students that the best way to show DFA-langs are closed under concat and * is to first...
From Computational Complexity
The (il)logic of fandom
(UMCP is having an REU (Research Experience for Undergradutes) this summer on Combinatorial Algorithms Applied Research. If you are an ugrad, go to that site and...
From Computational Complexity
TCS online series- could this work?
Oded Regev, Anindya De and Thomas Vidick we are about to start an online TCS seminar series. See here for details, though I have the first few paragraphs below...
From Computational Complexity
A New application of Ramsey Theory to a Geometry problem
All of the material summazized here is in a new paper by Gasarch and Zbarsky. You can find that paper here) Consider the following problem: Let {p1,...,pn}...
From Computational Complexity
paperfree?- we are not there yet
Last time I taught I had to decide if I would HAND OUT the HW or just say its posted (NOTE- I post it in any case.) This may seem old fashion but I think there...
From Computational Complexity
Do daughtered candidates to better- Look at the Data!
Someone in my election night party predicted Obama because: Ever since women got the right to vote (1920) if one candidate has a daughter and one does not, then...
From Computational Complexity
Goodstein Sequences (Its his 100th birthday!)
LANCE: Bill, on Dec 15, 2012 it will be Reuben Goodstein's 100th birthday. BILL: Is he still alive? Will there be a conference in his honor? Free Food? Cake? ...
From Computational Complexity
Book review column
(I am a bit behind on posting links to my book review column- this blog post is about the Third (of four) for the year 2012, and the fourth of four has alreadyhere...
From Computational Complexity
Where is the youth of TCS/questions on Nash Eq (guest post by VJ)
(Guest post by Vijay Vazirani.) On Theory Day on Nov 30, 2012 Vijay Vazarani gave a talk: New (Practical) Complementary Pivot Algorithms for Market Equilibrium...
From Computational Complexity
Inverse Closure Problem
In the undergraduate complexity course we spend some time on closure properties such as (1) REG closed under UNION, INTER, COMP and (2) R.E. closed under UNION...
From Computational Complexity
If GASARCH Tweeted what would he tweet?
If I tweeted this is what I would tweet: The problem with trying to predict who will win the election. Prez election thought: if you run as yourself and lose (Stevenson...
From Computational Complexity
Andrew Goldberg guest blog on new max flow result
Guest Blog by Andrew Goldberg on the recent Max Flow in O(nm) time algorithm. Maximum Flow in O(nm) Time Recently, Jim Orlin published an O(nm) maximum flow algorithm...
From Computational Complexity
Random thoughts on the election
Neither Lance and I have commented much on the Prez election. I only found one post from 2012 that mentioned Romney: Romney vs Aaronson. A few mentioned Obama but...
From Computational Complexity
Planarizing Gadgets for Perfect Matching do not Exist!
At Dagstuhl I was delighted when I saw the title of a talk to be given Planarizing Gadgets for Perfect Matching do not Exist because I had asked the question about...
From Computational Complexity
Theory Day. How to get the word out on this and other events?
Aravind asked me to post on this again (NOTE- registration-for-free deadline is TOMMOROW!!!!!) The University of Maryland at College park is having a Theory Day...
From Computational Complexity
Cruel XOR unusual Punishment
(This post was done with the help of Lane Hemaspaandra and John Purtilo.) The 8th amendment of the US Constitution states Excessive bail shall not be required...
From Computational Complexity