Peter Manohar

Electron. Colloquium Comput. Complex., 2024

2023

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

[BibT_eX]

[DOI]

Pravesh Kothari

Electron. Colloquium Comput. Complex., 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

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2019

Succinct Arguments in the Quantum Random Oracle Model.

[BibT_eX]

[DOI]

Nicholas Spooner

IACR Cryptol. ePrint Arch., 2019

On Local Testability in the Non-Signaling Setting.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

Probabilistic Checking against Non-Signaling Strategies from Linearity Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Testing Linearity against Non-Signaling Strategies.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

2017

On Axis-Parallel Tests for Tensor Product Codes.

[BibT_eX]

[DOI]