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



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

[2] fast inverse square root calculation, wikipedia


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.