Shachar Lovett

Morgan Shirley

CoRR, October, 2025

Quasipolynomial bounds for the corners theorem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis.

[BibT_eX]

[DOI]

Yogesh Dahiya

Electron. Colloquium Comput. Complex., 2025

List Decoding Quotient Reed-Muller Codes.

[BibT_eX]

[DOI]

Omri Gotlib

Proceedings of the 40th Computational Complexity Conference, 2025

Do PAC-Learners Learn the Marginal Distribution?

[BibT_eX]

[DOI]

Proceedings of the International Conference on Algorithmic Learning Theory, 2025

2024

Corners in Quasirandom Groups via Sparse Mixing.

[BibT_eX]

[DOI]

Michael Jaber

Anthony Ostuni

Electron. Colloquium Comput. Complex., 2024

Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication.

[BibT_eX]

[DOI]

Zander Kelley

Raghu Meka

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Refuting Approaches to the Log-Rank Conjecture for XOR Functions.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

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

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, February, 2023

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

[BibT_eX]

[DOI]

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

Fractional Certificates for Bounded Functions.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Streaming Lower Bounds and Asymmetric Set-Disjointness.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 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

Theory Comput., 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

Realizable Learning is All You Need.

[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

Log-rank and lifting for AND-functions.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 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

Improved lifting theorems via robust sunflowers.

[BibT_eX]

[DOI]

Raghu Meka

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

Decision list compression by mild random restrictions.

[BibT_eX]

[DOI]

Kewen Wu

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

XOR lemmas for resilient functions against polynomials.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Improved bounds for the sunflower lemma.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 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

Sign Rank vs Discrepancy.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Higher-order Fourier Analysis and Applications.

[BibT_eX]

[DOI]

Pooya Hatami

Found. Trends Theor. Comput. Sci., 2019

DNF sparsification beyond sunflowers.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates.

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Torus Polynomials: An Algebraic Approach to ACC Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

From DNF Compression to Sunflower Theorems via Regularity.

[BibT_eX]

[DOI]

Noam Solomon

Proceedings of the 34th Computational Complexity Conference, 2019

Optimality of Linear Sketching Under Modular Updates.

[BibT_eX]

[DOI]

Grigory Yaroslavtsev

Proceedings of the 34th Computational Complexity Conference, 2019

Equality Alone Does not Simulate Randomness.

[BibT_eX]

[DOI]

Marc Vinyals

Proceedings of the 34th Computational Complexity Conference, 2019

2018

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

[BibT_eX]

[DOI]

Ryan O'Donnell

Theory Comput., 2018

A proof of the GM-MDS conjecture.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

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

[BibT_eX]

[DOI]

Daniel M. Kane

Shay Moran

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The gram-schmidt walk: a cure for the Banaszczyk blues.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 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

Probabilistic Existence of Large Sets of Designs.

[BibT_eX]

[DOI]

Sankeerth Rao

Alexander Vardy

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

Generalized Comparison Trees for Point-Location Problems.

[BibT_eX]

[DOI]

Daniel M. Kane

Shay Moran

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 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

Pseudorandom Generators from Polarizing Random Walks.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

Hardness Amplification for Non-Commutative Arithmetic Circuits.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

Sunflowers and Quasi-Sunflowers from Randomness Extractors.

[BibT_eX]

[DOI]

Xin Li

Proceedings of the Approximation, 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

On the Impossibility of Entropy Reversal, and Its Application to Zero-Knowledge Proofs.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 15th International Conference, 2017

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

[BibT_eX]

[DOI]

Daniel Kane

Sankeerth Rao

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Active Classification with Comparison Queries.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Noisy Population Recovery from Unknown Noise.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Robust sensitivity.

[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

Algebraic attacks against random local functions and their countermeasures.

[BibT_eX]

[DOI]

Benny Applebaum

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Affine-malleable extractors, spectrum doubling, and application to privacy amplification.

[BibT_eX]

[DOI]

Divesh Aggarwal

Proceedings of the IEEE International Symposium on Information Theory, 2016

Structure of Protocols for XOR Functions.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

On the Beck-Fiala Conjecture for Random Set Systems.

[BibT_eX]

[DOI]

Esther Ezra

Proceedings of the Approximation, 2016

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

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

A tail bound for read-k families of functions.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 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

Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Rectangles Are Nonnegative Juntas.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

The List Decoding Radius of Reed-Muller Codes over Small Fields.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 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

The Freiman-Ruzsa theorem over finite fields.

[BibT_eX]

[DOI]

Chaim Even-Zohar

J. Comb. Theory A, 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

Variety Evasive Sets.

[BibT_eX]

[DOI]

János Kollár

Comput. Complex., 2014

Communication is bounded by root of rank.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Non-malleable codes from additive combinatorics.

[BibT_eX]

[DOI]

Divesh Aggarwal

Yevgeniy Dodis

Proceedings of the Symposium on Theory of Computing, 2014

En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations.

[BibT_eX]

[DOI]

Dmitry Gavinsky

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 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

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

[BibT_eX]

[DOI]

Arman Fazeli

Alexander Vardy

Electron. Colloquium Comput. Complex., 2013

Probabilistic existence of regular combinatorial structures

[BibT_eX]

[DOI]

Greg Kuperberg

Ron Peled

CoRR, 2013

New bounds for matching vector families.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Every locally characterized affine-invariant property is testable.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Testing Low Complexity Affine-Invariant Properties.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Eldar Fischer

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Estimating the Distance from Testable Affine-Invariant Properties.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

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

Equivalence of polynomial conjectures in additive combinatorics.

[BibT_eX]

[DOI]

Comb., 2012

Probabilistic existence of rigid combinatorial structures.

[BibT_eX]

[DOI]

Greg Kuperberg

Ron Peled

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Subspace evasive sets.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Constructive Discrepancy Minimization by Walking on the Edges.

[BibT_eX]

[DOI]

Raghu Meka

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

An Additive Combinatorics Approach Relating Rank to Communication Complexity.

[BibT_eX]

[DOI]

Eli Ben-Sasson

Noga Ron-Zewi

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

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

[BibT_eX]

[DOI]

Chris Beck

Russell Impagliazzo

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 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

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

[BibT_eX]

[DOI]

Noga Alon

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

2011

Computing polynomials with few multiplications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Linear systems over abelian groups.

[BibT_eX]

[DOI]

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

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

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

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 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

Bounded-Depth Circuits Cannot Sample Good Codes.

[BibT_eX]

[DOI]

Emanuele Viola

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

Linear Systems over Finite Abelian Groups.

[BibT_eX]

[DOI]

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

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

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

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

[BibT_eX]

[DOI]

Ely Porat

Proceedings of the Innovations in Computer Science, 2010

A Lower Bound for Dynamic Approximate Membership Data Structures.

[BibT_eX]

[DOI]

Ely Porat

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields.

[BibT_eX]

[DOI]

Partha Mukhopadhyay

Amir Shpilka

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 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

On the Complexity of Boolean Functions in Different Characteristics.

[BibT_eX]

[DOI]

Parikshit Gopalan

Amir Shpilka

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Pseudorandom Bit Generators That Fool Modular Sums.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

Random Low Degree Polynomials are Hard to Approximate.

[BibT_eX]

[DOI]

Ido Ben-Eliezer

Rani Hod

Proceedings of the Approximation, 2009

2008

The List-Decoding Size of Reed-Muller Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Inverse conjecture for the gowers norm is false.

[BibT_eX]

[DOI]

Roy Meshulam

Alex Samorodnitsky

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Unconditional pseudorandom generators for low degree polynomials.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Lower bounds for adaptive linearity tests.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008

Worst Case to Average Case Reductions for Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 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

Tight lower bounds for adaptive linearity tests.

[BibT_eX]

[DOI]