Peter Manohar
Email: pmanohar [at] ias [dot] edu
Office: 008 Simonyi Hall
About Me
I am a postdoctoral researcher in the Computer Science and Discrete Math group at the Institute for Advanced Study. I am broadly interested in Theoretical Computer Science, specifically in the areas of computational complexity, algorithms, and coding theory. My research is focused on designing spectral algorithms for semirandom and smoothed instances of NPhard constraint satisfaction problems and exploring connections between these spectral methods and problems in coding theory, extremal combinatorics, and cryptography.
I recently completed my PhD at Carnegie Mellon University, advised by Venkatesan Guruswami and Pravesh K. Kothari. My thesis is available here.
Prior to CMU, I completed a B.S. in EECS at UC Berkeley. At Berkeley, I was advised by Alessandro Chiesa, where I worked on property testing, probabilistically checkable proofs, and coding theory, and Ren Ng, where I worked on computer graphics.
At CMU, my research was supported by an NSF fellowship and a Cylab Presidential Fellowship. For the first three years of my PhD, I was also supported by an ARCS scholarship.
In Summer 2023, I was an intern at TTIC with Siddharth Bhandari, Yury Makarychev, and Madhur Tulsiani.
Once upon a time (in the preCOVID era), I helped coorganize CMU's Theory Club with Pedro Paredes.


Papers
 Exponential Lower Bounds for Smooth 3LCCs and Sharp Bounds for Designs
Pravesh K. Kothari, Peter Manohar
FOCS 2024
 An Exponential Lower Bound for Linear 3Query Locally Correctable Codes
Pravesh K. Kothari, Peter Manohar
STOC 2024
Article in Quanta Magazine
Invited to SICOMP Special Issue for STOC 2024
 Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
Venkatesan Guruswami, JunTing Hsieh, Pravesh K. Kothari, Peter Manohar
FOCS 2023
 A NearCubic Lower Bound for 3Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
STOC 2023
Invited to SICOMP Special Issue for STOC 2023
 Sparsity and L_{p}Restricted Isometry
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
arXiv 2022
 Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number
Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
APPROX 2022
 L_{p}Spread and Restricted Isometry Properties of Sparse Random Matrices
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
CCC 2022
 Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
STOC 2022
Invited to CACM Research Highlights
Invited to SICOMP Special Issue for STOC 2022
 PolynomialTime SumofSquares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang
ALT 2022
 A StressFree SumofSquares Lower Bound for Coloring
Pravesh K. Kothari, Peter Manohar
CCC 2021
 On Local Testability in the NonSignaling Setting
Alessandro Chiesa, Peter Manohar, Igor Shinkar
ITCS 2020
 Succinct Arguments in the Quantum Random Oracle Model
Alessandro Chiesa, Peter Manohar, Nicholas Spooner
TCC 2019 and QIP 2020
 Probabilistic Checking against NonSignaling Strategies from Linearity Testing
Alessandro Chiesa, Peter Manohar, Igor Shinkar
ITCS 2019
 Testing Linearity against NonSignaling Strategies
Alessandro Chiesa, Peter Manohar, Igor Shinkar
CCC 2018
 On AxisParallel Tests for Tensor Product Codes
Alessandro Chiesa, Peter Manohar, Igor Shinkar
RANDOM 2017
Other Projects
 Implementation of a HardwareAssisted BluetoothBased COVID19 Tracking Device in a High School: Mixed Methods Study
Dan Li, Tyler Shelby, Marie Brault, Rajit Manohar, Sten Vermund, Ashley Hagaman, Laura Forastiere, Tyler Caruthers, Emilie Egger, Yizhou Wang, Nathan Manohar, Peter Manohar, J Lucian Davis, Xin Zhou
JMIR Formative Research 2023
 HABIT: HardwareAssisted Bluetoothbased Infection Tracking
Nathan Manohar, Peter Manohar, Rajit Manohar
ePrint 2020
Now deployed at high schools in Connecticut!
 Lower Bounds for Caching with Delayed Hits
Peter Manohar, Jalani Williams
AndrewNets 2020
 Raymarched Microgeometry on Triangle Meshes
James Fong, Brian Lei, Peter Manohar
CS184 Final Project Showcase
 ecfactory: A SageMath Library for Constructing Elliptic Curves
Alessandro Chiesa, Peter Manohar
SCIPR Lab
Teaching
