News for hackers. Stuff that matters.
Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo... by duaneb on Wednesday July 22, 2015 @12:51PM (#9930767)
So, I don't have the theory background a PhD candidate might, so forgive my ignorance, but why would a theory be expected to build on the already proven partial results? I was under the impression their use was as a quality heuristic, not something a proof of a lower bound of the general case could make much use of.
Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo... by pja on Wednesday July 22, 2015 @01:17PM (#9930940)
Generally because that’s how mathematics tends to work - people publish a partial result & then they or others build on it to improve that result in various ways[1]. The authors are also usually embedded in a wider community of mathematicians who act as a pre-publication bullshit filter by asking pointed questions at seminars & that kind of thing.

It’s quite rare for a genuinely novel solution to a major problem in mathematics to spring up out of nowhere in the literature.

[1] Think of, eg, the Twin Prime conjecture (that there are infinitely many pairs of primes only 2 integers apart). For decades there was no progress on this problem, before Yitang Zhang published a paper last year proving that there were infinitely many primes less than a finite bound apart (70 million in his case). Then a horde of matheaticians attacked the problem using his & other new approaches to progressively reduce that large bound down to the point where it’s now been proven that there are infinitely many primes < 246 apart (according to the polymath group - I’m not sure whether this is a published result yet). The twin prime conjecture is in sight!

Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo... by duaneb on Wednesday July 22, 2015 @11:38PM (#9933843)
Yea, but to my understanding the partial work done thus far does not apply to an understanding of the general case solution. Let's say there is a linear solution for some form--how does that help establish a lower bound on the general form?

Recognition of past work I can understand. But it seems like occam would argue with me against the use of some of the partial results without understanding why they would be useful.