{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:21:27Z","timestamp":1725549687776},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281016"},{"type":"electronic","value":"9783540317111"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11534273_35","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T08:31:47Z","timestamp":1268382707000},"page":"396-408","source":"Crossref","is-referenced-by-count":1,"title":["Derandomization of Dimensionality Reduction and SDP Based Algorithms"],"prefix":"10.1007","author":[{"given":"Ankur","family":"Bhargava","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Rao","family":"Kosaraju","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D.: Database-Friendly Random Projections. In: Proceedings of the 20th ACM Symposium on Principles of Database Systems, pp. 274\u2013281 (2001)","DOI":"10.1145\/375551.375608"},{"issue":"3","key":"35_CR2","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF01581168","volume":"80","author":"N. Alon","year":"1998","unstructured":"Alon, N., Kahale, N.: Approximating the Independence Number via the \u03b8-Function. Mathematical Programming\u00a080(3), 253\u2013264 (1998)","journal-title":"Mathematical Programming"},{"key":"35_CR3","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley Inter-science Series in Discrete Mathematics and Optimization (1991)"},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"Arriaga, R.I., Vempala, S.: An Algorithmic Theory of Learning: Robust Concepts and Random Projection. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, pp. 616\u2013623 (1999)","DOI":"10.1109\/SFFCS.1999.814637"},{"key":"35_CR5","unstructured":"Berger, B.: The Fourth Moment Method. In: Proceedings of the 2nd Annual ACM SIAM Symposium on Discrete Algorithms, pp. 373\u2013383 (1991)"},{"key":"35_CR6","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J. Bourgain","year":"1985","unstructured":"Bourgain, J.: On Lipschitz Embedding of Finite Metric Spaces in Hilbert Space. Israeli Journal of Mathematics\u00a052, 46\u201352 (1985)","journal-title":"Israeli Journal of Mathematics"},{"issue":"1","key":"35_CR7","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S. Dasgupta","year":"2003","unstructured":"Dasgupta, S., Gupta, A.: An Elementary Proof of a Theorem of Johnson and Lindenstrauss. Random Structures and Algorithms\u00a022(1), 60\u201365 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"35_CR8","unstructured":"Engebretsen, L., Indyk, P., O\u2019Donnell, R.: Derandomized Dimensionality Reduction with Applications. In: Proceedings of the 13th Annual ACM SIAM Symposium on Discrete Algorithms, pp. 705\u2013712 (2002)"},{"key":"35_CR9","unstructured":"Feller, W.: An Introduction to Probability Theory and its Applications, volumes 1 & 2, 3rd ed., Wiley Series in Probability and Mathematical Statistics (1970)"},{"issue":"3","key":"35_CR10","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","volume":"44","author":"P. Frankl","year":"1987","unstructured":"Frankl, P., Maehara, H.: The Johnson-Lindenstrauss Lemma and the Sphericity of Some Graphs. Journal of Combinatorial Theory Series A\u00a044(3), 355\u2013362 (1987)","journal-title":"Journal of Combinatorial Theory Series A"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"Frieze, A., Jerrum, M.: Improved Approximation Algorithms for Max k-Cut and Max Bisection. In: Proceedings of the 3rd International Conference on Integer Programming and Combinatorial Optimization, pp. 1\u201313 (1995)","DOI":"10.1007\/3-540-59408-6_37"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Goemans, M., Williamson, D.: 0.878 Approximation Algorithms for MAX CUT and MAX 2SAT. In: Proceedings of the 26th Annual Symposium on the Theory of Computing, pp. 422\u2013431 (1994)","DOI":"10.1145\/195058.195216"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In: Proceedings of the 30th Annual Symposium on the Theory of Computing, pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"key":"35_CR14","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W.B. Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz Mappings into Hilbert Space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"Karger, D., Motwani, R., Sudan, M.: Approximate Graph Coloring by Semidefinite Programming. In: Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp. 1\u201310 (1994)","DOI":"10.1109\/SFCS.1994.365710"},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"Linial, N., London, E., Rabinovich, Y.: The Geometry of Graphs and Some of its Algorithmic Applications. In: Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp. 577\u2013591 (1994)","DOI":"10.1109\/SFCS.1994.365733"},{"key":"35_CR17","doi-asserted-by":"crossref","unstructured":"Mahajan, S., Ramesh, H.: Derandomizing Semidefinite Programming Based Approximation Algorithms. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, pp. 162\u2013169 (1995)","DOI":"10.1109\/SFCS.1995.492473"},{"key":"35_CR18","series-title":"Lecture Notes in Mathematics","volume-title":"Asymptotic Theory of Finite Dimensional Spaces","author":"V.D. Milman","year":"1980","unstructured":"Milman, V.D., Schechtman, G.: Asymptotic Theory of Finite Dimensional Spaces. Lecture Notes in Mathematics. Springer, Heidelberg (1980)"},{"key":"35_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"35_CR20","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/S0036144595288554","volume":"39","author":"V.Y. Pan","year":"1997","unstructured":"Pan, V.Y.: Solving a Polynomial Equation: Some History and Recent Progress. SIAM Review\u00a039(2), 187\u2013220 (1997)","journal-title":"SIAM Review"},{"key":"35_CR21","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Problems. Journal of Computer and System Sciences\u00a037, 130\u2013143 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR22","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized Rounding: A Technique for Provably Algorithms and Algorithmic Proofs. Combinatorica\u00a07, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"35_CR23","doi-asserted-by":"crossref","unstructured":"Sivakumar, D.: Algorithmic Derandomization via Complexity Theory. In: Proceedings of the 34th Annual Symposium on the Theory of Computing, pp. 619\u2013626 (2002)","DOI":"10.1145\/509907.509996"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11534273_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:10:01Z","timestamp":1605625801000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11534273_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281016","9783540317111"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11534273_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}