Shachar Lovett

According to our database1, Shachar Lovett authored at least 119 papers between 2007 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2020
Improved lifting theorems via robust sunflowers.
Electron. Colloquium Comput. Complex., 2020

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

Log-rank and lifting for AND-functions.
CoRR, 2020

Fractional Pseudorandom Generators from Any Fourier Level.
CoRR, 2020

Point Location and Active Learning: Learning Halfspaces Almost Optimally.
CoRR, 2020

Towards a combinatorial characterization of bounded memory learning.
CoRR, 2020

Noise-tolerant, Reliable Active Classification with Comparison Queries.
Proceedings of the Conference on Learning Theory, 2020

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

Near-optimal Linear Decision Trees for k-SUM and Related Problems.
J. ACM, 2019

Higher-order Fourier Analysis and Applications.
Found. Trends Theor. Comput. Sci., 2019

Decision list compression by mild random restrictions.
Electron. Colloquium Comput. Complex., 2019

From DNF compression to sunflower theorems via regularity.
Electron. Colloquium Comput. Complex., 2019

Sign rank vs Discrepancy.
Electron. Colloquium Comput. Complex., 2019

XOR Lemmas for Resilient Functions Against Polynomials.
Electron. Colloquium Comput. Complex., 2019

Improved bounds for the sunflower lemma.
Electron. Colloquium Comput. Complex., 2019

The Power of Comparisons for Actively Learning Linear Classifiers.
CoRR, 2019

2018
Special Issue: CCC 2017: Guest Editor's Foreword.
Theory Comput., 2018

The List Decoding Radius for Reed-Muller Codes Over Small Fields.
IEEE Trans. Inf. Theory, 2018

Structure of Protocols for XOR Functions.
SIAM J. Comput., 2018

DNF sparsification beyond sunflowers.
Electron. Colloquium Comput. Complex., 2018

A proof of the GM-MDS conjecture.
Electron. Colloquium Comput. Complex., 2018

Sunflowers and Quasi-sunflowers from Randomness Extractors.
Electron. Colloquium Comput. Complex., 2018

Generalized comparison trees for point-location problems.
Electron. Colloquium Comput. Complex., 2018

Optimality of Linear Sketching under Modular Updates.
Electron. Colloquium Comput. Complex., 2018

A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds.
Electron. Colloquium Comput. Complex., 2018

Equality Alone Does Not Simulate Randomness.
Electron. Colloquium Comput. Complex., 2018

Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates.
Electron. Colloquium Comput. Complex., 2018

Pseudorandom Generators from Polarizing Random Walks.
Electron. Colloquium Comput. Complex., 2018

Hardness Amplification for Non-Commutative Arithmetic Circuits.
Electron. Colloquium Comput. Complex., 2018

Torus polynomials: an algebraic approach to ACC lower bounds.
Electron. Colloquium Comput. Complex., 2018

The gram-schmidt walk: a cure for the Banaszczyk blues.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Robust Sensitivity of Boolean Functions.
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.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Additive Combinatorics and its Applications in Theoretical Computer Science.
Theory Comput., 2017

On the structure of the spectrum of small sets.
J. Comb. Theory, Ser. A, 2017

Probabilistic Existence of Large Sets of Designs.
Electron. Colloquium Comput. Complex., 2017

Labeling the complete bipartite graph with no zero cycles.
Electron. Colloquium Comput. Complex., 2017

Active classification with comparison queries.
Electron. Colloquium Comput. Complex., 2017

2016
Communication is Bounded by Root of Rank.
J. ACM, 2016

Robust sensitivity.
Electron. Colloquium Comput. Complex., 2016

On the impossibility of entropy reversal, and its application to zero-knowledge proofs.
Electron. Colloquium Comput. Complex., 2016

Noisy Population Recovery from Unknown Noise.
Electron. Colloquium Comput. Complex., 2016

The Fourier structure of low degree polynomials.
Electron. Colloquium Comput. Complex., 2016

Structure of protocols for XOR functions.
Electron. Colloquium Comput. Complex., 2016

Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem.
Proceedings of the Approximation, 2016

2015
An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem.
Theory Comput., 2015

Constructive Discrepancy Minimization by Walking on the Edges.
SIAM J. Comput., 2015

A tail bound for read-<i>k</i> families of functions.
Random Struct. Algorithms, 2015

On the Beck-Fiala Conjecture for Random Set Systems.
Electron. Colloquium Comput. Complex., 2015

Algebraic Attacks against Random Local Functions and Their Countermeasures.
Electron. Colloquium Comput. Complex., 2015

Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification.
Electron. Colloquium Comput. Complex., 2015

Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory.
Electron. Colloquium Comput. Complex., 2015

Large Supports are Required for Well-Supported Nash Equilibria.
Proceedings of the Approximation, 2015

2014
Correlation Testing for Affine Invariant Properties on 픽<sub>p<sup>n</sup></sub> in the High Error Regime.
SIAM J. Comput., 2014

New Bounds for Matching Vector Families.
SIAM J. Comput., 2014

The Freiman-Ruzsa theorem over finite fields.
J. Comb. Theory, Ser. A, 2014

An Additive Combinatorics Approach Relating Rank to Communication Complexity.
J. ACM, 2014

Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions.
Electron. Colloquium Comput. Complex., 2014

Group representations that resist random sampling.
Electron. Colloquium Comput. Complex., 2014

Linear codes cannot approximate the network capacity within any constant factor.
Electron. Colloquium Comput. Complex., 2014

Recent advances on the log-rank conjecture in communication complexity.
Electron. Colloquium Comput. Complex., 2014

0-1 Integer Linear Programming with a Linear Number of Constraints.
Electron. Colloquium Comput. Complex., 2014

General systems of linear forms: equidistribution and true complexity.
Electron. Colloquium Comput. Complex., 2014

Rectangles Are Nonnegative Juntas.
Electron. Colloquium Comput. Complex., 2014

List decoding Reed-Muller codes over small fields.
Electron. Colloquium Comput. Complex., 2014

Nonclassical polynomials as a barrier to polynomial lower bounds.
Electron. Colloquium Comput. Complex., 2014

Variety Evasive Sets.
Comput. Complex., 2014

Cooperative weakest link games.
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.
Theory Comput., 2013

A Space Lower Bound for Dynamic Approximate Membership Data Structures.
SIAM J. Comput., 2013

Estimating the distance from testable affine-invariant properties.
Electron. Colloquium Comput. Complex., 2013

En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations.
Electron. Colloquium Comput. Complex., 2013

Nontrivial t-designs over finite fields exist for all t.
Electron. Colloquium Comput. Complex., 2013

Non-malleable Codes from Additive Combinatorics.
Electron. Colloquium Comput. Complex., 2013

Probabilistic existence of regular combinatorial structures
CoRR, 2013

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

2012
Weight Distribution and List-Decoding Size of Reed-Muller Codes.
IEEE Trans. Inf. Theory, 2012

A Tail Bound for Read-k Families of Functions.
Electron. Colloquium Comput. Complex., 2012

The Freiman-Ruzsa Theorem in Finite Fields.
Electron. Colloquium Comput. Complex., 2012

New Lower Bounds for Matching Vector Codes.
Electron. Colloquium Comput. Complex., 2012

Testing Low Complexity Affine-Invariant Properties.
Electron. Colloquium Comput. Complex., 2012

Every locally characterized affine-invariant property is testable.
Electron. Colloquium Comput. Complex., 2012

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits.
Electron. Colloquium Comput. Complex., 2012

Equivalence of polynomial conjectures in additive combinatorics.
Comb., 2012

Bounded-Depth Circuits Cannot Sample Good Codes.
Comput. Complex., 2012

Random low-degree polynomials are hard to approximate.
Comput. Complex., 2012

Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem.
Proceedings of the COLT 2012, 2012

Pseudorandom Generators for Read-Once ACC^0.
Proceedings of the 27th Conference on Computational Complexity, 2012

2011
Inverse Conjecture for the Gowers Norm is False.
Theory Comput., 2011

Computing Polynomials with Few Multiplications.
Theory Comput., 2011

Probabilistic existence of rigid combinatorial structures.
Electron. Colloquium Comput. Complex., 2011

Correlation testing for affine invariant properties on F<sub>p</sub><sup>n</sup> in the high error regime.
Electron. Colloquium Comput. Complex., 2011

Subspace Evasive Sets.
Electron. Colloquium Comput. Complex., 2011

Linear systems over abelian groups.
Electron. Colloquium Comput. Complex., 2011

An additive combinatorics approach to the log-rank conjecture in communication complexity.
Electron. Colloquium Comput. Complex., 2011

On the Furthest Hyperplane Problem and Maximal Margin Clustering
CoRR, 2011

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

New Extension of the Weil Bound for Character Sums with Applications to Coding.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Linear Systems over Finite Abelian Groups.
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.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Holes in generalized Reed-Muller codes.
IEEE Trans. Inf. Theory, 2010

A lower bound for dynamic approximate membership data structures.
Electron. Colloquium Comput. Complex., 2010

Pseudorandom generators for CC<sub>0</sub>[p] and the Fourier spectrum of low-degree polynomials over finite fields.
Electron. Colloquium Comput. Complex., 2010

An elementary proof of anti-concentration of polynomials in Gaussian variables.
Electron. Colloquium Comput. Complex., 2010

Testing of exponentially large codes, by a new extension to Weil bound for character sums.
Electron. Colloquium Comput. Complex., 2010

Higher-order Fourier analysis of F<sub>p</sub><sup>n</sup> and the complexity of systems of linear forms.
Electron. Colloquium Comput. Complex., 2010

The Complexity of Boolean Functions in Different Characteristics.
Comput. Complex., 2010

2009
Unconditional Pseudorandom Generators for Low Degree Polynomials.
Theory Comput., 2009

Explicit lower bound for fooling polynomials by the sum of small-bias generators.
Electron. Colloquium Comput. Complex., 2009

Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness.
Electron. Colloquium Comput. Complex., 2009

The density of weights of Generalized Reed-Muller codes.
Electron. Colloquium Comput. Complex., 2009

Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness
CoRR, 2009

On cryptography with auxiliary input.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Pseudorandom Bit Generators That Fool Modular Sums.
Proceedings of the Approximation, 2009

2008
The List-Decoding Size of Reed-Muller Codes.
Electron. Colloquium Comput. Complex., 2008

Worst case to Average case reductions for polynomials.
Electron. Colloquium Comput. Complex., 2008

Lower bounds for adaptive linearity tests.
Proceedings of the STACS 2008, 2008

2007
Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits.
Electron. Colloquium Comput. Complex., 2007

Tight lower bounds for adaptive linearity tests.
Electron. Colloquium Comput. Complex., 2007


  Loading...