From The Computing Community Consortium Blog
Contributions to this post were provided by members of the Computing Community Consortium (CCC) Fairness, Accountability, Disinformation…
Helen Wright| June 29, 2020
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
Nearly three years ago I posted on the just announced Netflix prize. First to a 10% increase in the quality of the movie recommendations would receive a million...Lance From Computational Complexity | September 22, 2009 at 05:18 PM
You can now register on-line for FOCS which includes the 50th celebration. Early registration deadline is October 1. Hotel rate good until October 9th or whilehttp...Lance From Computational Complexity | September 21, 2009 at 05:20 PM
Google has acquired reCAPTCHA, Luis von Ahn's project to use humans to aid transcribing old documents. We consider Luis an honorary theorist and congrats for the...Lance From Computational Complexity | September 18, 2009 at 05:21 PM