default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDShachar Lovett
Person information
- affiliation: University of California at San Diego, La Jolla, CA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Journal Articles
- 2024
[j47]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Realizable Learning is All You Need. TheoretiCS 3 (2024)- 2023
- [j46]Abhishek Bhowmick
, Shachar Lovett:
Bias vs Structure of Polynomials in Large Fields, and Applications in Information Theory. IEEE Trans. Inf. Theory 69(2): 963-977 (2023) - 2022
- [j45]Xin Li, Shachar Lovett, Jiapeng Zhang:
Sunflowers and Robust Sunflowers from Randomness Extractors. Theory Comput. 18: 1-18 (2022) - [j44]Kaave Hosseini, Hamed Hatami, Shachar Lovett:
Sign-Rank vs. Discrepancy. Theory Comput. 18: 1-22 (2022) - 2021
- [j43]Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Decision List Compression by Mild Random Restrictions. J. ACM 68(6): 45:1-45:17 (2021) - [j42]Shachar Lovett:
Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture. SIAM J. Comput. 50(4): 1248-1262 (2021) - [j41]Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan:
Guest Column: Models of computation between decision trees and communication. SIGACT News 52(2): 46-70 (2021) - 2020
- [j40]Shachar Lovett, Sankeerth Rao, Alexander Vardy:
Probabilistic existence of large sets of designs. J. Comb. Theory A 176: 105286 (2020) - 2019
- [j39]Hamed Hatami, Pooya Hatami, Shachar Lovett:
Higher-order Fourier Analysis and Applications. Found. Trends Theor. Comput. Sci. 13(4): 247-448 (2019) - [j38]Daniel M. Kane, Shachar Lovett, Shay Moran:
Near-optimal Linear Decision Trees for k-SUM and Related Problems. J. ACM 66(3): 16:1-16:18 (2019) - [j37]Esther Ezra, Shachar Lovett:
On the Beck-Fiala conjecture for random set systems. Random Struct. Algorithms 54(4): 665-675 (2019) - [j36]Daniel Kane, Shachar Lovett, Sankeerth Rao:
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. SIAM J. Comput. 48(4): 1425-1435 (2019) - [j35]Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett:
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. Theory Comput. 15: 1-27 (2019) - [j34]Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett:
Pseudorandom Generators from Polarizing Random Walks. Theory Comput. 15: 1-26 (2019) - [j33]Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov:
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. Theory Comput. 15: 1-58 (2019) - 2018
- [j32]Benny Applebaum, Shachar Lovett:
Algebraic Attacks against Random Local Functions and Their Countermeasures. SIAM J. Comput. 47(1): 52-79 (2018) - [j31]Hamed Hatami, Kaave Hosseini, Shachar Lovett:
Structure of Protocols for XOR Functions. SIAM J. Comput. 47(1): 208-217 (2018) - [j30]Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett:
Non-Malleable Codes from Additive Combinatorics. SIAM J. Comput. 47(2): 524-546 (2018) - [j29]Abhishek Bhowmick, Shachar Lovett:
The List Decoding Radius for Reed-Muller Codes Over Small Fields. IEEE Trans. Inf. Theory 64(6): 4382-4391 (2018) - [j28]Shachar Lovett, Ryan O'Donnell:
Special Issue: CCC 2017: Guest Editor's Foreword. Theory Comput. 14(1): 1-2 (2018) - 2017
- [j27]Kaave Hosseini, Shachar Lovett:
On the structure of the spectrum of small sets. J. Comb. Theory A 148: 1-14 (2017) - [j26]Shachar Lovett:
Additive Combinatorics and its Applications in Theoretical Computer Science. Theory Comput. 8: 1-55 (2017) - 2016
- [j25]Shachar Lovett:
Communication is Bounded by Root of Rank. J. ACM 63(1): 1:1-1:9 (2016) - [j24]Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. SIAM J. Comput. 45(5): 1835-1869 (2016) - 2015
- [j23]Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A tail bound for read-k families of functions. Random Struct. Algorithms 47(1): 99-108 (2015) - [j22]Shachar Lovett, Cristopher Moore, Alexander Russell:
Group representations that resist random sampling. Random Struct. Algorithms 47(3): 605-614 (2015) - [j21]Shachar Lovett, Raghu Meka:
Constructive Discrepancy Minimization by Walking on the Edges. SIAM J. Comput. 44(5): 1573-1582 (2015) - [j20]Shachar Lovett:
An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem. Theory Comput. 6: 1-14 (2015) - 2014
- [j19]Zeev Dvir, János Kollár, Shachar Lovett:
Variety Evasive Sets. Comput. Complex. 23(4): 509-529 (2014) - [j18]Shachar Lovett:
Recent Advances on the Log-Rank Conjecture in Communication Complexity. Bull. EATCS 112 (2014) - [j17]Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi:
An Additive Combinatorics Approach Relating Rank to Communication Complexity. J. ACM 61(4): 22:1-22:18 (2014) - [j16]Chaim Even-Zohar, Shachar Lovett:
The Freiman-Ruzsa theorem over finite fields. J. Comb. Theory A 125: 333-341 (2014) - [j15]Arman Fazeli, Shachar Lovett, Alexander Vardy:
Nontrivial t-designs over finite fields exist for all t. J. Comb. Theory A 127: 149-160 (2014) - [j14]Hamed Hatami, Shachar Lovett:
Correlation Testing for Affine Invariant Properties on 픽pn in the High Error Regime. SIAM J. Comput. 43(4): 1417-1455 (2014) - [j13]Abhishek Bhowmick, Zeev Dvir, Shachar Lovett:
New Bounds for Matching Vector Families. SIAM J. Comput. 43(5): 1654-1683 (2014) - 2013
- [j12]Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka:
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields. Comput. Complex. 22(4): 679-725 (2013) - [j11]Shachar Lovett, Ely Porat:
A Space Lower Bound for Dynamic Approximate Membership Data Structures. SIAM J. Comput. 42(6): 2182-2196 (2013) - [j10]Noga Alon, Shachar Lovett:
Almost k-Wise vs. k-Wise Independent Permutations, and Uniformity for General Group Actions. Theory Comput. 9: 559-577 (2013) - 2012
- [j9]Ido Ben-Eliezer, Rani Hod, Shachar Lovett:
Random low-degree polynomials are hard to approximate. Comput. Complex. 21(1): 63-81 (2012) - [j8]Shachar Lovett, Emanuele Viola:
Bounded-Depth Circuits Cannot Sample Good Codes. Comput. Complex. 21(2): 245-266 (2012) - [j7]Shachar Lovett:
Equivalence of polynomial conjectures in additive combinatorics. Comb. 32(5): 607-618 (2012) - [j6]Tali Kaufman, Shachar Lovett, Ely Porat:
Weight Distribution and List-Decoding Size of Reed-Muller Codes. IEEE Trans. Inf. Theory 58(5): 2689-2696 (2012) - 2011
- [j5]Shachar Lovett, Roy Meshulam, Alex Samorodnitsky:
Inverse Conjecture for the Gowers Norm is False. Theory Comput. 7(1): 131-145 (2011) - [j4]Shachar Lovett:
Computing Polynomials with Few Multiplications. Theory Comput. 7(1): 185-188 (2011) - 2010
- [j3]Parikshit Gopalan, Amir Shpilka, Shachar Lovett:
The Complexity of Boolean Functions in Different Characteristics. Comput. Complex. 19(2): 235-263 (2010) - [j2]Shachar Lovett:
Holes in generalized Reed-Muller codes. IEEE Trans. Inf. Theory 56(6): 2583-2586 (2010) - 2009
- [j1]Shachar Lovett:
Unconditional Pseudorandom Generators for Low Degree Polynomials. Theory Comput. 5(1): 69-82 (2009)
Conference and Workshop Papers
- 2024
- [c87]Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni:
Refuting Approaches to the Log-Rank Conjecture for XOR Functions. ICALP 2024: 82:1-82:11 - [c86]Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka:
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. STOC 2024: 935-943 - [c85]Zander Kelley, Shachar Lovett, Raghu Meka:
Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication. STOC 2024: 1299-1310 - 2023
- [c84]Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellért Weisz, Csaba Szepesvári:
Exponential Hardness of Reinforcement Learning with Linear Function Approximation. COLT 2023: 1588-1617 - [c83]Shachar Lovett, Jiapeng Zhang:
Streaming Lower Bounds and Asymmetric Set-Disjointness. FOCS 2023: 871-882 - [c82]Shachar Lovett, Jiapeng Zhang:
Fractional Certificates for Bounded Functions. ITCS 2023: 84:1-84:13 - [c81]Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett:
Sampling Equilibria: Fast No-Regret Learning in Structured Games. SODA 2023: 3817-3855 - 2022
- [c80]Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang:
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. APPROX/RANDOM 2022: 16:1-16:24 - [c79]Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan:
Computational-Statistical Gap in Reinforcement Learning. COLT 2022: 1282-1302 - [c78]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Realizable Learning is All You Need. COLT 2022: 3015-3069 - [c77]Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang:
Lifting with Sunflowers. ITCS 2022: 104:1-104:24 - [c76]Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett:
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games. SODA 2022: 1069-1128 - [c75]Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett:
Hypercontractivity on high dimensional expanders. STOC 2022: 185-194 - 2021
- [c74]Sankeerth Rao Karingula, Shachar Lovett:
Singularity of Random Integer Matrices with Large Entries. APPROX-RANDOM 2021: 33:1-33:16 - [c73]Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty:
Fractional Pseudorandom Generators from Any Fourier Level. CCC 2021: 10:1-10:24 - [c72]Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz:
Bounded Memory Active Learning through Enriched Queries. COLT 2021: 2358-2387 - [c71]Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, Ruosong Wang:
Bilinear Classes: A Structural Framework for Provable Generalization in RL. ICML 2021: 2826-2836 - [c70]Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan:
Log-rank and lifting for AND-functions. STOC 2021: 197-208 - 2020
- [c69]Hamed Hatami, Kaave Hosseini, Shachar Lovett:
Sign Rank vs Discrepancy. CCC 2020: 18:1-18:14 - [c68]Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan:
Noise-tolerant, Reliable Active Classification with Comparison Queries. COLT 2020: 1957-2006 - [c67]Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan:
Point Location and Active Learning: Learning Halfspaces Almost Optimally. FOCS 2020: 1034-1044 - [c66]Alon Gonen, Shachar Lovett, Michal Moshkovitz:
Towards a Combinatorial Characterization of Bounded-Memory Learning. NeurIPS 2020 - [c65]Max Hopkins, Daniel Kane, Shachar Lovett:
The Power of Comparisons for Actively Learning Linear Classifiers. NeurIPS 2020 - [c64]Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman:
XOR lemmas for resilient functions against polynomials. STOC 2020: 234-246 - [c63]Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Decision list compression by mild random restrictions. STOC 2020: 247-254 - [c62]Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Improved bounds for the sunflower lemma. STOC 2020: 624-630 - 2019
- [c61]Shachar Lovett, Noam Solomon, Jiapeng Zhang:
From DNF Compression to Sunflower Theorems via Regularity. CCC 2019: 5:1-5:14 - [c60]Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev:
Optimality of Linear Sketching Under Modular Updates. CCC 2019: 13:1-13:17 - [c59]Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals:
Equality Alone Does not Simulate Randomness. CCC 2019: 14:1-14:11 - [c58]Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao:
Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. ITCS 2019: 13:1-13:16 - [c57]Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal:
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. ITCS 2019: 22:1-22:15 - [c56]Shachar Lovett, Jiapeng Zhang:
DNF sparsification beyond sunflowers. STOC 2019: 454-460 - 2018
- [c55]Xin Li, Shachar Lovett, Jiapeng Zhang:
Sunflowers and Quasi-Sunflowers from Randomness Extractors. APPROX-RANDOM 2018: 51:1-51:13 - [c54]Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett:
Pseudorandom Generators from Polarizing Random Walks. CCC 2018: 1:1-1:21 - [c53]Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin:
Hardness Amplification for Non-Commutative Arithmetic Circuits. CCC 2018: 12:1-12:16 - [c52]Shachar Lovett:
MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture. FOCS 2018: 194-199 - [c51]Daniel M. Kane, Shachar Lovett, Shay Moran:
Generalized Comparison Trees for Point-Location Problems. ICALP 2018: 82:1-82:13 - [c50]Shachar Lovett, Sankeerth Rao, Alexander Vardy:
Probabilistic Existence of Large Sets of Designs. SODA 2018: 1545-1556 - [c49]Shachar Lovett, Avishay Tal, Jiapeng Zhang:
The Robust Sensitivity of Boolean Functions. SODA 2018: 1822-1833 - [c48]Daniel M. Kane, Shachar Lovett, Shay Moran:
Near-optimal linear decision trees for k-SUM and related problems. STOC 2018: 554-563 - [c47]Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett:
The gram-schmidt walk: a cure for the Banaszczyk blues. STOC 2018: 587-597 - 2017
- [c46]Shachar Lovett, Jiapeng Zhang:
Noisy Population Recovery from Unknown Noise. COLT 2017: 1417-1431 - [c45]Daniel Kane, Shachar Lovett, Sankeerth Rao:
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. FOCS 2017: 252-259 - [c44]Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang:
Active Classification with Comparison Queries. FOCS 2017: 355-366 - [c43]Shachar Lovett, Jiapeng Zhang:
On the Impossibility of Entropy Reversal, and Its Application to Zero-Knowledge Proofs. TCC (1) 2017: 31-55 - 2016
- [c42]Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov:
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. APPROX-RANDOM 2016: 28:1-28:12 - [c41]Esther Ezra, Shachar Lovett:
On the Beck-Fiala Conjecture for Random Set Systems. APPROX-RANDOM 2016: 29:1-29:10 - [c40]Hamed Hatami, Kaave Hosseini, Shachar Lovett:
Structure of Protocols for XOR Functions. FOCS 2016: 282-288 - [c39]Divesh Aggarwal, Kaave Hosseini, Shachar Lovett:
Affine-malleable extractors, spectrum doubling, and application to privacy amplification. ISIT 2016: 2913-2917 - [c38]Benny Applebaum, Shachar Lovett:
Algebraic attacks against random local functions and their countermeasures. STOC 2016: 1087-1100 - 2015
- [c37]Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, Hehui Wu:
Large Supports are Required for Well-Supported Nash Equilibria. APPROX-RANDOM 2015: 78-84 - [c36]Abhishek Bhowmick, Shachar Lovett:
Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds. CCC 2015: 72-87 - [c35]Shachar Lovett, Jiapeng Zhang:
Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions. STOC 2015: 137-142 - [c34]Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. STOC 2015: 257-266 - [c33]Abhishek Bhowmick, Shachar Lovett:
The List Decoding Radius of Reed-Muller Codes over Small Fields. STOC 2015: 277-285 - 2014
- [c32]Yoram Bachrach, Omer Lev, Shachar Lovett, Jeffrey S. Rosenschein, Morteza Zadimoghaddam:
Cooperative weakest link games. AAMAS 2014: 589-596 - [c31]Dmitry Gavinsky, Shachar Lovett:
En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations. ICALP (1) 2014: 514-524 - [c30]Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett:
Non-malleable codes from additive combinatorics. STOC 2014: 774-783 - [c29]Shachar Lovett:
Communication is bounded by root of rank. STOC 2014: 842-846 - 2013
- [c28]Hamed Hatami, Shachar Lovett:
Estimating the Distance from Testable Affine-Invariant Properties. FOCS 2013: 237-242 - [c27]Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett:
Testing Low Complexity Affine-Invariant Properties. SODA 2013: 1337-1355 - [c26]Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett:
Every locally characterized affine-invariant property is testable. STOC 2013: 429-436 - [c25]Abhishek Bhowmick, Zeev Dvir, Shachar Lovett:
New bounds for matching vector families. STOC 2013: 823-832 - 2012
- [c24]Noga Alon, Shachar Lovett:
Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions. APPROX-RANDOM 2012: 350-361 - [c23]Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan:
Pseudorandom Generators for Read-Once ACC^0. CCC 2012: 287-297 - [c22]Zohar Shay Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, Omri Weinstein:
Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem. COLT 2012: 2.1-2.17 - [c21]Shachar Lovett, Raghu Meka:
Constructive Discrepancy Minimization by Walking on the Edges. FOCS 2012: 61-67 - [c20]Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits. FOCS 2012: 101-110 - [c19]Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi:
An Additive Combinatorics Approach Relating Rank to Communication Complexity. FOCS 2012: 177-186 - [c18]Zeev Dvir, Shachar Lovett:
Subspace evasive sets. STOC 2012: 351-358 - [c17]Greg Kuperberg, Shachar Lovett, Ron Peled:
Probabilistic existence of rigid combinatorial structures. STOC 2012: 1091-1106 - 2011
- [c16]Shachar Lovett, Srikanth Srinivasan:
Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 - o(1) Symmetric Gates. APPROX-RANDOM 2011: 640-651 - [c15]Shachar Lovett, Emanuele Viola:
Bounded-Depth Circuits Cannot Sample Good Codes. CCC 2011: 243-251 - [c14]Arkadev Chattopadhyay, Shachar Lovett:
Linear Systems over Finite Abelian Groups. CCC 2011: 300-308 - [c13]Tali Kaufman, Shachar Lovett:
New Extension of the Weil Bound for Character Sums with Applications to Coding. FOCS 2011: 788-796 - [c12]Hamed Hatami, Shachar Lovett:
Correlation testing for affine invariant properties on Fpn in the high error regime. STOC 2011: 187-194 - 2010
- [c11]Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka:
Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields. FOCS 2010: 695-704 - [c10]Shachar Lovett, Ely Porat:
A Lower Bound for Dynamic Approximate Membership Data Structures. FOCS 2010: 797-804 - [c9]Tali Kaufman, Shachar Lovett, Ely Porat:
Weight Distribution and List-Decoding Size of Reed-Muller Codes. ICS 2010: 422-433 - 2009
- [c8]Ido Ben-Eliezer, Rani Hod, Shachar Lovett:
Random Low Degree Polynomials are Hard to Approximate. APPROX-RANDOM 2009: 366-377 - [c7]Shachar Lovett, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Bit Generators That Fool Modular Sums. APPROX-RANDOM 2009: 615-630 - [c6]Parikshit Gopalan, Shachar Lovett, Amir Shpilka:
On the Complexity of Boolean Functions in Different Characteristics. CCC 2009: 173-183 - [c5]Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett:
On cryptography with auxiliary input. STOC 2009: 621-630 - 2008
- [c4]Tali Kaufman, Shachar Lovett:
Worst Case to Average Case Reductions for Polynomials. FOCS 2008: 166-175 - [c3]Shachar Lovett:
Lower bounds for adaptive linearity tests. STACS 2008: 515-526 - [c2]Shachar Lovett, Roy Meshulam, Alex Samorodnitsky:
Inverse conjecture for the gowers norm is false. STOC 2008: 547-556 - [c1]Shachar Lovett:
Unconditional pseudorandom generators for low degree polynomials. STOC 2008: 557-562
Editorship
- 2022
- [e1]Shachar Lovett:
37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA. LIPIcs 234, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022, ISBN 978-3-95977-241-9 [contents]
Informal and Other Publications
- 2023
- [i145]Shachar Lovett, Jiapeng Zhang:
Streaming Lower Bounds and Asymmetric Set-Disjointness. CoRR abs/2301.05658 (2023) - [i144]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Do PAC-Learners Learn the Marginal Distribution? CoRR abs/2302.06285 (2023) - [i143]Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan, Csaba Szepesvári, Gellért Weisz:
Exponential Hardness of Reinforcement Learning with Linear Function Approximation. CoRR abs/2302.12940 (2023) - [i142]Zander Kelley, Shachar Lovett, Raghu Meka:
Explicit separations between randomized and deterministic Number-on-Forehead communication. CoRR abs/2308.12451 (2023) - [i141]Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka:
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. CoRR abs/2311.09095 (2023) - [i140]Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni:
Refuting approaches to the log-rank conjecture for XOR functions. CoRR abs/2312.09400 (2023) - [i139]Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka:
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. Electron. Colloquium Comput. Complex. TR23 (2023) - [i138]Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni:
Refuting approaches to the log-rank conjecture for XOR functions. Electron. Colloquium Comput. Complex. TR23 (2023) - [i137]Zander Kelley, Shachar Lovett, Raghu Meka:
Explicit separations between randomized and deterministic Number-on-Forehead communication. Electron. Colloquium Comput. Complex. TR23 (2023) - [i136]Shachar Lovett, Jiapeng Zhang:
Streaming Lower Bounds and Asymmetric Set-Disjointness. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [i135]Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan:
Computational-Statistical Gaps in Reinforcement Learning. CoRR abs/2202.05444 (2022) - [i134]Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang:
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. CoRR abs/2205.00644 (2022) - [i133]Shachar Lovett, Jiapeng Zhang:
Fractional certificates for bounded functions. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [i132]Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz:
Bounded Memory Active Learning through Enriched Queries. CoRR abs/2102.05047 (2021) - [i131]Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, Ruosong Wang:
Bilinear Classes: A Structural Framework for Provable Generalization in RL. CoRR abs/2103.10897 (2021) - [i130]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Realizable Learning is All You Need. CoRR abs/2111.04746 (2021) - [i129]Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett:
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments. CoRR abs/2111.09444 (2021) - [i128]Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett:
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [i127]Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan:
Noise-tolerant, Reliable Active Classification with Comparison Queries. CoRR abs/2001.05497 (2020) - [i126]Alon Gonen, Shachar Lovett, Michal Moshkovitz:
Towards a combinatorial characterization of bounded memory learning. CoRR abs/2002.03123 (2020) - [i125]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Point Location and Active Learning: Learning Halfspaces Almost Optimally. CoRR abs/2004.11380 (2020) - [i124]Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty:
Fractional Pseudorandom Generators from Any Fourier Level. CoRR abs/2008.01316 (2020) - [i123]Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan:
Log-rank and lifting for AND-functions. CoRR abs/2010.08994 (2020) - [i122]Sankeerth Rao Karingula, Shachar Lovett:
Codes over integers, and the singularity of random matrices with large entries. CoRR abs/2010.12081 (2020) - [i121]Max Hopkins, Tali Kaufman, Shachar Lovett:
High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games. CoRR abs/2011.04658 (2020) - [i120]Max Hopkins, Tali Kaufman, Shachar Lovett:
High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games. Electron. Colloquium Comput. Complex. TR20 (2020) - [i119]Sankeerth Rao Karingula, Shachar Lovett:
Codes over integers, and the singularity of random matrices with large entries. Electron. Colloquium Comput. Complex. TR20 (2020) - [i118]Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan:
Log-rank and lifting for AND-functions. Electron. Colloquium Comput. Complex. TR20 (2020) - [i117]Shachar Lovett, Raghu Meka, Jiapeng Zhang:
Improved lifting theorems via robust sunflowers. Electron. Colloquium Comput. Complex. TR20 (2020) - 2019
- [i116]Shachar Lovett, Noam Solomon, Jiapeng Zhang:
From DNF compression to sunflower theorems via regularity. CoRR abs/1903.00580 (2019) - [i115]Max Hopkins, Daniel M. Kane, Shachar Lovett:
The Power of Comparisons for Actively Learning Linear Classifiers. CoRR abs/1907.03816 (2019) - [i114]Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Improved bounds for the sunflower lemma. CoRR abs/1908.08483 (2019) - [i113]Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Decision list compression by mild random restrictions. CoRR abs/1909.10658 (2019) - [i112]Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Improved bounds for the sunflower lemma. Electron. Colloquium Comput. Complex. TR19 (2019) - [i111]Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman:
XOR Lemmas for Resilient Functions Against Polynomials. Electron. Colloquium Comput. Complex. TR19 (2019) - [i110]Hamed Hatami, Kaave Hosseini, Shachar Lovett:
Sign rank vs Discrepancy. Electron. Colloquium Comput. Complex. TR19 (2019) - [i109]Shachar Lovett, Noam Solomon, Jiapeng Zhang:
From DNF compression to sunflower theorems via regularity. Electron. Colloquium Comput. Complex. TR19 (2019) - [i108]Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Decision list compression by mild random restrictions. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i107]Shachar Lovett:
MDS matrices over small fields: A proof of the GM-MDS conjecture. CoRR abs/1803.02523 (2018) - [i106]Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao:
Torus polynomials: an algebraic approach to ACC lower bounds. CoRR abs/1804.08176 (2018) - [i105]Daniel M. Kane, Shachar Lovett, Shay Moran:
Generalized comparison trees for point-location problems. CoRR abs/1804.08237 (2018) - [i104]Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev:
Optimality of Linear Sketching under Modular Updates. CoRR abs/1809.09063 (2018) - [i103]Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao:
Torus polynomials: an algebraic approach to ACC lower bounds. Electron. Colloquium Comput. Complex. TR18 (2018) - [i102]Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin:
Hardness Amplification for Non-Commutative Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR18 (2018) - [i101]Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett:
Pseudorandom Generators from Polarizing Random Walks. Electron. Colloquium Comput. Complex. TR18 (2018) - [i100]Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal:
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. Electron. Colloquium Comput. Complex. TR18 (2018) - [i99]Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals:
Equality Alone Does Not Simulate Randomness. Electron. Colloquium Comput. Complex. TR18 (2018) - [i98]Kaave Hosseini, Shachar Lovett:
A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds. Electron. Colloquium Comput. Complex. TR18 (2018) - [i97]Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev:
Optimality of Linear Sketching under Modular Updates. Electron. Colloquium Comput. Complex. TR18 (2018) - [i96]Daniel M. Kane, Shachar Lovett, Shay Moran:
Generalized comparison trees for point-location problems. Electron. Colloquium Comput. Complex. TR18 (2018) - [i95]Xin Li, Shachar Lovett, Jiapeng Zhang:
Sunflowers and Quasi-sunflowers from Randomness Extractors. Electron. Colloquium Comput. Complex. TR18 (2018) - [i94]Shachar Lovett:
A proof of the GM-MDS conjecture. Electron. Colloquium Comput. Complex. TR18 (2018) - [i93]Shachar Lovett, Jiapeng Zhang:
DNF sparsification beyond sunflowers. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [i92]Daniel M. Kane, Shachar Lovett, Sankeerth Rao:
Labeling the complete bipartite graph with no zero cycles. CoRR abs/1702.05773 (2017) - [i91]Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang:
Active classification with comparison queries. CoRR abs/1704.03564 (2017) - [i90]Daniel M. Kane, Shachar Lovett, Shay Moran:
Near-optimal linear decision trees for k-SUM and related problems. CoRR abs/1705.01720 (2017) - [i89]Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett:
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. CoRR abs/1708.01079 (2017) - [i88]Daniel M. Kane, Shachar Lovett, Shay Moran:
Near-optimal linear decision trees for k-SUM and related problems. Electron. Colloquium Comput. Complex. TR17 (2017) - [i87]Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang:
Active classification with comparison queries. Electron. Colloquium Comput. Complex. TR17 (2017) - [i86]Daniel M. Kane, Shachar Lovett, Sankeerth Rao:
Labeling the complete bipartite graph with no zero cycles. Electron. Colloquium Comput. Complex. TR17 (2017) - [i85]Shachar Lovett, Sankeerth Rao, Alexander Vardy:
Probabilistic Existence of Large Sets of Designs. Electron. Colloquium Comput. Complex. TR17 (2017) - [i84]Shachar Lovett, Jiapeng Zhang:
On the impossibility of entropy reversal, and its application to zero-knowledge proofs. IACR Cryptol. ePrint Arch. 2017: 922 (2017) - 2016
- [i83]Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov:
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. CoRR abs/1612.04304 (2016) - [i82]Kaave Hosseini, Shachar Lovett:
Structure of protocols for XOR functions. Electron. Colloquium Comput. Complex. TR16 (2016) - [i81]Shachar Lovett:
The Fourier structure of low degree polynomials. Electron. Colloquium Comput. Complex. TR16 (2016) - [i80]Shachar Lovett, Jiapeng Zhang:
Noisy Population Recovery from Unknown Noise. Electron. Colloquium Comput. Complex. TR16 (2016) - [i79]Shachar Lovett, Jiapeng Zhang:
On the impossibility of entropy reversal, and its application to zero-knowledge proofs. Electron. Colloquium Comput. Complex. TR16 (2016) - [i78]Shachar Lovett, Jiapeng Zhang:
Robust sensitivity. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i77]Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, Hehui Wu:
Large Supports are required for Well-Supported Nash Equilibria. CoRR abs/1504.03602 (2015) - [i76]Abhishek Bhowmick, Shachar Lovett:
Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. CoRR abs/1506.02047 (2015) - [i75]Abhishek Bhowmick, Shachar Lovett:
Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. Electron. Colloquium Comput. Complex. TR15 (2015) - [i74]Divesh Aggarwal, Kaave Hosseini, Shachar Lovett:
Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification. Electron. Colloquium Comput. Complex. TR15 (2015) - [i73]Benny Applebaum, Shachar Lovett:
Algebraic Attacks against Random Local Functions and Their Countermeasures. Electron. Colloquium Comput. Complex. TR15 (2015) - [i72]Esther Ezra, Shachar Lovett:
On the Beck-Fiala Conjecture for Random Set Systems. Electron. Colloquium Comput. Complex. TR15 (2015) - [i71]Divesh Aggarwal, Kaave Hosseini, Shachar Lovett:
Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification. IACR Cryptol. ePrint Arch. 2015: 1094 (2015) - 2014
- [i70]Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider:
0-1 Integer Linear Programming with a Linear Number of Constraints. CoRR abs/1401.5512 (2014) - [i69]Shachar Lovett:
Recent advances on the log-rank conjecture in communication complexity. CoRR abs/1403.8106 (2014) - [i68]Abhishek Bhowmick, Shachar Lovett:
List decoding Reed-Muller codes over small fields. CoRR abs/1407.3433 (2014) - [i67]Abhishek Bhowmick, Shachar Lovett:
Nonclassical polynomials as a barrier to polynomial lower bounds. CoRR abs/1412.4719 (2014) - [i66]Abhishek Bhowmick, Shachar Lovett:
Nonclassical polynomials as a barrier to polynomial lower bounds. Electron. Colloquium Comput. Complex. TR14 (2014) - [i65]Abhishek Bhowmick, Shachar Lovett:
List decoding Reed-Muller codes over small fields. Electron. Colloquium Comput. Complex. TR14 (2014) - [i64]Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. Electron. Colloquium Comput. Complex. TR14 (2014) - [i63]Hamed Hatami, Pooya Hatami, Shachar Lovett:
General systems of linear forms: equidistribution and true complexity. Electron. Colloquium Comput. Complex. TR14 (2014) - [i62]Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider:
0-1 Integer Linear Programming with a Linear Number of Constraints. Electron. Colloquium Comput. Complex. TR14 (2014) - [i61]Shachar Lovett:
Recent advances on the log-rank conjecture in communication complexity. Electron. Colloquium Comput. Complex. TR14 (2014) - [i60]Shachar Lovett:
Linear codes cannot approximate the network capacity within any constant factor. Electron. Colloquium Comput. Complex. TR14 (2014) - [i59]Shachar Lovett, Cristopher Moore, Alexander Russell:
Group representations that resist random sampling. Electron. Colloquium Comput. Complex. TR14 (2014) - [i58]Shachar Lovett, Jiapeng Zhang:
Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i57]Greg Kuperberg, Shachar Lovett, Ron Peled:
Probabilistic existence of regular combinatorial structures. CoRR abs/1302.4295 (2013) - [i56]Hamed Hatami, Shachar Lovett:
Estimating the distance from testable affine-invariant properties. CoRR abs/1306.0649 (2013) - [i55]Shachar Lovett:
Communication is bounded by root of rank. CoRR abs/1306.1877 (2013) - [i54]Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett:
Non-malleable Codes from Additive Combinatorics. Electron. Colloquium Comput. Complex. TR13 (2013) - [i53]Arman Fazeli, Shachar Lovett, Alexander Vardy:
Nontrivial t-designs over finite fields exist for all t. Electron. Colloquium Comput. Complex. TR13 (2013) - [i52]Dmitry Gavinsky, Shachar Lovett:
En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations. Electron. Colloquium Comput. Complex. TR13 (2013) - [i51]Hamed Hatami, Shachar Lovett:
Estimating the distance from testable affine-invariant properties. Electron. Colloquium Comput. Complex. TR13 (2013) - [i50]Shachar Lovett:
Communication is bounded by root of rank. Electron. Colloquium Comput. Complex. TR13 (2013) - [i49]Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett:
Non-malleable Codes from Additive Combinatorics. IACR Cryptol. ePrint Arch. 2013: 201 (2013) - 2012
- [i48]Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett:
Testing Low Complexity Affine-Invariant Properties. CoRR abs/1201.0330 (2012) - [i47]Zeev Dvir, János Kollár, Shachar Lovett:
Variety Evasive Sets. CoRR abs/1203.4532 (2012) - [i46]Shachar Lovett, Raghu Meka:
Constructive Discrepancy Minimization by Walking on The Edges. CoRR abs/1203.5747 (2012) - [i45]Abhishek Bhowmick, Zeev Dvir, Shachar Lovett:
New Lower Bounds for Matching Vector Codes. CoRR abs/1204.1367 (2012) - [i44]Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. CoRR abs/1205.1478 (2012) - [i43]Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett:
Every locally characterized affine-invariant property is testable. CoRR abs/1212.3849 (2012) - [i42]Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. Electron. Colloquium Comput. Complex. TR12 (2012) - [i41]Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett:
Every locally characterized affine-invariant property is testable. Electron. Colloquium Comput. Complex. TR12 (2012) - [i40]Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett:
Testing Low Complexity Affine-Invariant Properties. Electron. Colloquium Comput. Complex. TR12 (2012) - [i39]Abhishek Bhowmick, Zeev Dvir, Shachar Lovett:
New Lower Bounds for Matching Vector Codes. Electron. Colloquium Comput. Complex. TR12 (2012) - [i38]Chaim Even-Zohar, Shachar Lovett:
The Freiman-Ruzsa Theorem in Finite Fields. Electron. Colloquium Comput. Complex. TR12 (2012) - [i37]Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. Electron. Colloquium Comput. Complex. TR12 (2012) - [i36]Shachar Lovett:
An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i35]Hamed Hatami, Shachar Lovett:
Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime. CoRR abs/1104.3335 (2011) - [i34]Edo Liberty, Shachar Lovett, Omri Weinstein:
On the Furthest Hyperplane Problem and Maximal Margin Clustering. CoRR abs/1107.1358 (2011) - [i33]Zeev Dvir, Shachar Lovett:
Subspace Evasive Sets. CoRR abs/1110.5696 (2011) - [i32]Greg Kuperberg, Shachar Lovett, Ron Peled:
Probabilistic existence of rigid combinatorial structures. CoRR abs/1111.0492 (2011) - [i31]Eli Ben-Sasson, Shachar Lovett, Noga Zewi:
An additive combinatorics approach to the log-rank conjecture in communication complexity. CoRR abs/1111.5884 (2011) - [i30]Noga Alon, Shachar Lovett:
Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions. Electron. Colloquium Comput. Complex. TR11 (2011) - [i29]Eli Ben-Sasson, Shachar Lovett, Noga Zewi:
An additive combinatorics approach to the log-rank conjecture in communication complexity. Electron. Colloquium Comput. Complex. TR11 (2011) - [i28]Arkadev Chattopadhyay, Shachar Lovett:
Linear systems over abelian groups. Electron. Colloquium Comput. Complex. TR11 (2011) - [i27]Zeev Dvir, Shachar Lovett:
Subspace Evasive Sets. Electron. Colloquium Comput. Complex. TR11 (2011) - [i26]Hamed Hatami, Shachar Lovett:
Correlation testing for affine invariant properties on Fpn in the high error regime. Electron. Colloquium Comput. Complex. TR11 (2011) - [i25]Greg Kuperberg, Shachar Lovett, Ron Peled:
Probabilistic existence of rigid combinatorial structures. Electron. Colloquium Comput. Complex. TR11 (2011) - [i24]Shachar Lovett:
Computing polynomials with few multiplications. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [i23]Hamed Hatami, Shachar Lovett:
Higher-order Fourier analysis of Fpn and the complexity of systems of linear forms. Electron. Colloquium Comput. Complex. TR10 (2010) - [i22]Tali Kaufman, Shachar Lovett:
Testing of exponentially large codes, by a new extension to Weil bound for character sums. Electron. Colloquium Comput. Complex. TR10 (2010) - [i21]Shachar Lovett:
Equivalence of polynomial conjectures in additive combinatorics. Electron. Colloquium Comput. Complex. TR10 (2010) - [i20]Shachar Lovett:
An elementary proof of anti-concentration of polynomials in Gaussian variables. Electron. Colloquium Comput. Complex. TR10 (2010) - [i19]Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka:
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields. Electron. Colloquium Comput. Complex. TR10 (2010) - [i18]Shachar Lovett, Ely Porat:
A lower bound for dynamic approximate membership data structures. Electron. Colloquium Comput. Complex. TR10 (2010) - [i17]Shachar Lovett, Emanuele Viola:
Bounded-depth circuits cannot sample good codes. Electron. Colloquium Comput. Complex. TR10 (2010) - 2009
- [i16]Shachar Lovett:
The density of weights of Generalized Reed--Muller codes. CoRR abs/0904.0811 (2009) - [i15]Ido Ben-Eliezer, Shachar Lovett, Ariel Yadin:
Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness. CoRR abs/0911.3473 (2009) - [i14]Parikshit Gopalan, Shachar Lovett, Amir Shpilka:
On the Complexity of Boolean Functions in Different Characteristics. Electron. Colloquium Comput. Complex. TR09 (2009) - [i13]Shachar Lovett:
The density of weights of Generalized Reed-Muller codes. Electron. Colloquium Comput. Complex. TR09 (2009) - [i12]Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin:
Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness. Electron. Colloquium Comput. Complex. TR09 (2009) - [i11]Shachar Lovett, Yoav Tzur:
Explicit lower bound for fooling polynomials by the sum of small-bias generators. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [i10]Shachar Lovett:
Lower bounds for adaptive linearity tests. CoRR abs/0802.2857 (2008) - [i9]Tali Kaufman, Shachar Lovett:
The List-Decoding Size of Reed-Muller Codes. CoRR abs/0811.2356 (2008) - [i8]Ido Ben-Eliezer, Rani Hod, Shachar Lovett:
Random low degree polynomials are hard to approximate. Electron. Colloquium Comput. Complex. TR08 (2008) - [i7]Shachar Lovett, Tali Kaufman:
Worst case to Average case reductions for polynomials. Electron. Colloquium Comput. Complex. TR08 (2008) - [i6]Shachar Lovett, Tali Kaufman:
The List-Decoding Size of Reed-Muller Codes. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [i5]Shachar Lovett, Sasha Sodin:
Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits. CoRR abs/math/0701102 (2007) - [i4]Shachar Lovett:
Unconditional pseudorandom generators for low degree polynomials. Electron. Colloquium Comput. Complex. TR07 (2007) - [i3]Shachar Lovett:
Tight lower bounds for adaptive linearity tests. Electron. Colloquium Comput. Complex. TR07 (2007) - [i2]Shachar Lovett, Roy Meshulam, Alex Samorodnitsky:
Inverse Conjecture for the Gowers norm is false. Electron. Colloquium Comput. Complex. TR07 (2007) - [i1]Shachar Lovett, Sasha Sodin:
Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits. Electron. Colloquium Comput. Complex. TR07 (2007)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-09-05 02:09 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
