2,070 reputation
1524
bio website
location
age
visits member for 4 years, 9 months
seen 5 mins ago

1h
comment Super-linear time complexity lower bounds for any natural problem in NP?
@RyanWilliams Is there evidence weakness of multitape machines within standard axioms?
3h
reviewed Approve Terminology in combinatorics
5h
awarded  Nice Question
5h
comment Are there effective small intervals in which primes are dense?
Using 'always' sounds like you proved the problem is NP-complete. If so, please update your answer there.
5h
comment Are there effective small intervals in which primes are dense?
So Shor's answer is expected poly reduction and with this new answer you have the stronger result that you have always poly reduction (using 'always' sounds deterministic reduction, is there a difference?).
6h
comment Are there effective small intervals in which primes are dense?
What is the expected poly definition (is this what is used in Shor's answer)? What is strict definition? What is n_0? your comment is too terse to see where you are leading with this new question here in MO.
6h
comment Are there effective small intervals in which primes are dense?
I still don't understand, both your links are exatly same. What is $n_0$ here? Do you think you have a better answer than Shor's with 'GH from MO's answer. If so you should post it there in factoring link.
6h
comment Are there effective small intervals in which primes are dense?
If reduction is 'deterministic' polynomial, then you should update answer there since it would have showed problem is NP complete.
6h
comment Are there effective small intervals in which primes are dense?
Clearly states 'This is not quite an answer, but it's close. The following is a proof that the problem is NP-hard under randomized reductions'.
6h
comment Are there effective small intervals in which primes are dense?
you mean the reduction was not randomized polynomial in Shor's answer even after Hsien-Chih's comment?
6h
comment Are there effective small intervals in which primes are dense?
How does this result improve the randomized reduction there?
6h
comment Are there effective small intervals in which primes are dense?
I thought randomized reduction was already done through Hsien-Chih's comment with $\theta=0.625$? Only question that remained there was on existence of deterministic reduction.
1d
revised Sampling from random unimodular matrices of a particular type?
added 3 characters in body
1d
revised Sampling from random unimodular matrices of a particular type?
added 3 characters in body
1d
asked Sampling from random unimodular matrices of a particular type?
1d
comment $n!$ computation in $\mathsf{BSS}$ model
This does not imply $\mathsf{SAT}$ collapses (if collapses mean poly time).
1d
comment $n!$ computation in $\mathsf{BSS}$ model
@joro That would be interesting. I do not know of such result. So what does n! have to do with SAT (you mentioned on n! in subexp 'For SAT this would mean collapse AFAICT')?
1d
comment $n!$ computation in $\mathsf{BSS}$ model
What does phrase 'subexp SAT would imply SAT collapse' imply?
1d
comment $n!$ computation in $\mathsf{BSS}$ model
I know that $\mathsf{permanent}$ is easy implies $n!$ is easy. I do not know of connection to $\mathsf{SAT}$.
1d
comment $n!$ computation in $\mathsf{BSS}$ model
Why would $n!$ in subexp time collapse $\mathsf{SAT}$? Is there a direct connection between $n!$ and $\mathsf{SAT}$?