5 Search Results for "Nadimpalli, Shivam"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.33
Testing Intersecting and Union-Closed Families

Authors: Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, specifically intersecting families and union-closed families. A function f: {0,1}ⁿ → {0,1} is intersecting (respectively, union-closed) if its set of satisfying assignments corresponds to an intersecting family (respectively, a union-closed family) of subsets of [n]. Our main results are that - in sharp contrast with the property of being a monotone set system - the property of being an intersecting set system, and the property of being a union-closed set system, both turn out to be information-theoretically difficult to test. We show that: - For ε ≥ Ω(1/√n), any non-adaptive two-sided ε-tester for intersectingness must make 2^{Ω(n^{1/4}/√{ε})} queries. We also give a 2^{Ω(√{n log(1/ε)})}-query lower bound for non-adaptive one-sided ε-testers for intersectingness. - For ε ≥ 1/2^{Ω(n^{0.49})}, any non-adaptive two-sided ε-tester for union-closedness must make n^{Ω(log(1/ε))} queries. Thus, neither intersectingness nor union-closedness shares the poly(n,1/ε)-query non-adaptive testability that is enjoyed by monotonicity. To complement our lower bounds, we also give a simple poly(n^{√{nlog(1/ε)}},1/ε)-query, one-sided, non-adaptive algorithm for ε-testing each of these properties (intersectingness and union-closedness). We thus achieve nearly tight upper and lower bounds for two-sided testing of intersectingness when ε = Θ(1/√n), and for one-sided testing of intersectingness when ε = Θ(1).
Cite as

Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio. Testing Intersecting and Union-Closed Families. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 33:1-33:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2024.33,
  author =	{Chen, Xi and De, Anindya and Li, Yuhao and Nadimpalli, Shivam and Servedio, Rocco A.},
  title =	{{Testing Intersecting and Union-Closed Families}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{33:1--33:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.33},
  URN =		{urn:nbn:de:0030-drops-195610},
  doi =		{10.4230/LIPIcs.ITCS.2024.33},
  annote =	{Keywords: Sublinear algorithms, property testing, computational complexity, monotonicity, intersecting families, union-closed families}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.96
Unitary Property Testing Lower Bounds by Polynomials

Authors: Adrian She and Henry Yuen

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether it satisfies some property. In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum" problems that have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. Our main contribution is a generalized polynomial method for unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a marked subspace, and approximating the entanglement entropy of a marked state. We also present a unitary property testing-based approach towards an oracle separation between QMA and QMA(2), a long standing question in quantum complexity theory.
Cite as

Adrian She and Henry Yuen. Unitary Property Testing Lower Bounds by Polynomials. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 96:1-96:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{she_et_al:LIPIcs.ITCS.2023.96,
  author =	{She, Adrian and Yuen, Henry},
  title =	{{Unitary Property Testing Lower Bounds by Polynomials}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{96:1--96:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.96},
  URN =		{urn:nbn:de:0030-drops-175995},
  doi =		{10.4230/LIPIcs.ITCS.2023.96},
  annote =	{Keywords: Quantum query complexity, polynomial method, unitary property testing, quantum proofs, invariant theory, quantum recurrence time, entanglement entropy, BQP, QMA, QMA(2)}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.53
Convex Influences

Authors: Anindya De, Shivam Nadimpalli, and Rocco A. Servedio

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We introduce a new notion of influence for symmetric convex sets over Gaussian space, which we term "convex influence". We show that this new notion of influence shares many of the familiar properties of influences of variables for monotone Boolean functions f: {±1}ⁿ → {±1}. Our main results for convex influences give Gaussian space analogues of many important results on influences for monotone Boolean functions. These include (robust) characterizations of extremal functions, the Poincaré inequality, the Kahn-Kalai-Linial theorem [J. Kahn et al., 1988], a sharp threshold theorem of Kalai [G. Kalai, 2004], a stability version of the Kruskal-Katona theorem due to O'Donnell and Wimmer [R. O'Donnell and K. Wimmer, 2009], and some partial results towards a Gaussian space analogue of Friedgut’s junta theorem [E. Friedgut, 1998]. The proofs of our results for convex influences use very different techniques than the analogous proofs for Boolean influences over {±1}ⁿ. Taken as a whole, our results extend the emerging analogy between symmetric convex sets in Gaussian space and monotone Boolean functions from {±1}ⁿ to {±1}.
Cite as

Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Convex Influences. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.ITCS.2022.53,
  author =	{De, Anindya and Nadimpalli, Shivam and Servedio, Rocco A.},
  title =	{{Convex Influences}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{53:1--53:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.53},
  URN =		{urn:nbn:de:0030-drops-156498},
  doi =		{10.4230/LIPIcs.ITCS.2022.53},
  annote =	{Keywords: Fourier analysis of Boolean functions, convex geometry, influences, threshold phenomena}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.53
Fourier Growth of Structured 𝔽₂-Polynomials and Applications

Authors: Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, and Emanuele Viola

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

Abstract
We analyze the Fourier growth, i.e. the L₁ Fourier weight at level k (denoted L_{1,k}), of various well-studied classes of "structured" m F₂-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [Chattopadhyay et al., 2019; Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2020] which show that upper bounds on Fourier growth (even at level k = 2) give unconditional pseudorandom generators. Our main structural results on Fourier growth are as follows: - We show that any symmetric degree-d m F₂-polynomial p has L_{1,k}(p) ≤ Pr [p = 1] ⋅ O(d)^k. This quadratically strengthens an earlier bound that was implicit in [Omer Reingold et al., 2013]. - We show that any read-Δ degree-d m F₂-polynomial p has L_{1,k}(p) ≤ Pr [p = 1] ⋅ (k Δ d)^{O(k)}. - We establish a composition theorem which gives L_{1,k} bounds on disjoint compositions of functions that are closed under restrictions and admit L_{1,k} bounds. Finally, we apply the above structural results to obtain new unconditional pseudorandom generators and new correlation bounds for various classes of m F₂-polynomials.
Cite as

Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, and Emanuele Viola. Fourier Growth of Structured 𝔽₂-Polynomials and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{blasiok_et_al:LIPIcs.APPROX/RANDOM.2021.53,
  author =	{B{\l}asiok, Jaros{\l}aw and Ivanov, Peter and Jin, Yaonan and Lee, Chin Ho and Servedio, Rocco A. and Viola, Emanuele},
  title =	{{Fourier Growth of Structured \mathbb{F}₂-Polynomials and Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{53:1--53:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.53},
  URN =		{urn:nbn:de:0030-drops-147462},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.53},
  annote =	{Keywords: Fourier analysis, Pseudorandomness, Fourier growth}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.69
Quantitative Correlation Inequalities via Semigroup Interpolation

Authors: Anindya De, Shivam Nadimpalli, and Rocco A. Servedio

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Most correlation inequalities for high-dimensional functions in the literature, such as the Fortuin-Kasteleyn-Ginibre inequality and the celebrated Gaussian Correlation Inequality of Royen, are qualitative statements which establish that any two functions of a certain type have non-negative correlation. We give a general approach that can be used to bootstrap many qualitative correlation inequalities for functions over product spaces into quantitative statements. The approach combines a new extremal result about power series, proved using complex analysis, with harmonic analysis of functions over product spaces. We instantiate this general approach in several different concrete settings to obtain a range of new and near-optimal quantitative correlation inequalities, including: - A {quantitative} version of Royen’s celebrated Gaussian Correlation Inequality [Royen, 2014]. In [Royen, 2014] Royen confirmed a conjecture, open for 40 years, stating that any two symmetric convex sets must be non-negatively correlated under any centered Gaussian distribution. We give a lower bound on the correlation in terms of the vector of degree-2 Hermite coefficients of the two convex sets, conceptually similar to Talagrand’s quantitative correlation bound for monotone Boolean functions over {0,1}ⁿ [M. Talagrand, 1996]. We show that our quantitative version of Royen’s theorem is within a logarithmic factor of being optimal. - A quantitative version of the well-known FKG inequality for monotone functions over any finite product probability space. This is a broad generalization of Talagrand’s quantitative correlation bound for functions from {0,1}ⁿ to {0,1} under the uniform distribution [M. Talagrand, 1996]; the only prior generalization of which we are aware is due to Keller [Nathan Keller, 2012; Keller, 2008; Nathan Keller, 2009], which extended [M. Talagrand, 1996] to product distributions over {0,1}ⁿ. In the special case of p-biased distributions over {0,1}ⁿ that was considered by Keller, our new bound essentially saves a factor of p log(1/p) over the quantitative bounds given in [Nathan Keller, 2012; Keller, 2008; Nathan Keller, 2009]. We also give {a quantitative version of} the FKG inequality for monotone functions over the continuous domain [0,1]ⁿ, answering a question of Keller [Nathan Keller, 2009].
Cite as

Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Quantitative Correlation Inequalities via Semigroup Interpolation. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 69:1-69:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.ITCS.2021.69,
  author =	{De, Anindya and Nadimpalli, Shivam and Servedio, Rocco A.},
  title =	{{Quantitative Correlation Inequalities via Semigroup Interpolation}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{69:1--69:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.69},
  URN =		{urn:nbn:de:0030-drops-136081},
  doi =		{10.4230/LIPIcs.ITCS.2021.69},
  annote =	{Keywords: complex analysis, correlation inequality, FKG inequality, Gaussian correlation inequality, harmonic analysis, Markov semigroups}
}
  • Refine by Author
  • 4 Servedio, Rocco A.
  • 3 De, Anindya
  • 3 Nadimpalli, Shivam
  • 1 Błasiok, Jarosław
  • 1 Chen, Xi
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing
  • 2 Mathematics of computing → Probability and statistics
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Pseudorandomness and derandomization
  • Show More...

  • Refine by Keyword
  • 1 BQP
  • 1 FKG inequality
  • 1 Fourier analysis
  • 1 Fourier analysis of Boolean functions
  • 1 Fourier growth
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2021
  • 1 2022
  • 1 2023
  • 1 2024

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