tag:blogger.com,1999:blog-3722233.post209792040892008035..comments2022-12-06T23:29:49.138-06:00Comments on Computational Complexity: How Many Sides to Your Error?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-29057153823558650492008-12-11T11:36:00.000-06:002008-12-11T11:36:00.000-06:00The number field sieve factorization algorithm has...The number field sieve factorization algorithm has two-sided error (at least when you ask something like: is 7 the last digit of the smallest prime factor?) So, how about factorization of numbers with (log n)^(5/2) digits? Is this natural?<BR/><BR/>Assuming I've done my arithmetic right: this can be solved in polynomial time by the number field sieve, but not by any of the deterministic factoring algorithms, which are all somewhat slower.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3776785416048331862008-12-04T09:25:00.000-06:002008-12-04T09:25:00.000-06:00In the process of doing property testing on data s...In the process of doing property testing on data streams we have come across problems in which the natural algorithm has double sided error. <BR/><BR/>That is, the algorithm is always correct on any instance that strongly has or doesn't have the property, while on values near the boundary it can give an arbitrary answer (for both yes and no instances). <BR/><BR/>We call these algorithms "Windsor-Detroit" algorithms as they are probabilistic only on the border.<BR/><BR/>This is in contrast to property testing where usually the algorithm is BPP outside the boundary region (or in some cases even in RP outside the boundary region).<BR/><BR/>Alex Lopez-OrtizAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2259876036138007672008-12-03T09:07:00.000-06:002008-12-03T09:07:00.000-06:00What about (promise) decision problems that derive...What about (promise) decision problems that derive from approximation problems for which we only know randomized algorithms? For example, given a convex body described by a linear program, decide if its volume is less than 1 or greater than 2. Alternatively: given a purportedly "pseudorandom" generator, decide if its first output bit is either unbiased, or significantly biased. <BR/><BR/>For my money, the approximation-based promise problems are slightly more natural than derivatives of RP\coRP problems like the two-out-of-three algebraic circuits example. <BR/><BR/>Of course, I understand that we would like total problems rather than promise ones, but if naturalness is your criterion...<BR/><BR/>adamAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50925170918275363442008-12-02T11:25:00.000-06:002008-12-02T11:25:00.000-06:00My definition of UN-NATURALwould be a problem defi...My definition of UN-NATURAL<BR/>would be a problem defined<BR/>JUST FOR THE PURPOSE OF BEING IN/OUT OF A CERTAIN CLASS. For example, the sets that are in DTIME(n^2)<BR/>but not DTIME(n) via the<BR/>time hier theorem. <BR/>Hence the `given three circuits ...' problem is<BR/>certainly natural.<BR/><BR/>Note that its hard to really define `natural'GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42836093472086905512008-12-02T10:02:00.000-06:002008-12-02T10:02:00.000-06:00What's wrong with a perfectly natural problem like...What's wrong with a perfectly natural problem like that? Given the apparently central nature of the algebraic circuit problem (cf. the results of Impagliazzo-Kabanets) maybe we should also not be so dismissive of it as our "only" remaining problem. <BR/><BR/>The real question should be whether BPP collapses to RP intersect coRP (and of course whether that further collapses to P). As in your example, once we have a natural problem in RP union coRP that is not in RP intersect coRP then we will get candidates for natural problems in BPP that are likely not in RP union coRP by taking the obvious problems in the Boolean closure.Anonymousnoreply@blogger.com