# Implications of proof of abc conjecture for cs theory

What implications would a proof of the abc conjecture have for tcs?

http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/

## 2 Answers

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