In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate polynomials. Essentially, to test if the function values on a set of evaluation points correspond to a bivariate polynomial of maximum degrees $(d,d)$, we check whether the restriction of this to axis parallel lines (i.e. rows and columns) are all degree $d$ univariate polynomials (This is an equivalence condition in the absolute case, which is easy to verify. The interesting part is the robustness of the test: that is, if the function values on the restrictions to axis parallel lines agree with low-degree polynomials on "most" points (that is, close to Reed-Solomon codewords), then there is a bivariate low degree polynomial (a Reed-Muller codeword) which also agrees with the function on most evaluation points). The proof of robustness uses the notion of error-corrector polynomial to capture the "bad" evaluation points, polynomial interpolation and then uses resultants. For more details check out sections 2,3,4,5 in http://cs.yale.edu/homes/spielman/PAPERS/holographic.pdf

In a follow-up paper by Sudan and Ben-Sasson (lemma 6.13 and section 6.6 in http://people.csail.mit.edu/madhu/papers/2005/rspcpp-full.pdf) they extend the basic argument of Polishchuk-Spielman to obtain a universal constant relating the distances of the function from row, column polynomials and the Reed-Muller polynomial. They claim a basic proof using the constant taken to be 128, without optimization. Then in a follow-up paper (by Ben Sasson et al here http://eccc.hpi-web.de/report/2012/045/, in section 10 (more precisely section 10.3)) they again talk about optimizing this universal constant and get it down to 10.24.

My question is,

Where did the universal constant exactly come into the picture at all, and how did they use the value of 128 in the first place?

It seems to me (and I am sure I'm wrong here but not clear why) that one could have proved that same result without assuming anything about the size of the constant? It would be very helpful if someone could make that (simple and short) proof more explicit so that one sees how the constant and its assumed value enters the proof. Thanks in advance.

  • $\begingroup$ It may be too late, but out of curiosity: is your question "How/where do they use this assumption on the absolute constant (and its values 128) in the proof of the Lemma 6.13," or "why do they care about getting an explicit value for this constant $c_0$, as small as possible, in the rest -- i.e., in the applications of the lemma"? $\endgroup$ – Clement C. Aug 6 '15 at 11:52

Your Answer

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

Browse other questions tagged or ask your own question.