What implications would a proof of the abc conjecture have for tcs?
http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
Asked
Active
Viewed 2,457 times
24
-
see also proof claimed for connection between primes by Ball, Nature – vzn Sep 11 '12 at 01:27
-
high voted post with bkg/analysis/papers/links, mathoverflow, philosophy behind mochizuki's work" – vzn Sep 28 '12 at 15:38
-
1polymath resources on the Mochizuki attack, generally frequently updated. links to Mochizukis papers, recent discussions, (MSM) media coverage etc – vzn Sep 30 '12 at 18:41
2 Answers
25
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.
Ryan Williams
- 27,465
- 7
- 115
- 164
22
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
vzn
- 11,014
- 2
- 31
- 64