What implications would a proof of the abc conjecture have for tcs?
http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
-
$\begingroup$ see also proof claimed for connection between primes by Ball, Nature $\endgroup$vzn– vzn2012年09月11日 01:27:55 +00:00Commented Sep 11, 2012 at 1:27
-
$\begingroup$ high voted post with bkg/analysis/papers/links, mathoverflow, philosophy behind mochizuki's work" $\endgroup$vzn– vzn2012年09月28日 15:38:11 +00:00Commented 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$vzn– vzn2012年09月30日 18:41:30 +00:00Commented Sep 30, 2012 at 18:41
2 Answers 2
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.
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