# dorkusmonkey

 Dec 4 comment Cryptography without assumptions -- seeking an overviewNote that RSA is not NP-Complete, so requiring P=NP to factor might be overkill. Nov 27 awarded Yearling Nov 27 awarded Yearling Nov 26 comment dynamic algorithms for the subset-sum problem hold for vectors?LLL and other lattice reduction techniques have enjoyed moderate success with larger instances, but as far as I know, there are no good algorithms for anything other than when bit sizes that are exponentially smaller than the list length. Nov 26 comment dynamic algorithms for the subset-sum problem hold for vectors?There is an easy reduction from the 'vectorized' version of subset sum and the normal subset sum by padding each 'column' with enough zeros so that subsequent additions will not 'bleed' into the other columns (that is overflow via addition). Though only one type of reduction, this gives you a rough sense of how the bit size of the entries compares with the number of integers you have. In general, dynamic programming solutions only work for bit sizes that are exponentially smaller than the number of numbers. Nov 21 answered Factoring with LLL when the form of the factors is given Nov 20 comment Factoring with LLL when the form of the factors is givenYou want the coefficients of $f_1(x)$ and $f_2(x)$ integer as well? Nov 4 comment Theoretical guarantees for running times of belief propagation methods?This is also why survey propagation (a cousin of belief propagation) works so well on solving large random 3-SAT problems. For random factor graphs, locally, the graph looks like it's a tree and so survey propagation can make progress. Oct 15 comment Mouse coordinates on Canvas without Jquery+1, don't know why this doesn't have more upvotes. If you scroll down on a canvas and don't take into account the window.scrol[XY], your co-ordinates will be wrong. Oct 6 comment Overarching reasons why problems are in P or BPPThe Partial Sum LQ (as in factorization) algorithm and Hastad, Just, Lagarias and Schnorr algorithm (I assume the algorithm was named after the author's last names) are more "modern" algorithms for integer relation detection. Oct 4 comment Overarching reasons why problems are in P or BPPI would argue that LLL (and PSLQ/HJLS) are generalizations of the GCD algorithm, rather than the other way around. Oct 3 comment Overarching reasons why problems are in P or BPPAlso, primality testing, both the random and deterministic version, rely on a sort of probabilistic method, so that falls under your first criteria. From what little number theory I've seen, many arguments fall into this sort of probabilistic method/mathematical argument to guarantee polynomial running time. Oct 3 comment Overarching reasons why problems are in P or BPPIf you look at the Schreirer-Sims method, I would argue that this falls into a "linear algebra" like category, as the algorithm closely resembles Gaussian elimination, just with building stabilizing sets. Sep 19 comment robust algorithm for surface reconstruction from 3D point cloud?CGAL 4.0 is now completely under GPL/LGPL. See here. Sep 3 awarded Yearling Sep 3 awarded Yearling Aug 2 awarded Critic Aug 2 comment Worst case $O(n \ln n)$ in place stable sort?-1, violates the O(1) extra space condition. Jun 12 comment Does a noisy version of Conway's game of life support universal computation?Perhaps I'm stating the obvious, but you can just duplicate a configuration enough times so as to guarantee with high probability that a version of the configuration doesn't even have one cell flipped. My personal belief is that we can do much, much better, but at least it's a simple lower bound. May 9 comment How does Clarice know "Jack Gordon" was actually the real Buffalo Bill?This is mostly correct, with one key omission. Near the end, just before Hannibal escapes, he gives Clarice the case file notes back. Clarice, after reviewing the documents, sees a message on a map made by Hannibal, saying "Clarice, doesn't this random scattering of sites seem desperately random, like the elaboration of a bad liar?". After noting that the first victim was found after later victims, this gives Clarice a clew that Buffalo Bill knew the first victim personally before murdering her and allowed Clarice to pursue Buffalo Bill through his connection to the first victim.