Dor Minzer

Comput. Complex., December, 2025

A Dichotomy Theorem for Multi-Pass Streaming CSPs.

[BibT_eX]

[DOI]

Yumou Fei

Shuo Wang

CoRR, September, 2025

Turán Problems for Expanded Hypergraphs.

[BibT_eX]

[DOI]

Comb., June, 2025

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut.

[BibT_eX]

[DOI]

Yumou Fei

Shuo Wang

CoRR, March, 2025

Improved Round-by-round Soundness IOPs via Reed-Muller Codes.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2025

On Approximability of Satisfiable k-CSPs: V.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Parallel Repetition for 3-Player XOR Games.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity.

[BibT_eX]

[DOI]

Karthik C. S.

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Constant Degree Networks for Almost-Everywhere Reliable Transmission.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Quasi-Linear Size PCPs with Small Soundness from HDX.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

Reasonable Bounds for Combinatorial Lines of Length Three.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On Approximability of Satisfiable k-CSPs: VII.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On Approximability of Satisfiable k-CSPs: VI.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On Approximability of Satisfiable k-CSPs: VII.

[BibT_eX]

[DOI]

CoRR, 2024

On Approximability of Satisfiable k-CSPs: VI.

[BibT_eX]

[DOI]

CoRR, 2024

Quasi-Linear Size PCPs with Small Soundness from HDX.

[BibT_eX]

[DOI]

Nikhil Vyas

CoRR, 2024

Near Optimal Alphabet-Soundness Tradeoff PCPs.

[BibT_eX]

[DOI]

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

Influences in Mixing Measures.

[BibT_eX]

[DOI]

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

Product Mixing in Compact Lie Groups.

[BibT_eX]

[DOI]

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

On Approximability of Satisfiable k-CSPs: IV.

[BibT_eX]

[DOI]

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

Characterizing Direct Product Testing via Coboundary Expansion.

[BibT_eX]

[DOI]

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

Adversarial Low Degree Testing.

[BibT_eX]

[DOI]

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

A Dense Model Theorem for the Boolean Slice.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Constant Degree Direct Product Testers with Small Soundness.

[BibT_eX]

[DOI]

Noam Lifshitz

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Solving Unique Games over Globally Hypercontractive Graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

Parallel Repetition of k-Player Projection Games.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

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: II.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable k-CSPs: III.

[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]

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

Parallel Repetition for the GHZ Game: Exponential Decay.

[BibT_eX]

[DOI]

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

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

On approximability of satisfiable k-CSPs: I.

[BibT_eX]

[DOI]

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

Expander Random Walks: The General Case and Limitations.

[BibT_eX]

[DOI]

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

New separations results for external information.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

On Rich 2-to-1 Games.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 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

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

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

Small Set Expansion in The Johnson Graph.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

On non-optimally expanding sets in Grassmann graphs.

[BibT_eX]

[DOI]

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

Towards a proof of the 2-to-1 games conjecture?

[BibT_eX]

[DOI]

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

Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion.

[BibT_eX]

[DOI]

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

2017

On independent sets, 2-to-2 games, and Grassmann graphs.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2015

On Monotonicity Testing and Boolean Isoperimetric Type Theorems.

[BibT_eX]

[DOI]