☰

Shachar Lovett, Ph.D. - Publications

Affiliations: 
2010 Weizmann Institute of Science, Rehovot, Israel 
Area:
Mathematics, Computer Science
Tree Info Similar researchers PubMed Report error

33 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2019 Bansal N, Dadush D, Garg S, Lovett S. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues Theory of Computing. 15: 1-27. DOI: 10.4086/Toc.2019.V015A021  0.325
2019 Kane DM, Lovett S, Moran S. Near-optimal Linear Decision Trees for k-SUM and Related Problems Journal of the Acm. 66: 1-18. DOI: 10.1145/3285953  0.318
2018 Carmosino ML, Impagliazzo R, Lovett S, Mihajlin I. Hardness amplification for non-commutative arithmetic circuits Electronic Colloquium On Computational Complexity. 25: 16. DOI: 10.4230/Lipics.Ccc.2018.12  0.314
2018 Chattopadhyay E, Hatami P, Hosseini K, Lovett S. Pseudorandom generators from polarizing random walks Electronic Colloquium On Computational Complexity. 102: 21. DOI: 10.4230/Lipics.Ccc.2018.1  0.379
2018 Lovett S. A proof of the GM-MDS conjecture. Electronic Colloquium On Computational Complexity. 25: 47. DOI: 10.14288/1.0377638  0.305
2018 Hatami H, Hosseini K, Lovett S. Structure of Protocols for XOR Functions Siam Journal On Computing. 47: 208-217. DOI: 10.1137/17M1136869  0.303
2018 Applebaum B, Lovett S. Algebraic Attacks against Random Local Functions and Their Countermeasures Siam Journal On Computing. 47: 52-79. DOI: 10.1137/16M1085942  0.372
2018 Bhowmick A, Lovett S. The List Decoding Radius for Reed–Muller Codes Over Small Fields Ieee Transactions On Information Theory. 64: 4382-4391. DOI: 10.1109/Tit.2018.2822686  0.364
2017 Kuperberg G, Lovett S, Peled R. Probabilistic existence of regular combinatorial structures Geometric and Functional Analysis. 27: 919-972. DOI: 10.1007/S00039-017-0416-9  0.305
2016 HOSSEINI K, LOVETT S, MOSHKOVITZ G, SHAPIRA A. An improved lower bound for arithmetic regularity Mathematical Proceedings of the Cambridge Philosophical Society. 1-5. DOI: 10.1017/S030500411600013X  0.35
2016 Hatami H, Hatami P, Lovett S. General systems of linear forms: Equidistribution and true complexity Advances in Mathematics. 292: 446-477. DOI: 10.1016/J.Aim.2016.01.019  0.332
2015 Lovett S. An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem Theory of Computing. 6: 1-14. DOI: 10.4086/Toc.Gs.2015.006  0.347
2015 Göös M, Lovett S, Meka R, Watson T, Zuckerman D. Rectangles are nonnegative juntas Proceedings of the Annual Acm Symposium On Theory of Computing. 14: 257-266. DOI: 10.1137/15M103145X  0.346
2015 Lovett S, Meka R. Constructive discrepancy minimization by walking on the edges Siam Journal On Computing. 44: 1573-1582. DOI: 10.1137/130929400  0.33
2015 Gavinsky D, Lovett S, Saks M, Srinivasan S. A tail bound for read-k families of functions Random Structures and Algorithms. 47: 99-108. DOI: 10.1002/Rsa.20532  0.326
2014 Ben-Sasson E, Lovett S, Ron-Zewi N. An Additive Combinatorics Approach Relating Rank to Communication Complexity Journal of the Acm. 61: 22. DOI: 10.1145/2629598  0.327
2014 Bhowmick A, Dvir Z, Lovett S. New bounds for matching vector families Siam Journal On Computing. 43: 1654-1683. DOI: 10.1137/130932296  0.338
2014 Hatami H, Lovett S. Correlation testing for affine invariant properties on n pin the high error regime? Siam Journal On Computing. 43: 1417-1455. DOI: 10.1137/110831349  0.344
2014 Even-Zohar C, Lovett S. The Freiman-Ruzsa theorem over finite fields Journal of Combinatorial Theory. Series A. 125: 333-341. DOI: 10.1016/J.Jcta.2014.03.011  0.318
2013 Lovett S, Porat E. A space lower bound for dynamic approximate membership data structures Siam Journal On Computing. 42: 2182-2196. DOI: 10.1137/120867044  0.332
2013 Dvir Z, Kollár J, Lovett S. Variety Evasive Sets Computational Complexity. 23: 509-529. DOI: 10.1007/S00037-013-0073-9  0.358
2013 Lovett S, Mukhopadhyay P, Shpilka A. Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields Computational Complexity. 22: 679-725. DOI: 10.1007/s00037-012-0051-7  0.33
2012 Kaufman T, Lovett S, Porat E. Weight distribution and list-decoding size of reed-muller codes Ieee Transactions On Information Theory. 58: 2689-2696. DOI: 10.1109/Tit.2012.2184841  0.309
2012 Lovett S. Equivalence of polynomial conjectures in additive combinatorics Combinatorica. 32: 607-618. DOI: 10.1007/S00493-012-2714-Z  0.346
2012 Ben-Eliezer I, Hod R, Lovett S. Random low-degree polynomials are hard to approximate Computational Complexity. 21: 63-81. DOI: 10.1007/S00037-011-0020-6  0.386
2012 Alon N, Lovett S. Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7408: 350-361. DOI: 10.1007/978-3-642-32512-0_30  0.306
2011 Lovett S. Computing Polynomials with Few Multiplications Theory of Computing. 7: 185-188. DOI: 10.4086/Toc.2011.V007A013  0.333
2011 Hatami H, Lovett S. Higher-Order Fourier Analysis Of Fnp And The Complexity Of Systems Of Linear Forms Geometric and Functional Analysis. 21: 1331-1357. DOI: 10.1007/S00039-011-0141-8  0.316
2010 Lovett S. Holes in Generalized Reed-Muller codes Ieee Transactions On Information Theory. 56: 2583-2586. DOI: 10.1109/Tit.2010.2046206  0.337
2010 Lovett S, Mukhopadhyay P, Shpilka A. Pseudorandom generators for CC0[p] and the fourier spectrum of low-degree polynomials over finite fields Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 695-704. DOI: 10.1007/S00037-012-0051-7  0.422
2009 Lovett S, Reingold O, Trevisan L, Vadhan S. Pseudorandom bit generators that fool modular sums Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5687: 615-630. DOI: 10.1007/978-3-642-03685-9_46  0.594
2008 Lovett S. Unconditional pseudorandom generators for low degree polynomials Proceedings of the Annual Acm Symposium On Theory of Computing. 557-562. DOI: 10.4086/Toc.2009.V005A003  0.353
2008 Lovett S, Sodin S. Almost euclidean sections of the N-dimensional cross-polytope using O(N) random bits Communications in Contemporary Mathematics. 10: 477-489. DOI: 10.1142/S0219199708002879  0.341
Show low-probability matches.