Some councils put up 'Ignore your sat nav' signs because drivers kept relying more on the wrong information from electronic directions instead of trusting their...Jo Brodie From CS4FN (Computer Science For Fun) | September 30, 2022 at 05:33 AM
Imagine being able to pick up an ordinary banana and use it as a phone. That's part of the vision of 'invoked computing', which is being developed by Japanese researchers...Jo Brodie From CS4FN (Computer Science For Fun) | September 25, 2022 at 11:55 AM
Computer Science isn't just about using language, sometimes it's about losing it. Sometimes people want to send messages so no one even knows they exist and a great...Jo Brodie From CS4FN (Computer Science For Fun) | September 25, 2022 at 11:26 AM
In the 1990's Manindra Agrawal and V. Arvind published a paper claiming that if SAT is reducible to a (non-uniform) weighted threshold function then P = NP. Their...Lance From Computational Complexity | October 15, 2009 at 04:59 PM
While I was refactoring a hand full of commonly used methods from a few controllers into a superclass, I was looking for a way to test that these controllers are...Tobias Svensson From Return 42; | October 13, 2009 at 09:29 AM
This week Bill and I are both at the Dagstuhl Workshop on Algebraic Methods in Computation Complexity. I'll try to cover some of the talks and discussions on the...Lance From Computational Complexity | October 12, 2009 at 05:12 PM
A number of interesting visualizations of data. The original piece is 50 great examples of data visualization. There is no doubt that these are colorful, finely...Franz Dill From The Eponymous Pickle | October 12, 2009 at 10:20 AM
On the New York Times website, John Markoff writes an article Prizes Aside, the P-NP Puzzler has Consequences motivated by my CACM article on The Status of the....Lance From Computational Complexity | October 8, 2009 at 05:14 PM
In what seems like a small thing, Google now lets you get a quick view of search results, Gmail and Google docs as a PDF. As a result you can preserve more formatting...Franz Dill From The Eponymous Pickle | October 8, 2009 at 09:34 AM
When you get an invitation via email should you accept? How well targeted is it? Some real examples that I got.
I would like to invite you toclick...GASARCH From Computational Complexity | October 6, 2009 at 05:15 PM
In a prior post (a while back) I pondered if Mahaney's theorem (SAT \le_m S, S Spare, implies P=NP) should be taught in a basic grad course in complexity. I thought...GASARCH From Computational Complexity | October 5, 2009 at 05:16 PM
In a tweet a few days ago, David Bacon
wonders why everyone always assumes all he can do is quantum computing? Oh, because that's all he's done. Time to do something...Lance From Computational Complexity | October 2, 2009 at 05:16 PM
Reminder: FOCS early registration deadline today. Go here
Below is a revised version of the Journal Manifesto. I restate the key sentence from my last post and...GASARCH From Computational Complexity | October 1, 2009 at 05:16 PM
Some people say that for-profit journals do not currently serve our community well. Some even think they cannot do so. Others think they are doing a fine job as...GASARCH From Computational Complexity | September 30, 2009 at 05:17 PM
My family has discovered a British Series, the IT Crowd, about two techies in a corporate IT department. An American version never got past the pilot phase.
...Lance From Computational Complexity | September 29, 2009 at 05:17 PM
One of the comments of the last post asked my (or someones) opinion on the proofs floating around that P=NP or P\ne NP.
As a grad student I used to readWhat...GASARCH From Computational Complexity | September 28, 2009 at 05:18 PM
A reader writes
I come to you by way of your computational complexity blog. I get that there is some really good stuff there, but frankly don’t understand about...Lance From Computational Complexity | September 25, 2009 at 05:19 PM
There have been several posts on blogs about P vs NP and two expository articles. Is there anything else to add. I'm not sure, but here are my 2 cents.
QUESTION...GASARCH From Computational Complexity | September 24, 2009 at 05:19 PM
(Posted by request of Vijay V. Vazirani. Flame him for any spelling or grammar mistakes, or if you don't like the content.)
Another reason to goto FOCS:here...GASARCH From Computational Complexity | September 23, 2009 at 05:20 PM