{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,16]],"date-time":"2024-07-16T21:15:42Z","timestamp":1721164542742},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T00:00:00Z","timestamp":1612137600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T00:00:00Z","timestamp":1612137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s00493-020-4360-1","type":"journal-article","created":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T17:05:53Z","timestamp":1612199153000},"page":"545-579","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Lossless Dimension Expanders Via Linearized Polynomials and Subspace Designs"],"prefix":"10.1007","volume":"41","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[]},{"given":"Nicolas","family":"Resch","sequence":"additional","affiliation":[]},{"given":"Chaoping","family":"Xing","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,1]]},"reference":[{"key":"4360_CR1","first-page":"173","volume":"26","author":"D Aggarwal","year":"2019","unstructured":"D. Aggarwal, S. Guo, M. Obremski, J. Ribeiro and N. Stephens-Davidowitz: Extractor lower bounds, revisited, in: Electronic Colloquium on Computational Complexity (ECCC), volume 26, 173, 2019.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"4360_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/cjtcs.2014.009","volume":"9","author":"A Ben-Aroya","year":"2014","unstructured":"A. Ben-Aroya and I. Shinkar: A note on subspace evasive sets, Chicago Journal of Theoretical Computer Science 9 (2014), 1\u201311.","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"4360_CR3","unstructured":"B. Barak, R. Impagliazzo, A. Shpilka and A. Wigderson: Personal Communication to Dvir-Shpilka [8], 2004."},{"key":"4360_CR4","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.crma.2009.02.009","volume":"347","author":"J Bourgain","year":"2009","unstructured":"J. Bourgain: Expanders and dimensional expansion, Comptes Rendus Mathematique 347 (2009), 357\u2013362.","journal-title":"Comptes Rendus Mathematique"},{"key":"4360_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00039-012-0200-9","volume":"23","author":"J Bourgain","year":"2013","unstructured":"J. Bourgain and A. Yehudayoff: Expansion in SL2(\u211d) and monotone expanders, Geometric and Functional Analysis 23 (2013), 1\u201341, Preliminary version in the 44th Annual ACM Symposium on Theory of Computing (STOC 2012). This work is the full version of [4].","journal-title":"Geometric and Functional Analysis"},{"key":"4360_CR6","doi-asserted-by":"crossref","unstructured":"Z. Dvir and S. Lovett: Subspace evasive sets, in: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, 351\u2013358. ACM, 2012.","DOI":"10.1145\/2213977.2214010"},{"key":"4360_CR7","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1137\/05063605X","volume":"36","author":"Z Dvir","year":"2007","unstructured":"Z. Dvir and A. Shpilka: Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits, SIAM J. Comput. 36 (2007), 1404\u20131434, Preliminary Version in the 37th Annual ACM Symposium on Theory of Computing (STOC 2005).","journal-title":"SIAM J. Comput."},{"key":"4360_CR8","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s00493-011-2540-8","volume":"31","author":"Z Dvir","year":"2011","unstructured":"Z. Dvir and A. Shpilka: Towards dimension expanders over finite fields, Combinatorica 31 (2011), 305\u2013320.","journal-title":"Combinatorica"},{"key":"4360_CR9","doi-asserted-by":"publisher","first-page":"291","DOI":"10.4086\/toc.2010.v006a012","volume":"6","author":"Z Dvir","year":"2010","unstructured":"Z. Dvir and A. Wigderson: Monotone expanders: Constructions and applications, Theory of Computing 6 (2010), 291\u2013308.","journal-title":"Theory of Computing"},{"key":"4360_CR10","unstructured":"M. A. Forbes and V. Guruswami: Dimension expanders via rank condensers, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 800\u2013814, 2015."},{"key":"4360_CR11","doi-asserted-by":"crossref","unstructured":"M. A. Forbes and A. Shpilka: On identity testing of tensors, low-rank recovery and compressed sensing, in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 163\u2013172. ACM, 2012.","DOI":"10.1145\/2213977.2213995"},{"key":"4360_CR12","first-page":"1","volume":"21","author":"E M Gabidulin","year":"1985","unstructured":"E. M. Gabidulin: Theory of codes with maximum rank distance, Probl. Inform. Transm. 21 (1985), 1\u201312.","journal-title":"Probl. Inform. Transm."},{"key":"4360_CR13","doi-asserted-by":"crossref","unstructured":"A. Gabizon: Deterministic extractors for affine sources over large fields, in: Deterministic Extraction from Weak Random Sources, 33\u201353. Springer, 2011.","DOI":"10.1007\/978-3-642-14903-0_3"},{"key":"4360_CR14","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00493-014-3169-1","volume":"36","author":"V Guruswami","year":"2016","unstructured":"V. Guruswami and S. Kopparty: Explicit subspace designs, Combinatorica 36 (2016), 161\u2013185.","journal-title":"Combinatorica"},{"key":"4360_CR15","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TIT.2007.911222","volume":"54","author":"V Guruswami","year":"2008","unstructured":"V. Guruswami and A. Rudra: Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy, IEEE Transactions on Information Theory 54 (2008), 135\u2013150, Preliminary Version in the 38th Annual ACM Symposium on Theory of Computing (STOC 2006).","journal-title":"IEEE Transactions on Information Theory"},{"key":"4360_CR16","doi-asserted-by":"crossref","unstructured":"V. Guruswami: Linear-algebraic list decoding of folded Reed-Solomon codes, in: Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC 2011), 77\u201385, 2011.","DOI":"10.1109\/CCC.2011.22"},{"key":"4360_CR17","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/1538902.1538904","volume":"56","author":"V Guruswami","year":"2009","unstructured":"V. Guruswami, C. Umans and S. Vadhan: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes, Journal of the ACM (JACM) 56 (2009), 20.","journal-title":"Journal of the ACM (JACM)"},{"key":"4360_CR18","doi-asserted-by":"publisher","first-page":"3257","DOI":"10.1109\/TIT.2013.2246813","volume":"59","author":"V Guruswami","year":"2013","unstructured":"V. Guruswami and C. Wang: Linear-algebraic list decoding for variants of Reed-Solomon codes, IEEE Transactions on Information Theory 59 (2013), 3257\u20133268.","journal-title":"IEEE Transactions on Information Theory"},{"key":"4360_CR19","unstructured":"V. Guruswami and C. Wang: Evading subspaces over large fields and explicit list-decodable rank-metric codes, in: Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM 2014), 748\u2013761, 2014, full version at arXiv:1311.7084."},{"key":"4360_CR20","doi-asserted-by":"publisher","first-page":"2707","DOI":"10.1109\/TIT.2016.2544347","volume":"62","author":"V Guruswami","year":"2016","unstructured":"V. Guruswami, C. Wang and C. Xing: Explicit list-decodable rank-metric and subspace codes via subspace designs, IEEE Transactions on Information Theory 62 (2016), 2707\u20132718.","journal-title":"IEEE Transactions on Information Theory"},{"key":"4360_CR21","doi-asserted-by":"crossref","unstructured":"V. Guruswami and C. Xing: Folded codes from function field towers and improved optimal rate list decoding, in: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012), 339\u2013350, 2012, full version at arXiv:1204.4209.","DOI":"10.1145\/2213977.2214009"},{"key":"4360_CR22","doi-asserted-by":"crossref","unstructured":"V. Guruswami and C. Xing: List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound, in: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013), 843\u2013852. ACM, 2013.","DOI":"10.1145\/2488608.2488715"},{"key":"4360_CR23","doi-asserted-by":"publisher","first-page":"8757","DOI":"10.1090\/tran\/7369","volume":"370","author":"V Guruswami","year":"2018","unstructured":"V. Guruswami, C. Xing and C. Yuan: Subspace designs based on algebraic function fields, Transactions of the American Mathematical Society 370 (2018), 8757\u20138775.","journal-title":"Transactions of the American Mathematical Society"},{"key":"4360_CR24","doi-asserted-by":"publisher","first-page":"715","DOI":"10.26421\/QIC8.8-9-2","volume":"8","author":"A W Harrow","year":"2008","unstructured":"A. W. Harrow: Quantum expanders from any classical Cayley graph expander, Quantum Information & Computation 8 (2008), 715\u2013721.","journal-title":"Quantum Information & Computation"},{"key":"4360_CR25","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s00493-011-2537-3","volume":"31","author":"Z S Karnin","year":"2011","unstructured":"Z. S. Karnin and A. Shpilka: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in, Combinatorica 31 (2011), 333\u2013364.","journal-title":"Combinatorica"},{"key":"4360_CR26","doi-asserted-by":"crossref","unstructured":"R. Lidl and H. Niederreiter: Introduction to finite fields and their applications, Cambridge University Press, 1994.","DOI":"10.1017\/CBO9781139172769"},{"key":"4360_CR27","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1016\/j.jalgebra.2005.12.033","volume":"319","author":"A Lubotzky","year":"2008","unstructured":"A. Lubotzky and E. Zelmanov: Dimension expanders, Journal of Algebra 319 (2008), 730\u2013738.","journal-title":"Journal of Algebra"},{"key":"4360_CR28","doi-asserted-by":"crossref","unstructured":"H. Niederreiter and C. Xing: Algebraic geometry in coding theory and cryptography, Princeton University Press, 2009.","DOI":"10.2307\/j.ctvdtphcs"},{"key":"4360_CR29","series-title":"Quad. Mat.","first-page":"327","volume-title":"Complexity of computations and proofs","author":"P Pudl\u00e1k","year":"2004","unstructured":"P. Pudl\u00e1k and V. R\u00f6dl: Pseudorandom sets and explicit constructions of Ramsey graphs, in: Complexity of computations and proofs, volume 13 of Quad. Mat., 327\u2013346. Dept. Math., Seconda Univ. Napoli, Caserta, 2004."},{"key":"4360_CR30","unstructured":"F. Parvaresh and A. Vardy: Correcting errors beyond the Guruswami-Sudan radius in polynomial time, in: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 285\u2013294, 2005."},{"key":"4360_CR31","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1137\/S0895480197329508","volume":"13","author":"J Radhakrishnan","year":"2000","unstructured":"J. Radhakrishnan and A. Ta-Shma: Bounds for dispersers, extractors, and depth-two superconcentrators, SIAM Journal on Discrete Mathematics 13 (2000), 2\u201324.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4360_CR32","doi-asserted-by":"publisher","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O Reingold","year":"2002","unstructured":"O. Reingold, S. Vadhan and A. Wigderson: Entropy waves, the zig-zag graph product, and new constant-degree expanders, Annals of Mathematics 155 (2002), 157\u2013187.","journal-title":"Annals of Mathematics"},{"key":"4360_CR33","doi-asserted-by":"crossref","unstructured":"H. Stichtenoth: Algebraic function fields and codes, volume 254, Springer Science & Business Media, 2009.","DOI":"10.1007\/978-3-540-76878-4"},{"key":"4360_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000010","volume":"7","author":"S P Vadhan","year":"2012","unstructured":"S. P. Vadhan: Pseudorandomness, Foundations and Trends@ in Theoretical Computer Science 7 (2012), 1\u2013336.","journal-title":"Foundations and Trends@ in Theoretical Computer Science"},{"key":"4360_CR35","unstructured":"A. Wigderson: Expanders: Old and new applications and problems, Lecture at the Institute for Pure and Applied Mathematics (IPAM), February 2004."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4360-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-020-4360-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4360-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T06:41:03Z","timestamp":1671000063000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-020-4360-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,1]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["4360"],"URL":"https:\/\/doi.org\/10.1007\/s00493-020-4360-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,1]]},"assertion":[{"value":"19 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}