{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:56:00Z","timestamp":1725566160848},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228943"},{"type":"electronic","value":"9783540278214"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27821-4_11","type":"book-chapter","created":{"date-parts":[[2010,9,14]],"date-time":"2010-09-14T18:54:06Z","timestamp":1284490446000},"page":"117-127","source":"Crossref","is-referenced-by-count":8,"title":["On Systems of Linear Equations with Two Variables per Equation"],"prefix":"10.1007","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Reichman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"11_CR1","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(97)00115-1","volume":"209","author":"E. Amaldi","year":"1998","unstructured":"Amaldi, E., Kann, V.: On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science\u00a0209(1-2), 237\u2013260 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"11_CR2","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1006\/jagm.2000.1154","volume":"39","author":"G. Andersson","year":"2001","unstructured":"Andersson, G., Engebretsen, L., H\u00e1stad, J.: A new way of using semidefinite programming with applications to linear equations mod p. Journal of Algorithms\u00a039(2), 162\u2013204 (2001)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences\u00a054(2), 317\u2013331 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR4","unstructured":"Arora, S., Lund, C.: Hardness of Approximations. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, PWS Publishing Company (1997)"},{"issue":"3","key":"11_CR5","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","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. ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/3-540-45726-7_18","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"L. Engebretsen","year":"2002","unstructured":"Engebretsen, L., Guruswami, V.: Is constraint satisfaction over two variables always easy? In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 224\u2013238. Springer, Heidelberg (2002)"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042, 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. Hastad","year":"2001","unstructured":"Hastad, J.: Some optimal inapproximability results. Journal of ACM\u00a048, 798\u2013859 (2001)","journal-title":"Journal of ACM"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: STOC, pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"11_CR10","unstructured":"S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-\u03b5. Proceedings of Computational Complexity, 2003."},{"key":"11_CR11","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 Journal of Computing\u00a027, 763\u2013803 (1998)","journal-title":"SIAM Journal of Computing"},{"issue":"6","key":"11_CR12","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.1137\/S0097539797328847","volume":"29","author":"L. Trevisan","year":"2000","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM Journal on Computing\u00a029(6), 2074\u20132097 (2000)","journal-title":"SIAM Journal on Computing"}],"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-540-27821-4_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:23:07Z","timestamp":1605759787000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27821-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228943","9783540278214"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27821-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}