<p>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.</p>

<p>[1] <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.6358&amp;rep=rep1&amp;type=pdf">The abc conjecture and correctly rounded reciprocal square roots
</a> Ernie Croot, Ren-Cang Li, Hui June Zhu, Elsevier TCS 2004</p>

<p>[2] <a href="http://en.wikipedia.org/wiki/Fast_inverse_square_root">fast inverse square root calculation, wikipedia</a></p>

CC BY-SA 3.0
2012-09-11T05:15:20.477Z
2012-09-11T05:15:20.477Z
vzn
<p><a href="http://www.cc.gatech.edu/people/home/parik/RESEARCH/jcss.pdf">Bhatnagar, Gopalan, and Lipton</a> 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})$.</p>

<p>This presumably has relevance to the ${\sf TC^0}$ versus $\sf ACC^0[6]$ problem.</p>

CC BY-SA 3.0
2012-09-27T02:39:40.957Z
2012-09-27T02:39:40.957Z
Ryan Williams
<p>What implications would a proof of the <a href="http://en.wikipedia.org/wiki/Abc_conjecture">abc conjecture</a> have for tcs?</p>

<p><a href="http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/">http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/</a></p>

CC BY-SA 3.0
2012-09-11T01:27:55.557Z
see also [proof claimed for connection between primes](http://www.nature.com/news/proof-claimed-for-deep-connection-between-primes-1.11378) by Ball, Nature
vzn
CC BY-SA 3.0
2012-09-28T15:38:11.160Z
high voted post with bkg/analysis/papers/links, mathoverflow, [philosophy behind mochizuki's work"](http://mathoverflow.net/questions/106560/philosophy-behind-mochizukis-work-on-the-abc-conjecture)
vzn
CC BY-SA 3.0
2012-09-30T18:41:30.893Z
[polymath resources on the Mochizuki attack](http://michaelnielsen.org/polymath1/index.php?title=ABC_conjecture), generally frequently updated. links to Mochizukis papers, recent discussions, (MSM) media coverage etc
vzn
<big-picture><nt.number-theory>
Implications of proof of abc conjecture for cs theory
vtt
# Implications of proof of abc conjecture for cs theory

(Asked by: username_0 on 2012-09-04)

What implications would a proof of the [abc conjecture](http://en.wikipedia.org/wiki/Abc_conjecture) have for tcs?

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

**Tags:** big-picture, nt.number-theory
> **Comments:**
> **username_1**: see also [proof claimed for connection between primes](http://www.nature.com/news/proof-claimed-for-deep-connection-between-primes-1.11378) by Ball, Nature  
> **username_1**: high voted post with bkg/analysis/papers/links, mathoverflow, [philosophy behind mochizuki's work"](http://mathoverflow.net/questions/106560/philosophy-behind-mochizukis-work-on-the-abc-conjecture)  
> **username_1**: [polymath resources on the Mochizuki attack](http://michaelnielsen.org/polymath1/index.php?title=ABC_conjecture), generally frequently updated. links to Mochizukis papers, recent discussions, (MSM) media coverage etc  

---

## 2 answers

### Answer by username_2 on 2012-09-27. Score: 25

[Bhatnagar, Gopalan, and Lipton](http://www.cc.gatech.edu/people/home/parik/RESEARCH/jcss.pdf) 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.


---

### Answer by username_1 on 2012-09-11. Score: 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.6358&rep=rep1&type=pdf) Ernie Croot, Ren-Cang Li, Hui June Zhu, Elsevier TCS 2004

[2] [fast inverse square root calculation, wikipedia](http://en.wikipedia.org/wiki/Fast_inverse_square_root)


---

