Search Results

Documents authored by Manohar, Peter

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.42
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number

Authors: Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
Let H(k,n,p) be the distribution on k-uniform hypergraphs where every subset of [n] of size k is included as an hyperedge with probability p independently. In this work, we design and analyze a simple spectral algorithm that certifies a bound on the size of the largest clique, ω(H), in hypergraphs H ∼ H(k,n,p). For example, for any constant p, with high probability over the choice of the hypergraph, our spectral algorithm certifies a bound of Õ(√n) on the clique number in polynomial time. This matches, up to polylog(n) factors, the best known certificate for the clique number in random graphs, which is the special case of k = 2. Prior to our work, the best known refutation algorithms [Amin Coja-Oghlan et al., 2004; Sarah R. Allen et al., 2015] rely on a reduction to the problem of refuting random k-XOR via Feige’s XOR trick [Uriel Feige, 2002], and yield a polynomially worse bound of Õ(n^{3/4}) on the clique number when p = O(1). Our algorithm bypasses the XOR trick and relies instead on a natural generalization of the Lovász theta semidefinite programming relaxation for cliques in hypergraphs.
Cite as

Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 42:1-42:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2022.42,
  author =	{Guruswami, Venkatesan and Kothari, Pravesh K. and Manohar, Peter},
  title =	{{Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{42:1--42:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.42},
  URN =		{urn:nbn:de:0030-drops-171642},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.42},
  annote =	{Keywords: Planted clique, Average-case complexity, Spectral refutation, Random matrix theory}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.7
𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices

Authors: Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Random subspaces X of ℝⁿ of dimension proportional to n are, with high probability, well-spread with respect to the 𝓁₂-norm. Namely, every nonzero x ∈ X is "robustly non-sparse" in the following sense: x is ε ‖x‖₂-far in 𝓁₂-distance from all δ n-sparse vectors, for positive constants ε, δ bounded away from 0. This "𝓁₂-spread" property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and corresponds to X being a Euclidean section of the 𝓁₁ unit ball. Explicit 𝓁₂-spread subspaces of dimension Ω(n), however, are unknown, and the best known explicit constructions (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. We prove that with high probability such subspaces contain vectors x that are o(1)⋅‖x‖₂-close to o(n)-sparse with respect to the 𝓁₂-norm, and in particular are not 𝓁₂-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 𝓁_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 𝓁_p norm, and in fact this follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the 𝓁₁ norm [Berinde et al., 2008]. Instantiating this with suitable explicit expanders, we obtain the first explicit constructions of 𝓁_p-RIP matrices for 1 ≤ p < p₀, where 1 < p₀ < 2 is an absolute constant.
Cite as

Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff. 𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.CCC.2022.7,
  author =	{Guruswami, Venkatesan and Manohar, Peter and Mosheiff, Jonathan},
  title =	{{𝓁\underlinep-Spread and Restricted Isometry Properties of Sparse Random Matrices}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.7},
  URN =		{urn:nbn:de:0030-drops-165695},
  doi =		{10.4230/LIPIcs.CCC.2022.7},
  annote =	{Keywords: Spread Subspaces, Euclidean Sections, Restricted Isometry Property, Sparse Matrices}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.23
A Stress-Free Sum-Of-Squares Lower Bound for Coloring

Authors: Pravesh K. Kothari and Peter Manohar

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
We prove that with high probability over the choice of a random graph G from the Erdős-Rényi distribution G(n, 1/2), a natural n^{O(ε² log n)}-time, degree O(ε² log n) sum-of-squares semidefinite program cannot refute the existence of a valid k-coloring of G for k = n^{1/2 + ε}. 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 sum-of-squares strengthening, and this is tight up to a n^{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 instance-preserving non-pointwise 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 [Boaz Barak et al., 2016; S. B. {Hopkins} et al., 2017; Dmitriy Kunisky and Afonso S. Bandeira, 2019; Mrinalkanti Ghosh et al., 2020; Mohanty et al., 2020]. 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.
Cite as

Pravesh K. Kothari and Peter Manohar. A Stress-Free Sum-Of-Squares Lower Bound for Coloring. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kothari_et_al:LIPIcs.CCC.2021.23,
  author =	{Kothari, Pravesh K. and Manohar, Peter},
  title =	{{A Stress-Free Sum-Of-Squares Lower Bound for Coloring}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.23},
  URN =		{urn:nbn:de:0030-drops-142978},
  doi =		{10.4230/LIPIcs.CCC.2021.23},
  annote =	{Keywords: Sum-of-Squares, Graph Coloring, Independent Set, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.26
On Local Testability in the Non-Signaling Setting

Authors: Alessandro Chiesa, Peter Manohar, and Igor Shinkar

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Non-signaling 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 local-to-global phenomena for non-signaling functions. We prove that low-degree testing in the non-signaling setting is possible, assuming that the locality of the non-signaling 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 non-signaling function which passes the test with probability 1 and yet is maximally far from being low-degree. Along the way, we present general results about the local testability of linear codes in the non-signaling setting. These include formulating natural definitions that capture the condition that a non-signaling 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 non-signaling functions that is complete and sound.
Cite as

Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Local Testability in the Non-Signaling Setting. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 26:1-26:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chiesa_et_al:LIPIcs.ITCS.2020.26,
  author =	{Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor},
  title =	{{On Local Testability in the Non-Signaling Setting}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{26:1--26:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.26},
  URN =		{urn:nbn:de:0030-drops-117112},
  doi =		{10.4230/LIPIcs.ITCS.2020.26},
  annote =	{Keywords: non-signaling strategies, locally testable codes, low-degree testing, Fourier analysis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.25
Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing

Authors: Alessandro Chiesa, Peter Manohar, and Igor Shinkar

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Non-signaling 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 non-signaling strategies. In this paper we prove that the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies. Our result offers a new length-vs-query tradeoff when compared to the non-signaling PCP of Kalai, Raz, and Rothblum (STOC 2013 and 2014) and, moreover, may serve as an intermediate step to a proof of a non-signaling analogue of the PCP Theorem.
Cite as

Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chiesa_et_al:LIPIcs.ITCS.2019.25,
  author =	{Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor},
  title =	{{Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.25},
  URN =		{urn:nbn:de:0030-drops-101188},
  doi =		{10.4230/LIPIcs.ITCS.2019.25},
  annote =	{Keywords: probabilistically checkable proofs, linearity testing, non-signaling strategies}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.17
Testing Linearity against Non-Signaling Strategies

Authors: Alessandro Chiesa, Peter Manohar, and Igor Shinkar

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography. We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any non-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions. Quasi-distributions 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 non-negative probabilities). Quasi-distributions arise naturally in the study of Quantum Mechanics as a tool to describe various non-local phenomena. Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish general equivalences between non-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of Property Testing against non-signaling strategies beyond linearity testing.
Cite as

Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Testing Linearity against Non-Signaling Strategies. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 17:1-17:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chiesa_et_al:LIPIcs.CCC.2018.17,
  author =	{Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor},
  title =	{{Testing Linearity against Non-Signaling Strategies}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{17:1--17:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.17},
  URN =		{urn:nbn:de:0030-drops-88731},
  doi =		{10.4230/LIPIcs.CCC.2018.17},
  annote =	{Keywords: property testing, linearity testing, non-signaling strategies, quasi-distributions}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.39
On Axis-Parallel Tests for Tensor Product Codes

Authors: Alessandro Chiesa, Peter Manohar, and Igor Shinkar

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests. In this paper we study tests that only consider restrictions along axis-parallel hyperplanes, which have been studied by Polishchuk and Spielman (1994) and Ben-Sasson and Sudan (2006). While such tests are necessarily "weaker", they work for a more general class of codes, namely tensor product codes. Moreover, axis-parallel tests play a key role in constructing LTCs with inverse polylogarithmic rate and short PCPs (Polishchuk, Spielman 1994; Ben-Sasson, Sudan 2008; Meir 2010). We present two results on axis-parallel tests. (1) Bivariate low-degree testing with low-agreement. We prove an analogue of the Bivariate Low-Degree Testing Theorem of Polishchuk and Spielman in the low-agreement regime, albeit with much larger field size. Namely, for the 2-wise tensor product of the Reed-Solomon code, we prove that for sufficiently large fields, the 2-query variant of the axis-parallel line test (row-vs-column test) works for arbitrarily small agreement. Prior analyses of axis-parallel tests assumed high agreement, and no results for such tests in the low-agreement regime were known. Our proof technique deviates significantly from that of Polishchuk and Spielman, which relies on algebraic methods such as Bezout's Theorem, and instead leverages a fundamental result in extremal graph theory by Kovari, Sos, and Turan. To our knowledge, this is the first time this result is used in the context of low-degree testing. (2) Improved robustness for tensor product codes. Robustness is a strengthening of local testability that underlies many applications. We prove that the axis-parallel hyperplane test for the m-wise 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.
Cite as

Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Axis-Parallel Tests for Tensor Product Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 39:1-39:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chiesa_et_al:LIPIcs.APPROX-RANDOM.2017.39,
  author =	{Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor},
  title =	{{On Axis-Parallel Tests for Tensor Product Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{39:1--39:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.39},
  URN =		{urn:nbn:de:0030-drops-75882},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.39},
  annote =	{Keywords: tensor product codes, locally testable codes, low-degree testing, extremal graph theory}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact