{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:03:57Z","timestamp":1725563037846},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_55","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"738-751","source":"Crossref","is-referenced-by-count":3,"title":["A Query Efficient Non-adaptive Long Code Test with Perfect Completeness"],"prefix":"10.1007","author":[{"given":"Suguru","family":"Tamaki","sequence":"first","affiliation":[]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1","doi-asserted-by":"crossref","unstructured":"Austrin, P., H\u00e5stad, J.: Randomly supported independence and resistance. In: Proc.\u00a0of STOC 2009, pp. 483\u2013492 (2009)","DOI":"10.1145\/1536414.1536481"},{"issue":"4","key":"55_CR2","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1006\/jcss.2001.1747","volume":"62","author":"Y. Aumann","year":"2001","unstructured":"Aumann, Y., H\u00e5stad, J., Rabin, M.O., Sudan, M.: Linear-Consistency Testing. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a062(4), 589\u2013607 (2001)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"key":"55_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/978-3-540-45198-3_17","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"N. Alon","year":"2003","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing low-degree polynomials over GF(2). In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 188\u2013199. Springer, Heidelberg (2003)"},{"issue":"3","key":"55_CR4","first-page":"501","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof Verification and the Hardness of Approximation Problems. J.\u00a0ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"J.\u00a0ACM"},{"issue":"2","key":"55_CR5","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00037-009-0272-6","volume":"18","author":"P. Austrin","year":"2009","unstructured":"Austrin, P., Mossel, E.: Approximation Resistant Predicates from Pairwise Independence. Computational Complexity\u00a018(2), 249\u2013271 (2009)","journal-title":"Computational Complexity"},{"issue":"1","key":"55_CR6","first-page":"70","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic Checking of Proofs: A New Characterization of NP. J.\u00a0ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"J.\u00a0ACM"},{"issue":"1","key":"55_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.2307\/1970980","volume":"102","author":"W. Beckner","year":"1975","unstructured":"Beckner, W.: Inequalities in Fourier analysis. Annals of Mathematics\u00a0102(1), 159\u2013182 (1975)","journal-title":"Annals of Mathematics"},{"issue":"6","key":"55_CR8","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1109\/18.556674","volume":"42","author":"M. Bellare","year":"1996","unstructured":"Bellare, M., Coppersmith, D., H\u00e5stad, J., Kiwi, M.A., Sudan, M.: Linearity testing in characteristic two. IEEE Transactions on Information Theory\u00a042(6), 1781\u20131795 (1996)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"55_CR9","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free Bits, PCPs, and Nonapproximability-Towards Tight Results. SIAM J.\u00a0Comput.\u00a027(3), 804\u2013915 (1998)","journal-title":"SIAM J.\u00a0Comput."},{"key":"55_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-540-85363-3_26","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Blais","year":"2008","unstructured":"Blais, E.: Improved Bounds for Testing Juntas. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 317\u2013330. Springer, Heidelberg (2008)"},{"key":"55_CR11","doi-asserted-by":"crossref","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proc.\u00a0of STOC 2009, pp. 151\u2013158 (2009)","DOI":"10.1145\/1536414.1536437"},{"issue":"3","key":"55_CR12","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-Testing\/Correcting with Applications to Numerical Problems. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a047(3), 549\u2013595 (1993)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"issue":"2","key":"55_CR13","doi-asserted-by":"crossref","first-page":"335","DOI":"10.5802\/aif.357","volume":"20","author":"A. Bonami","year":"1970","unstructured":"Bonami, A.: \u00c9tude des coefficients de Fourier des fonctions de L p (G). Annales de l\u2019Institut Fourier\u00a020(2), 335\u2013402 (1970)","journal-title":"Annales de l\u2019Institut Fourier"},{"issue":"1","key":"55_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E. Ben-Sasson","year":"2005","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF Properties Are Hard to Test. SIAM J.\u00a0Comput.\u00a035(1), 1\u201321 (2005)","journal-title":"SIAM J.\u00a0Comput."},{"key":"55_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1007\/978-3-642-03685-9_34","volume-title":"APPROX-RANDOM 2009","author":"V. Chen","year":"2009","unstructured":"Chen, V.: A hypergraph dictatorship test with perfect completeness. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX-RANDOM 2009. LNCS, vol.\u00a05687, pp. 448\u2013461. Springer, Heidelberg (2009)"},{"key":"55_CR16","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Lee, H.K., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R.A., Wan, A.: Testing for Concise Representations. In: Proc.\u00a0of FOCS 2007, pp. 549\u2013558 (2007)","DOI":"10.1109\/FOCS.2007.32"},{"issue":"4","key":"55_CR17","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1002\/rsa.20226","volume":"33","author":"L. Engebretsen","year":"2008","unstructured":"Engebretsen, L., Holmerin, J.: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Struct.\u00a0Algorithms\u00a033(4), 497\u2013514 (2008)","journal-title":"Random Struct.\u00a0Algorithms"},{"key":"55_CR18","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. The Bulletin of the European Association for Theoretical Computer Science\u00a075, 97\u2013126 (2001)","journal-title":"The Bulletin of the European Association for Theoretical Computer Science"},{"key":"55_CR19","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Lewin, D., Sudan, M., Trevisan, L.: A Tight Characterization of NP with 3 Query PCPs. In: Proc.\u00a0of FOCS 1998, pp. 8\u201317 (1998)","DOI":"10.1109\/SFCS.1998.743424"},{"key":"55_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-540-85363-3_7","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Guruswami","year":"2008","unstructured":"Guruswami, V., Raghavendra, P.: Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 77\u201390. Springer, Heidelberg (2008)"},{"key":"55_CR21","first-page":"1061","volume":"97","author":"L. Gross","year":"1975","unstructured":"Gross, L.: Logarithmic Sobolev inequalities. Amer.\u00a0J.\u00a0Math.\u00a097, 1061\u20131083 (1975)","journal-title":"Amer.\u00a0J.\u00a0Math."},{"issue":"4","key":"55_CR22","first-page":"798","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J.\u00a0ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"J.\u00a0ACM"},{"key":"55_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-540-74208-1_11","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"J. H\u00e5stad","year":"2007","unstructured":"H\u00e5stad, J.: On the Approximation Resistance of a Random Predicate. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 149\u2013163. Springer, Heidelberg (2007)"},{"key":"55_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.4086\/toc.2005.v001a007","volume":"1","author":"J. H\u00e5stad","year":"2005","unstructured":"H\u00e5stad, J., Khot, S.: Query Efficient PCPs with Perfect Completeness. Theory of Computing\u00a01, 119\u2013148 (2005)","journal-title":"Theory of Computing"},{"issue":"2","key":"55_CR25","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1002\/rsa.10068","volume":"22","author":"J. H\u00e5stad","year":"2003","unstructured":"H\u00e5stad, J., Wigderson, A.: Simple analysis of graph tests for linearity and PCP. Random Struct.\u00a0Algorithms\u00a022(2), 139\u2013160 (2003)","journal-title":"Random Struct.\u00a0Algorithms"},{"key":"55_CR26","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proc.\u00a0of STOC 2002, pp. 767\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"issue":"2","key":"55_CR27","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1067309.1067318","volume":"36","author":"S. Khot","year":"2005","unstructured":"Khot, S.: Inapproximability results via Long Code based PCPs. SIGACT News\u00a036(2), 25\u201342 (2005)","journal-title":"SIGACT News"},{"key":"55_CR28","doi-asserted-by":"crossref","unstructured":"Khot, S., Saket, R.: A 3-Query Non-Adaptive PCP with Perfect Completeness. In: Proc.\u00a0of IEEE Conference on Computational Complexity 2006, pp. 159\u2013169 (2006)","DOI":"10.1109\/CCC.2006.5"},{"key":"55_CR29","unstructured":"Lovett, S.: Lower bounds for adaptive linearity tests. In: Proc.\u00a0of STACS 2008, pp. 515\u2013526 (2008)"},{"key":"55_CR30","doi-asserted-by":"crossref","unstructured":"Mossel, E., O\u2019Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences: invariance and optimality. Ann.\u00a0Math. (to appear)","DOI":"10.4007\/annals.2010.171.295"},{"key":"55_CR31","unstructured":"Mossel, E.: Gaussian Bounds for Noise Correlation of Functions. In: GAFA (to appear)"},{"key":"55_CR32","unstructured":"O\u2019Donnell, R.: Analysis of Boolean functions lecture notes (2007), http:\/\/www.cs.cmu.edu\/~odonnell\/boolean-analysis\/"},{"key":"55_CR33","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Wu, Y.: 3-bit dictator testing: 1 vs. 5\/8. In: Proc.\u00a0of SODA 2009, pp. 365\u2013373 (2009)","DOI":"10.1137\/1.9781611973068.41"},{"key":"55_CR34","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Wu, Y.: Conditional hardness for satisfiable 3-CSPs. In: Proc.\u00a0of STOC 2009, pp. 493\u2013502 (2009)","DOI":"10.1145\/1536414.1536482"},{"issue":"1","key":"55_CR35","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M. Parnas","year":"2002","unstructured":"Parnas, M., Ron, D., Samorodnitsky, A.: Testing Basic Boolean Formulae. SIAM J.\u00a0Discrete Math.\u00a016(1), 20\u201346 (2002)","journal-title":"SIAM J.\u00a0Discrete Math."},{"issue":"3","key":"55_CR36","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A Parallel Repetition Theorem. SIAM J.\u00a0Comput.\u00a027(3), 763\u2013803 (1998)","journal-title":"SIAM J.\u00a0Comput."},{"key":"55_CR37","doi-asserted-by":"crossref","unstructured":"Ron, D.: Property Testing: A Learning Theory Perspective, 112 pages. Now Publishers Inc. (2008)","DOI":"10.1561\/9781601981837"},{"key":"55_CR38","doi-asserted-by":"crossref","unstructured":"Sudan, M., Trevisan, L.: Probabilistically Checkable Proofs with Low Amortized Query Complexity. In: Proc.\u00a0of FOCS 1998, pp. 18\u201327 (1998)","DOI":"10.1109\/SFCS.1998.743425"},{"key":"55_CR39","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proc.\u00a0of STOC 2000, pp. 191\u2013199 (2000)","DOI":"10.1145\/335305.335329"},{"issue":"1","key":"55_CR40","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/070681612","volume":"39","author":"A. Samorodnitsky","year":"2009","unstructured":"Samorodnitsky, A., Trevisan, L.: Gowers Uniformity, Influence of Variables, and PCPs. SIAM J.\u00a0Comput.\u00a039(1), 323\u2013360 (2009)","journal-title":"SIAM J.\u00a0Comput."},{"key":"55_CR41","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). In: Proc.\u00a0of STOC 1998, pp. 299\u2013308 (1998)","DOI":"10.1145\/276698.276769"},{"key":"55_CR42","unstructured":"Tamaki, S., Yoshida, Y.: A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness. Electronic Colloquium on Computational Complexity, TR09-074 (2009)"},{"key":"55_CR43","unstructured":"Zwick, U.: Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint. In: Proc.\u00a0of SODA 1998, pp. 201\u2013210 (1998)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:05:36Z","timestamp":1606187136000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}