bio  website  

location  
age  
visits  member for  4 years, 9 months 
seen  5 mins ago  
stats  profile views  3,300 
1h

comment 
Superlinear 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 NPcomplete. 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 NPhard 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 HsienChih'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 HsienChih'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}$? 