{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:17:17Z","timestamp":1725664637511},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602460"},{"type":"electronic","value":"9783540447689"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60246-1_126","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:55:21Z","timestamp":1330278921000},"page":"201-210","source":"Crossref","is-referenced-by-count":1,"title":["Derandomization for sparse approximations and independent sets"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Hofmeister","sequence":"first","affiliation":[]},{"given":"Hanno","family":"Lefmann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/BF02579451","volume":"1","author":"M. Ajtai","year":"1981","unstructured":"M. Ajtai, P. Erd\u00f6s, J. Koml\u00f3s and E. Szemer\u00e9di, On Tur\u00e1n's Theorem for Sparse Graphs, Combinatorica 1, 313\u2013317 (1981).","journal-title":"Combinatorica"},{"key":"18_CR2","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/0097-3165(80)90030-8","volume":"29","author":"M. Ajtai","year":"1980","unstructured":"M. Ajtai, J. Koml\u00f3s and E. Szemer\u00e9di, A Note on Ramsey Numbers, J. of Combinatorial Theory, Ser. A 29, 354\u2013360 (1980).","journal-title":"J. of Combinatorial Theory, Ser. A"},{"key":"18_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0195-6698(81)80014-5","volume":"2","author":"M. Ajtai","year":"1981","unstructured":"M. Ajtai, J. Koml\u00f3s and E. Szemer\u00e9di, A Dense Infinite Sidon Sequence, European J. of Combinatorics 2, 2\u201311 (1981).","journal-title":"European J. of Combinatorics"},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/0024-3795(94)90357-3","volume":"199","author":"I. Alth\u00f6fer","year":"1994","unstructured":"I. Alth\u00f6fer, On Sparse Approximations to Randomized Strategies and Convex Combinations, Linear Algebra and its Applications 199, 339\u2013355 (1994).","journal-title":"Linear Algebra and its Applications"},{"key":"18_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0895480191218496","volume":"7","author":"N. Alon","year":"1994","unstructured":"N. Alon and J. Bruck, Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition, SIAM J. on Discrete Mathematics 7, 1994, 1\u20138.","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"18_CR6","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon, J. Spencer and P. Erd\u00f6s, The Probabilistic Method, Wiley & Sons, New York (1992)."},{"key":"18_CR7","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0221003","volume":"21","author":"J. Bruck","year":"1992","unstructured":"J. Bruck and R. Smolensky, Polynomial Threshold Functions, AC\n0\nFunctions and Spectral Norms, SIAM J. on Computing 21, 33\u201342 (1992).","journal-title":"SIAM J. on Computing"},{"key":"18_CR8","unstructured":"M. Halld\u00f3rsson and J. Radhakrishnan, Greed is Good: Approximating Independent Sets in Sparse and Bounded-degree Graphs, Proc. 26th ACM Symp. on Theory of Computing (STOC), 439\u2013448 (1994)."},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"R. J. Lipton and N. E. Young, Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory, Proc. 26th ACM Symp. on Theory of Computing (STOC), 734\u2013740 (1994).","DOI":"10.1145\/195058.195447"},{"key":"18_CR10","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan, Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs, J. of Computer and System Sciences 37, 130\u2013143 (1988).","journal-title":"J. of Computer and System Sciences"},{"key":"18_CR11","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0012-365X(83)90273-X","volume":"46","author":"J. Shearer","year":"1983","unstructured":"J. Shearer, A Note on the Independence Number of Triangle-free Graphs, Discrete Mathematics 46, 83\u201387 (1983).","journal-title":"Discrete Mathematics"},{"key":"18_CR12","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0095-8956(91)90080-4","volume":"53","author":"J. Shearer","year":"1991","unstructured":"J. Shearer, A Note on the Independence Number of Triangle-free Graphs, II, J. of Combinatorial Theory 53, 300\u2013307 (1991).","journal-title":"J. of Combinatorial Theory"},{"key":"18_CR13","unstructured":"N. E. Young, Greedy Algorithms by Derandomizing Unknown Distributions, preprint (1994). See also: Randomized Rounding without Solving the Linear Program, Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (SODA), to appear (1995)."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1995"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60246-1_126.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:34:07Z","timestamp":1619573647000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60246-1_126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602460","9783540447689"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-60246-1_126","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}