Papers
 Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
arXiv 2021
Abstract:
We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and averagecase input models, where the input is an arbitrary instance of the CSP with only the negation patterns of the literals rerandomized with some small probability. For an nvariable smoothed instance of a karity CSP, our algorithm runs in n^O(\ell) time, and succeeds with high probability in bounding the optimum fraction of satisfiable constraints away from 1, provided that the number of constraints is at least \tilde{O}(n) (n/\ell)^((k/2)  1). This matches, up to polylogarithmic factors in n, the tradeoff between running time and the number of constraints of the stateoftheart algorithms for refuting fully random instances of CSPs [RRS17].
We also make a surprising new connection between our algorithm and even covers in hypergraphs, which we use to positively resolve Feige's 2008 conjecture, an extremal combinatorics conjecture on the existence of even covers in sufficiently dense hypergraphs that generalizes the wellknown Moore bound for the girth of graphs. As a corollary, we show that polynomialsize refutation witnesses exist for arbitrary smoothed CSP instances with number of constraints a polynomial factor below the "spectral threshold" of n^(k/2), extending the celebrated result for random 3SAT of Feige, Kim and Ofek [FKO06].
Full version available at [ arXiv].
 L_{p}Spread Properties of Sparse Matrices
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
arXiv 2021
Abstract:
Random subspaces X of R^{n} of dimension proportional to n are, with high probability, wellspread with respect to the L_{p}norm (for p in [1,2]). Namely, every nonzero x in X is "robustly nonsparse" in the following sense: x is (eps x_{p})far in L_{p}distance from all (delta n)sparse vectors, for positive constants eps, delta bounded away from 0. This "L_{p}spread" property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and, for p = 2, corresponds to X being a Euclidean section of the L_{1} unit ball. Explicit L_{p}spread subspaces of dimension Omega(n), however, are not known except for p = 1. The construction for p = 1, as well as the best known constructions for p in (1,2] (which achieve weaker spread properties), are analogs of low density parity check (LDPC) codes over the reals, i.e., they are kernels of certain sparse matrices.
Motivated by this, we study the spread properties of the kernels of sparse random matrices. Rather surprisingly, we prove that with high probability such subspaces contain vectors x that are o(1)x_2close to o(n)sparse with respect to the L_{2}norm, and in particular are not L_{2}spread. This is strikingly different from the case of random LDPC codes, whose distance is asymptotically almost as good as that of (dense) random linear codes.
On the other hand, for p < 2 we prove that such subspaces are L_{p}spread with high probability. The spread property of sparse random matrices thus exhibits a threshold behavior at p = 2. Our proof for p < 2 moreover shows that a random sparse matrix has the stronger restricted isometry property (RIP) with respect to the L_{p} norm. In fact, we show that RIP follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the L_{1} norm [BGI+08]. Instantiating this with suitable explicit expanders, we obtain the first explicit constructions of L_{p}spread subspaces and L_{p}RIP matrices for 1 <= p < p_0, where 1 < p_0 < 2 is an absolute constant.
Full version available at [ arXiv].
 A StressFree SumofSquares Lower Bound for Coloring
Pravesh K. Kothari, Peter Manohar
CCC 2021
Abstract:
We prove that with high probability over the choice of a random graph G from the ErdősRényi distribution G(n, 1/2), a natural n^O(eps^2 log n)time, degree O(eps^2 log n) sumofsquares semidefinite program cannot refute the existence of a valid kcoloring of G for k = n^(1/2 + eps). Our result implies that the refutation guarantee of the basic semidefinite program (a close variant of the Lovász theta function) cannot be appreciably improved by a natural o(log n)degree sumofsquares strengthening, and this is tight up to an o(1) slack in k. To the best of our knowledge, this is the first lower bound for coloring G(n, 1/2) for even a single round strengthening of the basic SDP in any SDP hierarchy.
Our proof relies on a new variant of instancepreserving nonpointwise complete reduction within SoS from coloring a graph to finding large independent sets in it. Our proof is (perhaps surprisingly) short, simple and does not require complicated spectral norm bounds on random matrices with dependent entries that have been otherwise necessary in the proofs of many similar results [BHK+16, HKP+17, KB19, GJJ+20, MRX20].
Our result formally holds for a constraint system where vertices are allowed to belong to multiple color classes; we leave the extension to the formally stronger formulation of coloring, where vertices must belong to unique colors classes, as an outstanding open problem.
Full version available at [ arXiv].
 On Local Testability in the NonSignaling Setting
Alessandro Chiesa, Peter Manohar, Igor Shinkar
ITCS 2020
Abstract:
Nonsignaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of localtoglobal phenomena for nonsignaling functions.
We prove that lowdegree testing in the nonsignaling setting is possible, assuming that the locality of the nonsignaling function exceeds a threshold. We additionally show that if the locality is below the threshold then the test fails spectacularly, in that there exists a nonsignaling function which passes the test with probability 1 and yet is maximally far from being lowdegree.
Along the way, we present general results about the local testability of linear codes in the nonsignaling setting. These include formulating natural definitions that capture the condition that a nonsignaling function "belongs" to a given code, and characterizing the sets of local constraints that imply membership in the code. We prove these results by formulating a logical inference system for linear constraints on nonsignaling functions that is complete and sound.
Full version available at [ ECCC].
 Succinct Arguments in the Quantum Random Oracle Model
Alessandro Chiesa, Peter Manohar, Nicholas Spooner
TCC 2019 and QIP 2020
Abstract:
Succinct noninteractive arguments (SNARGs) are highly efficient certificates of membership in nondeterministic languages. Constructions of SNARGs in the random oracle model are widely believed to be postquantum secure, provided the oracle is instantiated with a suitable postquantum hash function. No formal evidence, however, supports this belief.
In this work we provide the first such evidence by proving that the SNARG construction of Micali is unconditionally secure in the quantum random oracle model. We also prove that, analogously to the classical case, the SNARG inherits the zero knowledge and proof of knowledge properties of the PCP underlying the Micali construction. We thus obtain the first zero knowledge SNARG of knowledge (zkSNARK) that is secure in the quantum random oracle model.
Our main tool is a new lifting lemma that shows how, for a rich class of oracle games, we can generically deduce security against quantum attackers by bounding a natural classical property of these games. This means that in order to prove our theorem we only need to establish classical properties about the Micali construction. This approach not only lets us prove postquantum security but also enables us to prove explicit bounds that are tight up to small factors.
Finally, we use our techniques to prove that SNARGs based on interactive oracle proofs (IOPs) with roundbyround soundness are unconditionally secure in the quantum random oracle model. This result establishes the postquantum security of many SNARGs of practical interest.
Full version available at [ ePrint].
 Probabilistic Checking against NonSignaling Strategies from Linearity Testing
Alessandro Chiesa, Peter Manohar, Igor Shinkar
ITCS 2019
Abstract:
Nonsignaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proofs (PCPs) that are sound against nonsignaling strategies.
In this paper we prove that the exponentiallength constantquery PCP construction due to Arora et al. (JACM 1998) is sound against nonsignaling strategies.
Our result offers a new lengthvsquery tradeoff when compared to the nonsignaling PCP of Kalai, Raz, and Rothblum (STOC 2013 and 2014) and, moreover, may serve as an intermediate step to a proof of a nonsignaling analogue of the PCP Theorem.
Full version available at [ ECCC].
 Testing Linearity against NonSignaling Strategies
Alessandro Chiesa, Peter Manohar, Igor Shinkar
CCC 2018
Abstract:
Nonsignaling strategies are collections of distributions with certain nonlocal correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent nonlocality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.
We initiate the study of Property Testing against nonsignaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any nonsignaling strategy that passes the linearity test with high probability must be close to a quasidistribution over linear functions.
Quasidistributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that local views follow standard distributions (with nonnegative probabilities). Quasidistributions arise naturally in the study of Quantum Mechanics as a tool to describe various nonlocal phenomena.
Our analysis of the linearity test relies on Fourier analytic techniques applied to quasidistributions. Along the way, we also establish general equivalences between nonsignaling strategies and quasidistributions, which we believe will provide a useful perspective on the study of Property Testing against nonsignaling strategies beyond linearity testing.
Full version available at [ ECCC].
 On AxisParallel Tests for Tensor Product Codes
Alessandro Chiesa, Peter Manohar, Igor Shinkar
RANDOM 2017
Abstract:
Many lowdegree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the linevsline (Arora, Sudan 2003), planevsplane (Raz, Safra 1997), and cubevscube (Bhangale, Dinur, Navon 2017) tests.
In this paper we study tests that only consider restrictions along axisparallel hyperplanes, which have been studied by Polishchuk and Spielman (1994) and BenSasson and Sudan (2006).
While such tests are necessarily "weaker", they work for a more general class of codes, namely tensor product codes.
Moreover, axisparallel tests play a key role in constructing LTCs with inverse polylogarithmic rate and short PCPs (Polishchuk, Spielman 1994; BenSasson, Sudan 2008; Meir 2010). We present two results on axisparallel tests.
(1) Bivariate lowdegree testing with lowagreement.
We prove an analogue of the Bivariate LowDegree Testing Theorem of Polishchuk and Spielman in the lowagreement regime, albeit with much larger field size. Namely, for the 2wise tensor product of the ReedSolomon code, we prove that for sufficiently large fields, the 2query variant of the axisparallel line test (rowvscolumn test) works for arbitrarily small agreement. Prior analyses of axisparallel tests assumed high agreement, and no results for such tests in the lowagreement regime were known.
Our proof technique deviates significantly from that of Polishchuk and Spielman, which relies on algebraic methods such as Bézout's Theorem, and instead leverages a fundamental result in extremal graph theory by Kövári, Sós, and Turán. To our knowledge, this is the first time this result is used in the context of lowdegree testing.
(2) Improved robustness for tensor product codes.
Robustness is a strengthening of local testability that underlies many applications. We prove that the axisparallel hyperplane test for the mwise tensor product of a linear code with block length n and distance d is Omega(d^m/n^m)robust. This improves on a theorem of Viderman (2012) by a factor of 1/poly(m). While the improvement is not large, we believe that our proof is a notable simplification compared to prior work.
Full version available at [ ECCC].
Other projects
 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
Abstract:
Caches are a fundamental component of latencysensitive computer systems. Recent work of [ASWB20] has initi ated the study of delayed hits: a phenomenon in caches that occurs when the latency between the cache and backing store is much larger than the time between new requests. We present two results for the delayed hits caching model.
(1) Competitive ratio lower bound.
We prove that the competitive ratio of the algorithm in [ASWB20], and more generally of any deterministic online algorithm for delayed hits, is at least Omega(k Z), where k is the cache size and Z is the delay parameter.
(2) Antimonotonicity of the delayed hits latency.
Anti monotonicity is a naturally desirable property of cache latency: having a cache hit instead of a cache miss should result in lower overall latency. We prove that the latency of the delayed hits model is not antimonotone by ex hibiting a scenario where having a cache hit instead of a miss results in an increase in overall latency. We additionally present a modification of the delayed hits model that makes the latency antimonotone.
Full version available at [ arXiv].
AndrewNets 2020 is a mock conference for the final projects in CMU's graduate networks class. Our paper was "accepted" to appear in the "conference".
 Raymarched Microgeometry on Triangle Meshes
James Fong, Brian Lei, Peter Manohar
CS 184 Final Project Showcase
 ecfactory: A SageMath Library for Constructing Elliptic Curves
Alessandro Chiesa, Peter Manohar
SCIPR Lab
Teaching
