What implications would a proof of the abc conjecture have for tcs?
http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
$\begingroup$
$\endgroup$
3
-
$\begingroup$ see also proof claimed for connection between primes by Ball, Nature $\endgroup$– vznCommented Sep 11, 2012 at 1:27
-
$\begingroup$ high voted post with bkg/analysis/papers/links, mathoverflow, philosophy behind mochizuki's work" $\endgroup$– vznCommented Sep 28, 2012 at 15:38
-
1$\begingroup$ polymath resources on the Mochizuki attack, generally frequently updated. links to Mochizukis papers, recent discussions, (MSM) media coverage etc $\endgroup$– vznCommented Sep 30, 2012 at 18:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Bhatnagar, Gopalan, and Lipton show that, assuming the abc conjecture, there are polynomials of degree $O((kn)^{1/2+\varepsilon})$ representing the Threshold-of-$k$ function over ${\mathbb Z}_6$. For fixed constant $k$, and $m$ which has $t$ prime factors, the abc conjecture implies a polynomial for Threshold-of-$k$ over $\mathbb Z_m$ with degree $O(n^{1/t+\varepsilon})$.
This presumably has relevance to the ${\sf TC^0}$ versus $\sf ACC^0[6]$ problem.
answered Sep 27, 2012 at 2:39
$\begingroup$
$\endgroup$
this paper points out that computing the reciprocal square root value using floating point representation is widespread in CS applications ("very common in scientific computations"); the authors show that a more efficient formula is possible for computing the correctly rounded value if the ABC conjecture holds.
[1] The abc conjecture and correctly rounded reciprocal square roots Ernie Croot, Ren-Cang Li, Hui June Zhu, Elsevier TCS 2004
