Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
see also proof claimed for connection between primes by Ball, Nature –  vzn Sep 11 '12 at 1:27
high voted post with bkg/analysis/papers/links, mathoverflow, philosophy behind mochizuki's work" –  vzn Sep 28 '12 at 15:38
polymath 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 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.

share|improve this answer

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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