{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T09:28:29Z","timestamp":1746523709528,"version":"3.32.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1007\/bf01196133","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T14:51:37Z","timestamp":1108738297000},"page":"79-90","source":"Crossref","is-referenced-by-count":28,"title":["Randomized graph products, chromatic numbers, and the Lov\ufffdsz ?-function"],"prefix":"10.1007","volume":"17","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","unstructured":"N. Alon, N. Kahale: Approximating the independence number via the ?-function.Manuscript, November 1994."},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy: Proof verification and hardness of approximation problems.Proc. of 33rd IEEE Symp. on Foundations of Computer Science, 1992, 14?23.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"S. Arora, S. Safra: Probabilistic checking of proofs: a new characterization of NP.Proc. of 33rd IEEE Symp. on Foundations of Computer Science, 1992, 2?13.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"M. Bellare, O. Goldreich, M. Sudan: Free bits, PCPs and nonapproximability-towards tight results.Proc. of 36th IEEE Symp. on Foundations of Computer Science, 1995, 422?431.","DOI":"10.1109\/SFCS.1995.492573"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman, G. Schnitger: On the complexity of approximating the independent set problem,Information and Computation 96 (1992), 77?94.","journal-title":"Information and Computation"},{"key":"CR6","unstructured":"A. Blum: Algorithms for approximate graph coloring, Phd dissertation, MIT, 1991."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1145\/176584.176586","volume":"41","author":"A. Blum","year":"1994","unstructured":"A. Blum: New approximation algorithms for graph coloring.Journal of the ACM,41 (1994), 470?516.","journal-title":"Journal of the ACM"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"R. Boppana, M. Haldorsson: Approximating maximum independent sets by excluding subgraphs,Proc. of 2nd SWAT, Springer, LNCS 447 (1990), 13?25.","DOI":"10.1007\/3-540-52846-6_74"},{"issue":"2","key":"CR9","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"U. Feige, S. Goldwasser, L. Lov\ufffdsz, S. Safra, M. Szegedy: Interactive proofs and the hardness of approximating cliques,Journal of the ACM,43(2) (1996), 268?292.","journal-title":"Journal of the ACM"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"U. Feige, J. Kilian: Zero knowledge and the chromatic number,Proc. of Eleventh Annual IEEE Conference on Computational Complexity, 1996, 278?287.","DOI":"10.1109\/CCC.1996.507690"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579457","volume":"1","author":"P. Frankl","year":"1981","unstructured":"P. Frankl, R. Wilson: Intersection theorems with geometric consequences,Combinatorica 1 (1981), 357?368.","journal-title":"Combinatorica"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"M. Furer: Improved hardness results for approximating the chromatic number,Proc. of 36th IEEE Symp. on Foundations of Computer Science, (1995), 414?421.","DOI":"10.1109\/SFCS.1995.492572"},{"issue":"6","key":"CR13","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"M. Goemans, D. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,Journal of the ACM,42(6) (1995), 1115?1145.","journal-title":"Journal of the ACM"},{"key":"CR14","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Grotschel","year":"1987","unstructured":"M. Grotschel, L. Lov\ufffdsz, A. Schrijver:Geometric algorithms and combinatorial optimization, Springer-Verlag, Berlin, 1987."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"J. Hastad: Clique is hard to approximate withinn 1??,Proc. of 37th IEEE Symposium of Foundations of Computer Science, 1996, 627?636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"W. Hoeffding: Probability inequalities for sums of bounded random variables,Journal of the American Statistical Association,58 (1963), 13?30.","journal-title":"Journal of the American Statistical Association"},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"D. Karger, R. Motwani, M. Sudan: Approximate Graph Coloring by Semidefinite Programming,Proc. of 35th IEEE Symp. on Foundations of Computer Science, (1994), 2?13.","DOI":"10.1109\/SFCS.1994.365710"},{"key":"CR18","first-page":"1","volume":"1","author":"D. Knuth","year":"1994","unstructured":"D. Knuth: The sandwich theorem,Electronic J. Comp.,1 (1994), 1?48.","journal-title":"Electronic J. Comp."},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"N. Linial, U. Vazirani: Graph products and chromatic numbers,Proc. of 30th IEEE Symp. on Foundations of Computer Science, (1989), 124?128.","DOI":"10.1109\/SFCS.1989.63466"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\ufffdsz","year":"1975","unstructured":"L. Lov\ufffdsz: On the ratio of the optimal integral and fractional covers,Discrete Mathematics,13 (1975), 383?390.","journal-title":"Discrete Mathematics"},{"issue":"No. 1","key":"CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\ufffdsz","year":"1979","unstructured":"L. Lov\ufffdsz: On the Shannon Capacity of a Graph,IEEE Trans. on Information Theory, Vol. IT-25, No. 1, 1979, 1?7.","journal-title":"IEEE Trans. on Information Theory"},{"issue":"5","key":"CR22","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund, M. Yannakakis: On the hardness of approximating minimization problems,Journal of the ACM,41(5) (1994), 960?981.","journal-title":"Journal of the ACM"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J. Moon","year":"1965","unstructured":"J. Moon, L. Moser: On cliques in graphsIsrael J. Math.,3 (1965), 23?28.","journal-title":"Israel J. Math."},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"M. Szegedy: A note on the ? number of Lov\ufffdsz and the generalized Delsarte bound,Proc. of 35th IEEE Symp. on Foundations of Computer Science, (1994), 36?39.","DOI":"10.1109\/SFCS.1994.365707"},{"issue":"4","key":"CR25","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A. Wigderson","year":"1983","unstructured":"A. Wigderson: Improving the performance guarantee for approximate graph coloring,Journal of the ACM,30(4) (1983), 729?735.","journal-title":"Journal of the ACM"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01196133.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01196133\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01196133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:42:44Z","timestamp":1734957764000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01196133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["BF01196133"],"URL":"https:\/\/doi.org\/10.1007\/bf01196133","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}