{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T05:26:16Z","timestamp":1737523576001,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_41","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"493-505","source":"Crossref","is-referenced-by-count":11,"title":["Testing Hypergraph Coloring"],"prefix":"10.1007","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"41_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. In Proc. 40th FOCS, pages 656\u2013666, 1999.","DOI":"10.1109\/SFFCS.1999.814642"},{"key":"41_CR2","first-page":"425","volume":"3","author":"N. Alon","year":"1996","unstructured":"N. Alon, P. Kelsen, S. Mahajan, and H. Ramesh. Coloring 2-colorable hypergraphs with a sublinear number of colors. Nordic Journal of Computing, 3:425\u2013439, 1996.","journal-title":"Nordic Journal of Computing"},{"key":"41_CR3","unstructured":"N. Alon and M. Krivelevich. To appear in SIAM Journal on Discrete Mathematics."},{"issue":"1","key":"41_CR4","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"1999","unstructured":"Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. Balanced allocations. SIAM Journal on Computing, 29(1):180\u2013200, September 1999.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"41_CR5","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J. Beck","year":"1991","unstructured":"J. Beck. An algorithmic approach to the Lov\u00e1sz local lemma. I. Random Structures and Algorithms, 2(4):343\u2013365, 1991.","journal-title":"Random Structures and Algorithms"},{"issue":"3","key":"41_CR6","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"M. Blum, M. Luby, and R. Rubinfeld. Self-testing\/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47(3):549\u2013595, December 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"41_CR7","doi-asserted-by":"crossref","unstructured":"M. A. Bender and D. Ron. Testing acyclity of directed graphs in sublinear time. In Proc. 27th ICALP, pages 809\u2013820, 2000.","DOI":"10.1007\/3-540-45022-X_68"},{"key":"41_CR8","doi-asserted-by":"crossref","unstructured":"H. Chen and A. Frieze. Coloring bipartite hypergraphs. In Proc. 5th IPCO, pages 345\u2013358, 1996.","DOI":"10.1007\/3-540-61310-2_26"},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"A. Czumaj and C. Scheideler. An algorithmic approach to the general Lov\u00e1sz Local Lemma with applications to scheduling and satisfiability problems. In Proc. 32nd STOC, pages 38\u201347, 2000.","DOI":"10.1145\/335305.335310"},{"key":"41_CR10","unstructured":"A. Czumaj and C. Scheideler. Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lov\u00e1sz Local Lemma. In Proc. 11th SODA, pages 30\u201339, 2000."},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"A. Czumaj, C. Sohler, and M. Ziegler. Property testing in computational geometry. In Proc. 8th ESA, pages 155\u2013166, 2000.","DOI":"10.1007\/3-540-45253-2_15"},{"key":"41_CR12","first-page":"609","volume-title":"Infinite and Finite Sets (to Paul Erd\u0151s on his 60th birthday)","author":"P. Erd\u0151s","year":"1975","unstructured":"P. Erd\u0151s and L. Lov\u00e1sz. Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal, R. Rado, and V. T. S\u00f3s, editors, Infinite and Finite Sets (to Paul Erd\u0151s on his 60th birthday), volume II, pages 609\u2013627. North-Holland, Amsterdam, 1975."},{"key":"41_CR13","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F. Erg\u00fcn","year":"2000","unstructured":"F. Erg\u00fcn, S. Kannan, S. R. Kumar, R. Rubinfeld, and M. Viswanathan. Spot-checkers. Journal of Computer and System Sciences, 60:717\u2013751, 2000.","journal-title":"Journal of Computer and System Sciences"},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"F. Erg\u00fcn, S. Ravi Kumar, and R. Rubinfeld. Approximate checking of polynomials and functional equations. In Proc. 37th FOCS, pages 592\u2013601, 1996.","DOI":"10.1109\/SFCS.1996.548518"},{"key":"41_CR15","unstructured":"E. Fischer. Testing graphs for colorability properties. In Proc. 12th SODA, pages 873\u2013882, 2001."},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"E. Fischer and I. Newman. Testing of matrix properties. To appear in Proc. 33rd STOC, 2001.","DOI":"10.1145\/380752.380812"},{"key":"41_CR17","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s004930050052","volume":"19","author":"A. Frieze","year":"1999","unstructured":"A. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinatorica, 19:175\u2013220, 1999.","journal-title":"Combinatorica"},{"issue":"4","key":"41_CR18","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653\u2013750, July 1998.","journal-title":"Journal of the ACM"},{"issue":"3","key":"41_CR19","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"O. Goldreich","year":"1999","unstructured":"O. Goldreich and D. Ron. A sublinear bipartiteness tester for bounded degree graphs. Combinatorica, 19(3):335\u2013373, 1999.","journal-title":"Combinatorica"},{"key":"41_CR20","doi-asserted-by":"crossref","unstructured":"V. Guruswami, J. H\u00e5stad, and M. Sudan. Hardness of approximate hypergraph coloring. In Proc. 41st FOCS, pages 149\u2013158, 2000.","DOI":"10.1109\/SFCS.2000.892074"},{"key":"41_CR21","doi-asserted-by":"crossref","unstructured":"M. Krivelevich, R. Nathaniel, and B. Sudakov. Approximating coloring and maximum independent sets in 3-uniform hypergraphs. In Proc. 12th SODA, pages 327\u2013328, 2001.","DOI":"10.1006\/jagm.2001.1173"},{"key":"41_CR22","doi-asserted-by":"crossref","unstructured":"M. Krivelevich and B. Sudakov. Approximate coloring of uniform hypergraphs. In Proc. 6th ESA, pages 477\u2013489, 1998.","DOI":"10.1007\/3-540-68530-8_40"},{"key":"41_CR23","unstructured":"L. Lov\u00e1sz. Coverings and colorings of hypergraphs. In Proc. 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pages 3\u201312. 1973."},{"key":"41_CR24","doi-asserted-by":"crossref","unstructured":"C-J. Lu. Deterministic hypergraph coloring and its applications. In Proc. 2nd RANDOM, pages 35\u201346, 1998.","DOI":"10.1007\/3-540-49543-6_4"},{"key":"41_CR25","doi-asserted-by":"crossref","unstructured":"I. Newman. Testing of function that have small width branching programs. In Proc. 41st FOCS, pages 251\u2013258, 2000.","DOI":"10.1109\/SFCS.2000.892112"},{"key":"41_CR26","doi-asserted-by":"crossref","unstructured":"M. Parnas and D. Ron. Testing metric properties. To appear in Proc. 33rd STOC, 2001.","DOI":"10.1145\/380752.380811"},{"key":"41_CR27","doi-asserted-by":"crossref","unstructured":"J. Radhakrishnan and A. Srinivasan. Improved bounds and algorithms for hypergraph two-coloring. In Proc. 39th FOCS, pages 684\u2013693, 1998.","DOI":"10.1109\/SFCS.1998.743519"},{"key":"41_CR28","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02582932","volume":"1","author":"V. R\u00f6dl","year":"1985","unstructured":"V. R\u00f6dl and R. A. Duke. On graphs with small subgraphs of large chromatic number. Graphs and Combinatorics, 1:91\u201396, 1985.","journal-title":"Graphs and Combinatorics"},{"key":"41_CR29","doi-asserted-by":"crossref","unstructured":"D. Ron. Property testing. To appear in P. M. Pardalos, S. Rajasekaran, J. Reif, and J. D. P. Rolim, editors, Handobook of Randomized Algorithms. Kluwer Academic Publishers, 2001.","DOI":"10.1007\/978-1-4615-0013-1_15"},{"key":"41_CR30","doi-asserted-by":"crossref","unstructured":"R. Rubinfeld. Robust functional equations and their applications to program testing. In Proc. 35th FOCS, pages 288\u2013299, 1994.","DOI":"10.1109\/SFCS.1994.365686"},{"issue":"2","key":"41_CR31","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"R. Rubinfeld and M. Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252\u2013271, April 1996.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:50:15Z","timestamp":1737503415000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}