Shachar Lovett

According to our database, Shachar Lovett authored at least 143 papers between 2007 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Realizable Learning is All You Need.

Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan

TheoretiCS, 2024

2023

Bias vs Structure of Polynomials in Large Fields, and Applications in Information Theory.

Abhishek Bhowmick, Shachar Lovett

IEEE Trans. Inf. Theory, February, 2023

Streaming Lower Bounds and Asymmetric Set-Disjointness.

Shachar Lovett, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2023

Explicit separations between randomized and deterministic Number-on-Forehead communication.

Zander Kelley, Shachar Lovett, Raghu Meka

Electron. Colloquium Comput. Complex., 2023

Refuting approaches to the log-rank conjecture for XOR functions.

Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni

Electron. Colloquium Comput. Complex., 2023

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.

Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka

Electron. Colloquium Comput. Complex., 2023

Do PAC-Learners Learn the Marginal Distribution?

Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan

CoRR, 2023

Sampling Equilibria: Fast No-Regret Learning in Structured Games.

Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Exponential Hardness of Reinforcement Learning with Linear Function Approximation.

Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellért Weisz, Csaba Szepesvári

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Sign-Rank vs. Discrepancy.

Kaave Hosseini, Hamed Hatami, Shachar Lovett

Theory Comput., 2022

Sunflowers and Robust Sunflowers from Randomness Extractors.

Xin Li, Shachar Lovett, Jiapeng Zhang

Theory Comput., 2022

Fractional certificates for bounded functions.

Shachar Lovett, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2022

Computational-Statistical Gaps in Reinforcement Learning.

Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan

CoRR, 2022

Hypercontractivity on high dimensional expanders.

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games.

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Lifting with Sunflowers.

Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Computational-Statistical Gap in Reinforcement Learning.

Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Eigenstripping, Spectral Decay, and Edge-Expansion on Posets.

Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang

Proceedings of the Approximation, 2022

2021

Guest Column: Models of computation between decision trees and communication.

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan

SIGACT News, 2021

Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture.

Shachar Lovett

SIAM J. Comput., 2021

Decision List Compression by Mild Random Restrictions.

Shachar Lovett, Kewen Wu, Jiapeng Zhang

J. ACM, 2021

Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments.

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Electron. Colloquium Comput. Complex., 2021

Bilinear Classes: A Structural Framework for Provable Generalization in RL.

Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, Ruosong Wang

Proceedings of the 38th International Conference on Machine Learning, 2021

Bounded Memory Active Learning through Enriched Queries.

Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz

Proceedings of the Conference on Learning Theory, 2021

Fractional Pseudorandom Generators from Any Fourier Level.

Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty

Proceedings of the 36th Computational Complexity Conference, 2021

Singularity of Random Integer Matrices with Large Entries.

Sankeerth Rao Karingula, Shachar Lovett

Proceedings of the Approximation, 2021

2020

Improved lifting theorems via robust sunflowers.

Shachar Lovett, Raghu Meka, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2020

Log-rank and lifting for AND-functions.

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan

Electron. Colloquium Comput. Complex., 2020

Codes over integers, and the singularity of random matrices with large entries.

Sankeerth Rao Karingula, Shachar Lovett

Electron. Colloquium Comput. Complex., 2020

High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games.

Max Hopkins, Tali Kaufman, Shachar Lovett

Electron. Colloquium Comput. Complex., 2020

The Power of Comparisons for Actively Learning Linear Classifiers.

Max Hopkins, Daniel Kane, Shachar Lovett

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Towards a Combinatorial Characterization of Bounded-Memory Learning.

Alon Gonen, Shachar Lovett, Michal Moshkovitz

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Point Location and Active Learning: Learning Halfspaces Almost Optimally.

Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Noise-tolerant, Reliable Active Classification with Comparison Queries.

Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan

Proceedings of the Conference on Learning Theory, 2020

2019

Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem.

Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov

Theory Comput., 2019

Pseudorandom Generators from Polarizing Random Walks.

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

Theory Comput., 2019

The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues.

Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett

Theory Comput., 2019

The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes.

Daniel Kane, Shachar Lovett, Sankeerth Rao

SIAM J. Comput., 2019

Near-optimal Linear Decision Trees for k-SUM and Related Problems.

Daniel M. Kane, Shachar Lovett, Shay Moran

J. ACM, 2019

Higher-order Fourier Analysis and Applications.

Hamed Hatami, Pooya Hatami, Shachar Lovett

Found. Trends Theor. Comput. Sci., 2019

From DNF compression to sunflower theorems via regularity.

Shachar Lovett, Noam Solomon, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2019

XOR Lemmas for Resilient Functions Against Polynomials.

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman

Electron. Colloquium Comput. Complex., 2019

Improved bounds for the sunflower lemma.

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2019

2018

Special Issue: CCC 2017: Guest Editor's Foreword.

Shachar Lovett, Ryan O'Donnell

Theory Comput., 2018

The List Decoding Radius for Reed-Muller Codes Over Small Fields.

Abhishek Bhowmick, Shachar Lovett

IEEE Trans. Inf. Theory, 2018

Structure of Protocols for XOR Functions.

Hamed Hatami, Kaave Hosseini, Shachar Lovett

SIAM J. Comput., 2018

DNF sparsification beyond sunflowers.

Shachar Lovett, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2018

A proof of the GM-MDS conjecture.

Shachar Lovett

Electron. Colloquium Comput. Complex., 2018

Sunflowers and Quasi-sunflowers from Randomness Extractors.

Xin Li, Shachar Lovett, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2018

Generalized comparison trees for point-location problems.

Daniel M. Kane, Shachar Lovett, Shay Moran

Electron. Colloquium Comput. Complex., 2018

Optimality of Linear Sketching under Modular Updates.

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2018

A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds.

Kaave Hosseini, Shachar Lovett

Electron. Colloquium Comput. Complex., 2018

Equality Alone Does Not Simulate Randomness.

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

Electron. Colloquium Comput. Complex., 2018

Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates.

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

Electron. Colloquium Comput. Complex., 2018

Hardness Amplification for Non-Commutative Arithmetic Circuits.

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

Electron. Colloquium Comput. Complex., 2018

Torus polynomials: an algebraic approach to ACC lower bounds.

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao

Electron. Colloquium Comput. Complex., 2018

The Robust Sensitivity of Boolean Functions.

Shachar Lovett, Avishay Tal, Jiapeng Zhang

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture.

Shachar Lovett

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Additive Combinatorics and its Applications in Theoretical Computer Science.

Shachar Lovett

Theory Comput., 2017

On the structure of the spectrum of small sets.

Kaave Hosseini, Shachar Lovett

J. Comb. Theory, Ser. A, 2017

Probabilistic Existence of Large Sets of Designs.

Shachar Lovett, Sankeerth Rao, Alexander Vardy

Electron. Colloquium Comput. Complex., 2017

Labeling the complete bipartite graph with no zero cycles.

Daniel M. Kane, Shachar Lovett, Sankeerth Rao

Electron. Colloquium Comput. Complex., 2017

Active classification with comparison queries.

Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2017

2016

Communication is Bounded by Root of Rank.

Shachar Lovett

J. ACM, 2016

Robust sensitivity.

Shachar Lovett, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2016

On the impossibility of entropy reversal, and its application to zero-knowledge proofs.

Shachar Lovett, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2016

Noisy Population Recovery from Unknown Noise.

Shachar Lovett, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2016

The Fourier structure of low degree polynomials.

Shachar Lovett

Electron. Colloquium Comput. Complex., 2016

Structure of protocols for XOR functions.

Kaave Hosseini, Shachar Lovett

Electron. Colloquium Comput. Complex., 2016

2015

An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem.

Shachar Lovett

Theory Comput., 2015

Constructive Discrepancy Minimization by Walking on the Edges.

Shachar Lovett, Raghu Meka

SIAM J. Comput., 2015

A tail bound for read-<i>k</i> families of functions.

Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan

Random Struct. Algorithms, 2015

On the Beck-Fiala Conjecture for Random Set Systems.

Esther Ezra, Shachar Lovett

Electron. Colloquium Comput. Complex., 2015

Algebraic Attacks against Random Local Functions and Their Countermeasures.

Benny Applebaum, Shachar Lovett

Electron. Colloquium Comput. Complex., 2015

Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification.

Divesh Aggarwal, Kaave Hosseini, Shachar Lovett

Electron. Colloquium Comput. Complex., 2015

Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory.

Abhishek Bhowmick, Shachar Lovett

Electron. Colloquium Comput. Complex., 2015

Large Supports are Required for Well-Supported Nash Equilibria.

Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, Hehui Wu

Proceedings of the Approximation, 2015

2014

Correlation Testing for Affine Invariant Properties on 픽_pⁿ in the High Error Regime.

Hamed Hatami, Shachar Lovett

SIAM J. Comput., 2014

New Bounds for Matching Vector Families.

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

SIAM J. Comput., 2014

The Freiman-Ruzsa theorem over finite fields.

Chaim Even-Zohar, Shachar Lovett

J. Comb. Theory, Ser. A, 2014

An Additive Combinatorics Approach Relating Rank to Communication Complexity.

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

J. ACM, 2014

Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions.

Shachar Lovett, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2014

Group representations that resist random sampling.

Shachar Lovett, Cristopher Moore, Alexander Russell

Electron. Colloquium Comput. Complex., 2014

Linear codes cannot approximate the network capacity within any constant factor.

Shachar Lovett

Electron. Colloquium Comput. Complex., 2014

Recent advances on the log-rank conjecture in communication complexity.

Shachar Lovett

Electron. Colloquium Comput. Complex., 2014

0-1 Integer Linear Programming with a Linear Number of Constraints.

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

Electron. Colloquium Comput. Complex., 2014

General systems of linear forms: equidistribution and true complexity.

Hamed Hatami, Pooya Hatami, Shachar Lovett

Electron. Colloquium Comput. Complex., 2014

Rectangles Are Nonnegative Juntas.

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

Electron. Colloquium Comput. Complex., 2014

List decoding Reed-Muller codes over small fields.

Abhishek Bhowmick, Shachar Lovett

Electron. Colloquium Comput. Complex., 2014

Nonclassical polynomials as a barrier to polynomial lower bounds.

Abhishek Bhowmick, Shachar Lovett

Electron. Colloquium Comput. Complex., 2014

Variety Evasive Sets.

Zeev Dvir, János Kollár, Shachar Lovett

Comput. Complex., 2014

Cooperative weakest link games.

Yoram Bachrach, Omer Lev, Shachar Lovett, Jeffrey S. Rosenschein, Morteza Zadimoghaddam

Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2014

2013

Almost k-Wise vs. k-Wise Independent Permutations, and Uniformity for General Group Actions.

Noga Alon, Shachar Lovett

Theory Comput., 2013

A Space Lower Bound for Dynamic Approximate Membership Data Structures.

Shachar Lovett, Ely Porat

SIAM J. Comput., 2013

Estimating the distance from testable affine-invariant properties.

Hamed Hatami, Shachar Lovett

Electron. Colloquium Comput. Complex., 2013

En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations.

Dmitry Gavinsky, Shachar Lovett

Electron. Colloquium Comput. Complex., 2013

Nontrivial t-designs over finite fields exist for all t.

Arman Fazeli, Shachar Lovett, Alexander Vardy

Electron. Colloquium Comput. Complex., 2013

Non-malleable Codes from Additive Combinatorics.

Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett

Electron. Colloquium Comput. Complex., 2013

Probabilistic existence of regular combinatorial structures

Greg Kuperberg, Shachar Lovett, Ron Peled

CoRR, 2013

Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields.

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

Comput. Complex., 2013

2012

Weight Distribution and List-Decoding Size of Reed-Muller Codes.

Tali Kaufman, Shachar Lovett, Ely Porat

IEEE Trans. Inf. Theory, 2012

A Tail Bound for Read-k Families of Functions.

Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2012

The Freiman-Ruzsa Theorem in Finite Fields.

Chaim Even-Zohar, Shachar Lovett

Electron. Colloquium Comput. Complex., 2012

New Lower Bounds for Matching Vector Codes.

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

Electron. Colloquium Comput. Complex., 2012

Testing Low Complexity Affine-Invariant Properties.

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett

Electron. Colloquium Comput. Complex., 2012

Every locally characterized affine-invariant property is testable.

Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

Electron. Colloquium Comput. Complex., 2012

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits.

Chris Beck, Russell Impagliazzo, Shachar Lovett

Electron. Colloquium Comput. Complex., 2012

Equivalence of polynomial conjectures in additive combinatorics.

Shachar Lovett

Comb., 2012

Bounded-Depth Circuits Cannot Sample Good Codes.

Shachar Lovett, Emanuele Viola

Comput. Complex., 2012

Random low-degree polynomials are hard to approximate.

Ido Ben-Eliezer, Rani Hod, Shachar Lovett

Comput. Complex., 2012

Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem.

Zohar Shay Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, Omri Weinstein

Proceedings of the COLT 2012, 2012

Pseudorandom Generators for Read-Once ACC^0.

Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Inverse Conjecture for the Gowers Norm is False.

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky

Theory Comput., 2011

Computing Polynomials with Few Multiplications.

Shachar Lovett

Theory Comput., 2011

Probabilistic existence of rigid combinatorial structures.

Greg Kuperberg, Shachar Lovett, Ron Peled

Electron. Colloquium Comput. Complex., 2011

Correlation testing for affine invariant properties on F_pⁿ in the high error regime.

Hamed Hatami, Shachar Lovett

Electron. Colloquium Comput. Complex., 2011

Subspace Evasive Sets.

Zeev Dvir, Shachar Lovett

Electron. Colloquium Comput. Complex., 2011

Linear systems over abelian groups.

Arkadev Chattopadhyay, Shachar Lovett

Electron. Colloquium Comput. Complex., 2011

An additive combinatorics approach to the log-rank conjecture in communication complexity.

Eli Ben-Sasson, Shachar Lovett, Noga Zewi

Electron. Colloquium Comput. Complex., 2011

On the Furthest Hyperplane Problem and Maximal Margin Clustering

Edo Liberty, Shachar Lovett, Omri Weinstein

CoRR, 2011

Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime

Hamed Hatami, Shachar Lovett

CoRR, 2011

New Extension of the Weil Bound for Character Sums with Applications to Coding.

Tali Kaufman, Shachar Lovett

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Linear Systems over Finite Abelian Groups.

Arkadev Chattopadhyay, Shachar Lovett

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 - o(1) Symmetric Gates.

Shachar Lovett, Srikanth Srinivasan

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Holes in generalized Reed-Muller codes.

Shachar Lovett

IEEE Trans. Inf. Theory, 2010

A lower bound for dynamic approximate membership data structures.

Shachar Lovett, Ely Porat

Electron. Colloquium Comput. Complex., 2010

Pseudorandom generators for CC₀[p] and the Fourier spectrum of low-degree polynomials over finite fields.

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

Electron. Colloquium Comput. Complex., 2010

An elementary proof of anti-concentration of polynomials in Gaussian variables.

Shachar Lovett

Electron. Colloquium Comput. Complex., 2010

Testing of exponentially large codes, by a new extension to Weil bound for character sums.

Tali Kaufman, Shachar Lovett

Electron. Colloquium Comput. Complex., 2010

Higher-order Fourier analysis of F_pⁿ and the complexity of systems of linear forms.

Hamed Hatami, Shachar Lovett

Electron. Colloquium Comput. Complex., 2010

The Complexity of Boolean Functions in Different Characteristics.

Parikshit Gopalan, Amir Shpilka, Shachar Lovett

Comput. Complex., 2010

2009

Unconditional Pseudorandom Generators for Low Degree Polynomials.

Shachar Lovett

Theory Comput., 2009

Explicit lower bound for fooling polynomials by the sum of small-bias generators.

Shachar Lovett, Yoav Tzur

Electron. Colloquium Comput. Complex., 2009

Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness.

Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin

Electron. Colloquium Comput. Complex., 2009

The density of weights of Generalized Reed-Muller codes.

Shachar Lovett

Electron. Colloquium Comput. Complex., 2009

Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Ido Ben-Eliezer, Shachar Lovett, Ariel Yadin

CoRR, 2009

On cryptography with auxiliary input.

Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Pseudorandom Bit Generators That Fool Modular Sums.

Shachar Lovett, Omer Reingold, Luca Trevisan, Salil P. Vadhan

Proceedings of the Approximation, 2009

2008

The List-Decoding Size of Reed-Muller Codes.

Shachar Lovett, Tali Kaufman

Electron. Colloquium Comput. Complex., 2008

Worst case to Average case reductions for polynomials.

Shachar Lovett, Tali Kaufman

Electron. Colloquium Comput. Complex., 2008

Lower bounds for adaptive linearity tests.

Shachar Lovett

Proceedings of the STACS 2008, 2008

2007

Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits.

Shachar Lovett, Sasha Sodin

Electron. Colloquium Comput. Complex., 2007

Tight lower bounds for adaptive linearity tests.

Shachar Lovett

Electron. Colloquium Comput. Complex., 2007