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
What is more importantt: Automata Theory or Crypto?
The way the requirements are set up at Univ of MD at College Park, without getting into details, has set up a competition between Crypto and Automata Theory That...
From Computational Complexity
A problem about Graph Partitions (guest post)
(Guest post from Richard Taylor who requests information on a problem.) The following graph partition problem arises in connection with studies I am doing on...
From Computational Complexity
Kurt Mehlhorn to receive EATCS award
Kurt Mehlhorn will receive EATCS award! Read about it here. He has had a LONG and PRODUCTIVE career with many EXCELLENT papers. While he is mostly known for data...
From Computational Complexity
e to the pi vs pi to the e
(ANSWER to Trivia Questions from Last Post: The last president who became president NOT by being VP and having the prez die, but then did not run again, was Rutherford...
From Computational Complexity
Prediction on Presidents Day
Its PRESIDENT"S DAY so I have two predictions: One about the election of 2012 and one about P vs NP. ON P VS NP: I have one prediction about P vs NP. It isON...
From Computational Complexity
FOCS 2010 CALL FOR PAPES is out!
(Univ of MD at College Park had Monday, Tuesday, Wed, Thursday all off. I've spend most of that time shoveling snow, so I am tired. Hence I am glad to have a SHORT...
From Computational Complexity
What is an Elementary Proof?
What is an Elementary Proof? Different things in different contexts. An Elementary Proof is one that does not use Complex Analysis. Basic Calculus is fine. This...
From Computational Complexity
The more things change the more things change
There have been some articles on how much things have changed because of technology. One from the Washington Post Magazine, titled Going, Going, ..., Gone lists...
From Computational Complexity
Time Space Tradeoffs for SAT- good resuls but...
This is a real conversation between BILL and STUDENT (a Software Engineering Masters Student who knows some theory). As such there are likely BETTER arguments BILL...
From Computational Complexity
Naming and Ranking
Martin Kruskal invented Soliton Waves which were a very important concept in Physics. Rebecca Kruskal (Martin's Granddaughter): Daddy, how come they are not...
From Computational Complexity
Travel Support for Grad Students who GOTO STOC 2010
If you are a grad student and want to goto STOC 2010 there is travel support money that you can apply for. See here for details. What is the best way to get...
From Computational Complexity
Referees'''' reports
A commenter a LOOOOONG time ago left the following: Tell me, Gasarch, how in the world do you get your papers published when you consistently skip the apostrophe...
From Computational Complexity
Guest post on ICS 2010 (x of y for some x and y)
(Another Guest post about ICS 2010. From Aaron Sterling. Is he on his way to break the MOST GUEST POSTS IN A YEAR record? I doubt it- I think I hold it from before...
From Computational Complexity
The First Pseudorandom Generator--Probably
(The following was told to be by Ilan Newman at Dagstuhl 2009. His source was the book The Broken Dice and other mathematical tales of chance.) What was the...
From Computational Complexity
When is a theorem really proven?
One of the comments on this blog pointed out correctly that for a theorem to be accepted by the community is not a Eureka Moment. It is a social process. The author...
From Computational Complexity
Job Postings
Two sites to look for jobs at: Lance Fortnow set up this blog that collects theory annoucments including jobs: here Boaz Barak Obama, in an effort to create...
From Computational Complexity
Two Theorems this blog missed
I warned Lance to wait until early Jan to post 2009 Complexity Year in Review. It was my fear that by posting it on Dec 28, 2009 he may miss out if someone proves...
From Computational Complexity
Should CCC2012 be at the North Pole?
The last few posts on ICS in China have lead to off-topic (though maybe they were not off topic) comments on whether we should have conferences in countries who...
From Computational Complexity
Do Innovative papers have a hard time getting into STOC and FOCS? I ask this objectively with no ax or teeth to grind.
(This is my last post until next week Tuesday.) Many people believe the following: FOCS and STOC only take technically hard results on problems that we already...
From Computational Complexity