Dor Minzer

Kai Zhe Zheng

Electron. Colloquium Comput. Complex., 2024

On Approximability of Satisfiable k-CSPs: V.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

Constant Degree Direct Product Testers with Small Soundness.

[BibT_eX]

[DOI]

Noam Lifshitz

Electron. Colloquium Comput. Complex., 2024

Parallel Repetition for 3-Player XOR Games.

[BibT_eX]

[DOI]

CoRR, 2024

Quasi-Linear Size PCPs with Small Soundness from HDX.

[BibT_eX]

[DOI]

Nikhil Vyas

CoRR, 2024

Influences in Mixing Measures.

[BibT_eX]

[DOI]

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

Adversarial Low Degree Testing.

[BibT_eX]

[DOI]

Kai Zhe Zheng

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

Solving Unique Games over Globally Hypercontractive Graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Product mixing in compact Lie groups.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable k-CSPs: IV.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable k-CSPs: II.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable k-CSPs: III.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Parallel Repetition of k-Player Projection Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Characterizing Direct Product Testing via Coboundary Expansion.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Effective Bounds for Restricted 3-Arithmetic Progressions in Fpn.

[BibT_eX]

[DOI]

CoRR, 2023

Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries.

[BibT_eX]

[DOI]

Kai Zheng

CoRR, 2023

On Approximability of Satisfiable k-CSPs: III.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

On Approximability of Satisfiable k-CSPs: II.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test.

[BibT_eX]

[DOI]

Kai Zheng

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

Rounding via Low Dimensional Embeddings.

[BibT_eX]

[DOI]

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

Improved Monotonicity Testers via Hypercube Embeddings.

[BibT_eX]

[DOI]

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

Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries.

[BibT_eX]

[DOI]

Kai Zhe Zheng

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

NP-Hardness of Almost Coloring Almost 3-Colorable Graphs.

[BibT_eX]

[DOI]

Yahli Hecht

Proceedings of the Approximation, 2023

2022

Parallel Repetition for the GHZ Game: Exponential Decay.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

On Approximability of Satisfiable k-CSPs: I.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Isoperimetric Inequalities Made Simpler.

[BibT_eX]

[DOI]

CoRR, 2022

Approximate polymorphisms.

[BibT_eX]

[DOI]

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

Improved Optimal Testing Results from Global Hypercontractivity.

[BibT_eX]

[DOI]

Tali Kaufman

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

On Monotonicity Testing and the 2-to-2 Games Conjecture

[BibT_eX]

[DOI]

ACM Books 49, ACM, ISBN: 978-1-4503-9968-5, 2022

2021

Expander Random Walks: The General Case and Limitations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

New separations results for external information.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

An Invariance Principle for the Multi-slice, with Applications.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Optimal tiling of the Euclidean space using symmetric bodies.

[BibT_eX]

[DOI]

CoRR, 2020

Hypercontractivity on the symmetric group.

[BibT_eX]

[DOI]

CoRR, 2020

AND testing and robust judgement aggregation.

[BibT_eX]

[DOI]

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

Towards a Proof of the Fourier-Entropy Conjecture?

[BibT_eX]

[DOI]

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

2019

On Rich $2$-to-$1$ Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Revisiting Bourgain-Kalai and Fourier Entropies.

[BibT_eX]

[DOI]

CoRR, 2019

Can Distributed Uniformity Testing Be Local?

[BibT_eX]

[DOI]

Uri Meir

Rotem Oshman

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Noise Sensitivity on the p -Biased Hypercube.

[BibT_eX]

[DOI]

Noam Lifshitz

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

On Monotonicity Testing and the 2-to-2 Games Conjecture

[BibT_eX]

[DOI]

PhD thesis, 2018

On Monotonicity Testing and Boolean Isoperimetric-type Theorems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Small Set Expansion in The Johnson Graph.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

2017

On Non-Optimally Expanding Sets in Grassmann Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

2016

On Independent Sets, 2-to-2 Games and Grassmann Graphs.

[BibT_eX]

[DOI]