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 NP-hard 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 pre-COVID era), I helped co-organize CMU's Theory Club with Pedro Paredes.
|
|
Papers
- A k^(q/(q-2)) Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
Oliver Janzer, Peter Manohar
arXiv 2024
- Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
Pravesh K. Kothari, Peter Manohar
FOCS 2024
- An Exponential Lower Bound for Linear 3-Query 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, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar
FOCS 2023
- A Near-Cubic Lower Bound for 3-Query 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 Lp-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
- Lp-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
- Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang
ALT 2022
- A Stress-Free Sum-of-Squares Lower Bound for Coloring
Pravesh K. Kothari, Peter Manohar
CCC 2021
- On Local Testability in the Non-Signaling 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 Non-Signaling Strategies from Linearity Testing
Alessandro Chiesa, Peter Manohar, Igor Shinkar
ITCS 2019
- Testing Linearity against Non-Signaling Strategies
Alessandro Chiesa, Peter Manohar, Igor Shinkar
CCC 2018
- On Axis-Parallel Tests for Tensor Product Codes
Alessandro Chiesa, Peter Manohar, Igor Shinkar
RANDOM 2017
Other Projects
- Implementation of a Hardware-Assisted Bluetooth-Based COVID-19 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: Hardware-Assisted Bluetooth-based 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
|