{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:33:44Z","timestamp":1774679624937,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T00:00:00Z","timestamp":1307318400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2011,6,6]]},"DOI":"10.1145\/1993636.1993721","type":"proceedings-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:53:52Z","timestamp":1307361232000},"page":"637-644","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Breaking the k\n            <sup>2<\/sup>\n            barrier for explicit RIP matrices"],"prefix":"10.1145","author":[{"given":"Jean","family":"Bourgain","sequence":"first","affiliation":[{"name":"Institute For Advanced Study, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen J.","family":"Dilworth","sequence":"additional","affiliation":[{"name":"University of South Carolina, Columbia, SC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Ford","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergei V.","family":"Konyagin","sequence":"additional","affiliation":[{"name":"Steklov Mathematical Institute, Moscow, Russian Fed."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denka","family":"Kutzarova","sequence":"additional","affiliation":[{"name":"Bulgarian Academy of Sciences, Sofia, Bulgaria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6,6]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-007-9003-x"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2008.4797639"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00303-2"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-008-0691-6"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-1384809"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004108001230"},{"key":"e_1_3_2_2_8_1","volume-title":"Exponential sum estimate over subgroup in an arbitrary finite field. preprint","author":"Bourgain J.","year":"2010","unstructured":"J. Bourgain and A. A. Glibichuk . Exponential sum estimate over subgroup in an arbitrary finite field. preprint , 2010 . J. Bourgain and A. A. Glibichuk. Exponential sum estimate over subgroup in an arbitrary finite field. preprint, 2010."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2008.03.014"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.885507"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2007.04.002"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2007.01.004"},{"key":"e_1_3_2_2_15_1","first-page":"243","volume-title":"Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Gilbert A. C.","year":"2003","unstructured":"A. C. Gilbert , S. Mutukrishnan , and M. J. Strauss . Approximation of functions over redundant dictionaries using coherence . In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 243 -- 252 , 2003 . A. C. Gilbert, S. Mutukrishnan, and M. J. Strauss. Approximation of functions over redundant dictionaries using coherence. In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 243--252, 2003."},{"key":"e_1_3_2_2_16_1","volume-title":"i Prilozhen., 20(1):14--20, 96","author":"Gluskin E. D.","year":"1986","unstructured":"E. D. Gluskin . An octahedron is poorly approximated by random subspaces. Funktsional . Anal. i Prilozhen., 20(1):14--20, 96 , 1986 . E. D. Gluskin. An octahedron is poorly approximated by random subspaces. Funktsional. Anal. i Prilozhen., 20(1):14--20, 96, 1986."},{"key":"e_1_3_2_2_17_1","unstructured":"S. Gurevich and R. Hadani. The statistical restricted isometry property and the Wigner semicircle distribution of incoherent dictionaries. preprint arXiv:0812.2602.  S. Gurevich and R. Hadani. The statistical restricted isometry property and the Wigner semicircle distribution of incoherent dictionaries. preprint arXiv:0812.2602."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1779-2"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"issue":"5","key":"e_1_3_2_2_20_1","first-page":"682","article-title":"Double Kloosterman sums","volume":"66","author":"Karatsuba A. A.","year":"1999","unstructured":"A. A. Karatsuba . Double Kloosterman sums . Mat. Zametki , 66 ( 5 ): 682 -- 687 , 1999 . Russian. English translation in Math. Notes 66 (1999), no. 5--6, 565--569. A. A. Karatsuba. Double Kloosterman sums. Mat. Zametki, 66(5):682--687, 1999. Russian. English translation in Math. Notes 66 (1999), no. 5--6, 565--569.","journal-title":"Mat. Zametki"},{"key":"e_1_3_2_2_21_1","first-page":"251","article-title":"On widths of octahedron","volume":"30","author":"Kashin B. S.","year":"1975","unstructured":"B. S. Kashin . On widths of octahedron . Uspekhi Matem. Nauk , 30 : 251 -- 252 , 1975 . Russian. B. S. Kashin. On widths of octahedron. Uspekhi Matem. Nauk, 30:251--252, 1975. Russian.","journal-title":"Uspekhi Matem. Nauk"},{"key":"e_1_3_2_2_22_1","first-page":"334","article-title":"Widths of certain finite-dimensional sets and classes of smooth functions. Izv. Akad. Nauk SSSR","volume":"41","author":"Kashin B. S.","year":"1977","unstructured":"B. S. Kashin . Widths of certain finite-dimensional sets and classes of smooth functions. Izv. Akad. Nauk SSSR , Ser. Mat. , 41 : 334 -- 351 , 1977 . Russian. English transl. in Math. USSR Izv. 11 (1978), 317--333. B. S. Kashin. Widths of certain finite-dimensional sets and classes of smooth functions. Izv. Akad. Nauk SSSR, Ser. Mat., 41:334--351, 1977. Russian. English transl. in Math. USSR Izv. 11 (1978), 317--333.","journal-title":"Ser. Mat."},{"key":"e_1_3_2_2_23_1","unstructured":"V. I. Levenshtein. Bounds for packings of metric spaces and some of their applications. Problemy Kibernet (40):43--110 1983. Russian.  V. I. Levenshtein. Bounds for packings of metric spaces and some of their applications. Problemy Kibernet (40):43--110 1983. Russian."},{"key":"e_1_3_2_2_24_1","volume-title":"Orthogonal super greedy algorithm and applications in compressed sensing. preprint","author":"Liu E.","year":"2010","unstructured":"E. Liu and V. N. Temlyakov . Orthogonal super greedy algorithm and applications in compressed sensing. preprint , 2010 . E. Liu and V. N. Temlyakov. Orthogonal super greedy algorithm and applications in compressed sensing. preprint, 2010."},{"key":"e_1_3_2_2_25_1","volume-title":"On efficiency of Orthogonal Matching Pursuit. preprint","author":"Livshitz E.","year":"2010","unstructured":"E. Livshitz . On efficiency of Orthogonal Matching Pursuit. preprint , 2010 , ArXiv : 1004.3946. E. Livshitz. On efficiency of Orthogonal Matching Pursuit. preprint, 2010, ArXiv: 1004.3946."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0618-7"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-008-9031-3"},{"key":"e_1_3_2_2_28_1","volume-title":"On the size of incoherent systems. preprint","author":"Nelson J.","year":"2010","unstructured":"J. Nelson and V. N. Temlyakov . On the size of incoherent systems. preprint , 2010 . J. Nelson and V. N. Temlyakov. On the size of incoherent systems. preprint, 2010."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20227"},{"key":"e_1_3_2_2_30_1","unstructured":"T. Tao. Open question: deterministic uup matrices. http:\/\/terrytao.wordpress.com (2007 July 02).  T. Tao. Open question: deterministic uup matrices. http:\/\/terrytao.wordpress.com (2007 July 02)."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755149"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300008913"}],"event":{"name":"STOC'11: Symposium on Theory of Computing","location":"San Jose California USA","acronym":"STOC'11","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-third annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993636.1993721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:11Z","timestamp":1750244771000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,6]]},"references-count":32,"alternative-id":["10.1145\/1993636.1993721","10.1145\/1993636"],"URL":"https:\/\/doi.org\/10.1145\/1993636.1993721","relation":{},"subject":[],"published":{"date-parts":[[2011,6,6]]},"assertion":[{"value":"2011-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}