{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:55:03Z","timestamp":1725512103537},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540792277"},{"type":"electronic","value":"9783540792284"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79228-4_9","type":"book-chapter","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T05:07:56Z","timestamp":1209445676000},"page":"105-115","source":"Crossref","is-referenced-by-count":0,"title":["Derandomizing Graph Tests for Homomorphism"],"prefix":"10.1007","author":[{"given":"Angsheng","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Linqing","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Ben-Or","year":"2004","unstructured":"Ben-Or, M., Coppersmith, D., Luby, M., Rubinfeld, R.: Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004. LNCS, vol.\u00a03122, Springer, Heidelberg (2004)"},{"issue":"3","key":"9_CR2","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. Journal of Computer and System Sciences\u00a047(3), 549\u2013595 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Shpilka, A., Wigderson, A.: Derandomizing Homomorphism Testing in General Groups. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 427\u2013435 (2004)","DOI":"10.1145\/1007352.1007421"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Portland, OR, USA, May 21-23, 2000, pp. 191\u2013199 (2000)","DOI":"10.1145\/335305.335329"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Deterministic simulation in LOGSPACE. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 132\u2013140 (1987)","DOI":"10.1145\/28395.28410"},{"issue":"2","key":"9_CR6","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 Structures and Algorithms\u00a022(2), 139\u2013160 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"9_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algoriths and Probabilistic Analysis","author":"M. Mitzwnmacher","year":"2005","unstructured":"Mitzwnmacher, M., Upfal, E.: Probability and Computing: Randomized Algoriths and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Dinur, I.: The PCP Theorem by Gap Amplification. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 241\u2013250 (2006)","DOI":"10.1145\/1132516.1132553"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0012-365X(88)90189-6","volume":"72","author":"N. Alon","year":"1988","unstructured":"Alon, N., Chung, F.R.K.: Explicit construction of linear sized tolerant networks. Discrete Mathematics\u00a072, 15\u201319 (1988)","journal-title":"Discrete Mathematics"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Bellare, M., Coppersmith, D., Hastad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. In: The 36th Annual Symposium on Foundations of Computer Science, p. 432 (1995)","DOI":"10.1109\/SFCS.1995.492574"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M., Vadhan, S., Wigderson, A.: Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets. In: Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, June 9-11, pp. 612\u2013621 (2003)","DOI":"10.1145\/780542.780631"},{"key":"9_CR12","unstructured":"Wigderson, A., Xiao, D.: Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications. In: ECCC TR06-105 (2006)"},{"issue":"4","key":"9_CR13","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small Bias Probability Spaces: Efficient Constructions and Applications. SIAM Journal on Computing\u00a022(4), 838\u2013856 (1993)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79228-4_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:14:29Z","timestamp":1619522069000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79228-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540792277","9783540792284"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79228-4_9","relation":{},"subject":[]}}