How can I transform the term $x>C$ (i.e. the term assumes the value $1$ if $x>C$ and assumes the value $0$ otherwise) to an arithmetic circuit that computes it?

Where $x$ is the input to the circuit and $C$ is a known constant.

  • 3
    $\begingroup$ You can’t. Arithmetic circuits only compute polynomials, and the set of positive elements is not the zero set of a polynomial in any ordered ring. $\endgroup$ Aug 31, 2014 at 19:46
  • 1
    $\begingroup$ Well, if the ordered ring is an integral domain, then a nonconstant polynomial can only have finitely many zeros, whereas there are infinitely many positive elements. If it’s not a domain, the argument gets a bit more messy, but it still works out. $\endgroup$ Aug 31, 2014 at 20:26
  • 2
    $\begingroup$ What do you mean by $x>C$ then? A finite field can’t be ordered. Which ordered structure do you take $x$ and $C$ from, and how do you represent them by elements of the finite field? $\endgroup$ Aug 31, 2014 at 20:45
  • 5
    $\begingroup$ Bush: I suggest you try to reformulate the question to actually express what you are thinking of. $\endgroup$ Sep 1, 2014 at 9:34
  • 4
    $\begingroup$ You can use interpolation to write any function on a finite field as an arithmetic circuit. Do you have other requirements? $\endgroup$ Sep 1, 2014 at 16:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy