Shachar Lovett

Anthony Ostuni

Electron. Colloquium Comput. Complex., 2024

2023

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

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, February, 2023

Streaming Lower Bounds and Asymmetric Set-Disjointness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

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

[BibT_eX]

[DOI]

Zander Kelley

Raghu Meka

Electron. Colloquium Comput. Complex., 2023

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Do PAC-Learners Learn the Marginal Distribution?

[BibT_eX]

[DOI]

CoRR, 2023

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

[BibT_eX]

[DOI]

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

Exponential Hardness of Reinforcement Learning with Linear Function Approximation.

[BibT_eX]

[DOI]

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

2022

Sunflowers and Robust Sunflowers from Randomness Extractors.

[BibT_eX]

[DOI]

Xin Li

Adv. Math. Commun., 2022

Fractional certificates for bounded functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Computational-Statistical Gaps in Reinforcement Learning.

[BibT_eX]

[DOI]

CoRR, 2022

Hypercontractivity on high dimensional expanders.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

Lifting with Sunflowers.

[BibT_eX]

[DOI]

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

Computational-Statistical Gap in Reinforcement Learning.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2022

2021

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

[BibT_eX]

[DOI]

SIGACT News, 2021

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

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

[BibT_eX]

[DOI]

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

Bounded Memory Active Learning through Enriched Queries.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Fractional Pseudorandom Generators from Any Fourier Level.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

Singularity of Random Integer Matrices with Large Entries.

[BibT_eX]

[DOI]

Sankeerth Rao Karingula

Proceedings of the Approximation, 2021

2020

Probabilistic existence of large sets of designs.

[BibT_eX]

[DOI]

Sankeerth Rao

Alexander Vardy

J. Comb. Theory A, 2020

Improved lifting theorems via robust sunflowers.

[BibT_eX]

[DOI]

Raghu Meka

Electron. Colloquium Comput. Complex., 2020

Log-rank and lifting for AND-functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

Sankeerth Rao Karingula

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

Max Hopkins

Electron. Colloquium Comput. Complex., 2020

The Power of Comparisons for Actively Learning Linear Classifiers.

[BibT_eX]

[DOI]

Max Hopkins

Daniel Kane

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.

[BibT_eX]

[DOI]

Alon Gonen

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.

[BibT_eX]

[DOI]

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

Noise-tolerant, Reliable Active Classification with Comparison Queries.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

2019

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

[BibT_eX]

[DOI]

Theory Comput., 2019

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

[BibT_eX]

[DOI]

Theory Comput., 2019

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

[BibT_eX]

[DOI]

Daniel Kane

Sankeerth Rao

SIAM J. Comput., 2019

Higher-order Fourier Analysis and Applications.

[BibT_eX]

[DOI]

Pooya Hatami

Found. Trends Theor. Comput. Sci., 2019

Decision list compression by mild random restrictions.

[BibT_eX]

[DOI]

Kewen Wu

Electron. Colloquium Comput. Complex., 2019

From DNF compression to sunflower theorems via regularity.

[BibT_eX]

[DOI]

Noam Solomon

Electron. Colloquium Comput. Complex., 2019

Sign rank vs Discrepancy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

XOR Lemmas for Resilient Functions Against Polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Improved bounds for the sunflower lemma.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

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

[BibT_eX]

[DOI]

Ryan O'Donnell

Theory Comput., 2018

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

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2018

Structure of Protocols for XOR Functions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Algebraic Attacks against Random Local Functions and Their Countermeasures.

[BibT_eX]

[DOI]

Benny Applebaum

SIAM J. Comput., 2018

Non-Malleable Codes from Additive Combinatorics.

[BibT_eX]

[DOI]

Divesh Aggarwal

Yevgeniy Dodis

SIAM J. Comput., 2018

DNF sparsification beyond sunflowers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

A proof of the GM-MDS conjecture.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Sunflowers and Quasi-sunflowers from Randomness Extractors.

[BibT_eX]

[DOI]

Xin Li

Electron. Colloquium Comput. Complex., 2018

Generalized comparison trees for point-location problems.

[BibT_eX]

[DOI]

Daniel M. Kane

Shay Moran

Electron. Colloquium Comput. Complex., 2018

Optimality of Linear Sketching under Modular Updates.

[BibT_eX]

[DOI]

Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2018

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Equality Alone Does Not Simulate Randomness.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Marc Vinyals

Electron. Colloquium Comput. Complex., 2018

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Pseudorandom Generators from Polarizing Random Walks.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Hardness Amplification for Non-Commutative Arithmetic Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Torus polynomials: an algebraic approach to ACC lower bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

The Robust Sensitivity of Boolean Functions.

[BibT_eX]

[DOI]

Avishay Tal

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.

[BibT_eX]

[DOI]

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

2017

Additive Combinatorics and its Applications in Theoretical Computer Science.

[BibT_eX]

[DOI]

Theory Comput., 2017

On the structure of the spectrum of small sets.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2017

Labeling the complete bipartite graph with no zero cycles.

[BibT_eX]

[DOI]

Daniel M. Kane

Sankeerth Rao

Electron. Colloquium Comput. Complex., 2017

Active classification with comparison queries.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Near-optimal linear decision trees for k-SUM and related problems.

[BibT_eX]

[DOI]

Daniel M. Kane

Shay Moran

Electron. Colloquium Comput. Complex., 2017

2016

Rectangles Are Nonnegative Juntas.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Robust sensitivity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Noisy Population Recovery from Unknown Noise.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

The Fourier structure of low degree polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Structure of protocols for XOR functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

2015

Constructive Discrepancy Minimization by Walking on the Edges.

[BibT_eX]

[DOI]

Raghu Meka

SIAM J. Comput., 2015

A tail bound for read-k families of functions.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2015

On the Beck-Fiala Conjecture for Random Set Systems.

[BibT_eX]

[DOI]

Esther Ezra

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

Divesh Aggarwal

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Large Supports are Required for Well-Supported Nash Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

New Bounds for Matching Vector Families.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

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

[BibT_eX]

[DOI]

Arman Fazeli

Alexander Vardy

J. Comb. Theory A, 2014

The Freiman-Ruzsa theorem over finite fields.

[BibT_eX]

[DOI]

Chaim Even-Zohar

J. Comb. Theory A, 2014

An Additive Combinatorics Approach Relating Rank to Communication Complexity.

[BibT_eX]

[DOI]

Eli Ben-Sasson

Noga Ron-Zewi

J. ACM, 2014

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Group representations that resist random sampling.

[BibT_eX]

[DOI]

Cristopher Moore

Alexander Russell

Electron. Colloquium Comput. Complex., 2014

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

General systems of linear forms: equidistribution and true complexity.

[BibT_eX]

[DOI]

Pooya Hatami

Electron. Colloquium Comput. Complex., 2014

List decoding Reed-Muller codes over small fields.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Nonclassical polynomials as a barrier to polynomial lower bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Variety Evasive Sets.

[BibT_eX]

[DOI]

János Kollár

Comput. Complex., 2014

Cooperative weakest link games.

[BibT_eX]

[DOI]

Yoram Bachrach

Omer Lev

Jeffrey S. Rosenschein

Morteza Zadimoghaddam

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

2013

A Space Lower Bound for Dynamic Approximate Membership Data Structures.

[BibT_eX]

[DOI]

Ely Porat

SIAM J. Comput., 2013

Communication is bounded by root of rank.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Estimating the distance from testable affine-invariant properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

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

[BibT_eX]

[DOI]

Dmitry Gavinsky

Electron. Colloquium Comput. Complex., 2013

Probabilistic existence of regular combinatorial structures

[BibT_eX]

[DOI]

Greg Kuperberg

Ron Peled

CoRR, 2013

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

[BibT_eX]

[DOI]

Partha Mukhopadhyay

Amir Shpilka

Comput. Complex., 2013

2012

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

[BibT_eX]

[DOI]

Ely Porat

IEEE Trans. Inf. Theory, 2012

An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

A Tail Bound for Read-k Families of Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

The Freiman-Ruzsa Theorem in Finite Fields.

[BibT_eX]

[DOI]

Chaim Even-Zohar

Electron. Colloquium Comput. Complex., 2012

New Lower Bounds for Matching Vector Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Testing Low Complexity Affine-Invariant Properties.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Eldar Fischer

Electron. Colloquium Comput. Complex., 2012

Every locally characterized affine-invariant property is testable.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

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

[BibT_eX]

[DOI]

Chris Beck

Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2012

Bounded-Depth Circuits Cannot Sample Good Codes.

[BibT_eX]

[DOI]

Emanuele Viola

Comput. Complex., 2012

Random low-degree polynomials are hard to approximate.

[BibT_eX]

[DOI]

Ido Ben-Eliezer

Rani Hod

Comput. Complex., 2012

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

[BibT_eX]

[DOI]

Proceedings of the COLT 2012, 2012

Pseudorandom Generators for Read-Once ACC^0.

[BibT_eX]

[DOI]

Dmitry Gavinsky

Srikanth Srinivasan

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Computing polynomials with few multiplications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Probabilistic existence of rigid combinatorial structures.

[BibT_eX]

[DOI]

Greg Kuperberg

Ron Peled

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Subspace Evasive Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Linear systems over abelian groups.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

Eli Ben-Sasson

Noga Zewi

Electron. Colloquium Comput. Complex., 2011

Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions.

[BibT_eX]

[DOI]

Noga Alon

Electron. Colloquium Comput. Complex., 2011

On the Furthest Hyperplane Problem and Maximal Margin Clustering

[BibT_eX]

[DOI]

Edo Liberty

Omri Weinstein

CoRR, 2011

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

[BibT_eX]

[DOI]

CoRR, 2011

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

[BibT_eX]

[DOI]

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

Linear Systems over Finite Abelian Groups.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

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.

[BibT_eX]

[DOI]

Srikanth Srinivasan

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

2010

Holes in generalized Reed-Muller codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2010

A lower bound for dynamic approximate membership data structures.

[BibT_eX]

[DOI]

Ely Porat

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Partha Mukhopadhyay

Amir Shpilka

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Equivalence of polynomial conjectures in additive combinatorics.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

The Complexity of Boolean Functions in Different Characteristics.

[BibT_eX]

[DOI]

Parikshit Gopalan

Amir Shpilka

Comput. Complex., 2010

2009

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

[BibT_eX]

[DOI]

Yoav Tzur

Electron. Colloquium Comput. Complex., 2009

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

[BibT_eX]

[DOI]

Ido Ben-Eliezer

Ariel Yadin

Electron. Colloquium Comput. Complex., 2009

The density of weights of Generalized Reed-Muller codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

[BibT_eX]

[DOI]

Ido Ben-Eliezer

Ariel Yadin

CoRR, 2009

On cryptography with auxiliary input.

[BibT_eX]

[DOI]

Yevgeniy Dodis

Yael Tauman Kalai

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

Pseudorandom Bit Generators That Fool Modular Sums.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

The List-Decoding Size of Reed-Muller Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Worst case to Average case reductions for polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Lower bounds for adaptive linearity tests.

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

2007

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

[BibT_eX]

[DOI]

Sasha Sodin

Electron. Colloquium Comput. Complex., 2007

Inverse Conjecture for the Gowers norm is false.

[BibT_eX]

[DOI]

Roy Meshulam

Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2007

Tight lower bounds for adaptive linearity tests.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Unconditional pseudorandom generators for low degree polynomials.

[BibT_eX]

[DOI]