Peter Manohar

CoRR, August, 2025

Solving Random Planted CSPs below the nk/2} Threshold.

[BibT_eX]

[DOI]

CoRR, July, 2025

New Spectral Algorithms for Refuting Smoothed k-SAT.

[BibT_eX]

[DOI]

Commun. ACM, March, 2025

Spectral Refutations of Semirandom k-LIN over Larger Fields.

[BibT_eX]

[DOI]

Nicholas Kocurek

Proceedings of the Approximation, 2025

2024

Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs.

[BibT_eX]

[DOI]

Pravesh Kothari

Electron. Colloquium Comput. Complex., 2024

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs.

[BibT_eX]

[DOI]

Oliver Janzer

Electron. Colloquium Comput. Complex., 2024

A kq/q-2 Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs.

[BibT_eX]

[DOI]

Oliver Janzer

CoRR, 2024

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes.

[BibT_eX]

[DOI]

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

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs.

[BibT_eX]

[DOI]

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

2023

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation.

[BibT_eX]

[DOI]

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

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold.

[BibT_eX]

[DOI]

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

2022

Sparsity and 𝓁p-Restricted Isometry.

[BibT_eX]

[DOI]

Jonathan Mosheiff

CoRR, 2022

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random.

[BibT_eX]

[DOI]

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

ℓp-Spread and Restricted Isometry Properties of Sparse Random Matrices.

[BibT_eX]

[DOI]

Jonathan Mosheiff

Proceedings of the 37th Computational Complexity Conference, 2022

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2022

Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally.

[BibT_eX]

[DOI]

Brian Hu Zhang

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

2021

𝓁p-Spread Properties of Sparse Matrices.

[BibT_eX]

[DOI]

Jonathan Mosheiff

CoRR, 2021

A Stress-Free Sum-Of-Squares Lower Bound for Coloring.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

2020

HABIT: Hardware-Assisted Bluetooth-based Infection Tracking.

[BibT_eX]

[DOI]

Nathan Manohar

Rajit Manohar

IACR Cryptol. ePrint Arch., 2020

Lower Bounds for Caching with Delayed Hits.

[BibT_eX]

[DOI]

Jalani Williams

CoRR, 2020

On Local Testability in the Non-Signaling Setting.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Succinct Arguments in the Quantum Random Oracle Model.

[BibT_eX]

[DOI]

Nicholas Spooner

Proceedings of the Theory of Cryptography - 17th International Conference, 2019

Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing.

[BibT_eX]

[DOI]

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

2018

Testing Linearity against Non-Signaling Strategies.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

On Axis-Parallel Tests for Tensor Product Codes.

[BibT_eX]

[DOI]