Search Results

Documents authored by Natarajan, Raja

Found 7 Possible Name Variants:

Natarajan, Sivaramakrishnan R.

Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.275
Knapsack Cover Subject to a Matroid Constraint

Authors: Venkatesan T. Chakaravarthy, Anamitra Roy Choudhury, Sivaramakrishnan R. Natarajan, and Sambuddha Roy

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
We consider the Knapsack Covering problem subject to a matroid constraint. In this problem, we are given an universe U of n items where item i has attributes: a cost c(i) and a size s(i). We also have a demand D. We are also given a matroid M = (U, I) on the set U. A feasible solution S to the problem is one such that (i) the cumulative size of the items chosen is at least D, and (ii) the set S is independent in the matroid M (i.e. S is in I). The objective is to minimize the total cost of the items selected, sum_{i in S}c(i). Our main result proves a 2-factor approximation for this problem. The problem described above falls in the realm of mixed packing covering problems. We also consider packing extensions of certain other covering problems and prove that in such cases it is not possible to derive any constant factor pproximations.
Cite as

Venkatesan T. Chakaravarthy, Anamitra Roy Choudhury, Sivaramakrishnan R. Natarajan, and Sambuddha Roy. Knapsack Cover Subject to a Matroid Constraint. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 275-286, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2013.275,
  author =	{Chakaravarthy, Venkatesan T. and Choudhury, Anamitra Roy and Natarajan, Sivaramakrishnan R. and Roy, Sambuddha},
  title =	{{Knapsack Cover Subject to a Matroid Constraint}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{275--286},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.275},
  URN =		{urn:nbn:de:0030-drops-43795},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.275},
  annote =	{Keywords: Approximation Algorithms, LP rounding, Matroid Constraints, Knapsack problems}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.236
Density Functions subject to a Co-Matroid Constraint

Authors: Venkatesan T. Chakaravarthy, Natwar Modani, Sivaramakrishnan R. Natarajan, Sambuddha Roy, and Yogish Sabharwal

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
In this paper we consider the problem of finding the densest subset subject to co-matroid constraints. We are given a monotone supermodular set function f defined over a universe U, and the density of a subset S is defined to be f(S)/|S|. This generalizes the concept of graph density. Co-matroid constraints are the following: given matroid M a set S is feasible, iff the complement of S is independent in the matroid. Under such constraints, the problem becomes NP-hard. The specific case of graph density has been considered in literature under specific co-matroid constraints, for example, the cardinality matroid and the partition matroid. We show a 2-approximation for finding the densest subset subject to co-matroid constraints. Thereby we improve the approximation guarantees for the result for partition matroids in the literature.
Cite as

Venkatesan T. Chakaravarthy, Natwar Modani, Sivaramakrishnan R. Natarajan, Sambuddha Roy, and Yogish Sabharwal. Density Functions subject to a Co-Matroid Constraint. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 236-248, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2012.236,
  author =	{Chakaravarthy, Venkatesan T. and Modani, Natwar and Natarajan, Sivaramakrishnan R. and Roy, Sambuddha and Sabharwal, Yogish},
  title =	{{Density Functions subject to a Co-Matroid Constraint}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{236--248},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.236},
  URN =		{urn:nbn:de:0030-drops-38627},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.236},
  annote =	{Keywords: Approximation Algorithms, Submodular Functions, Graph Density}
}

Natarajan, Raja

Document
DOI: 10.4230/LIPIcs.ITP.2021.28
Verified Double Sided Auctions for Financial Markets

Authors: Raja Natarajan, Suneel Sarswat, and Abhishek Kr Singh

Published in: LIPIcs, Volume 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)

Abstract
Double sided auctions are widely used in financial markets to match demand and supply. Prior works on double sided auctions have focused primarily on single quantity trade requests. We extend various notions of double sided auctions to incorporate multiple quantity trade requests and provide fully formalized matching algorithms for double sided auctions with their correctness proofs. We establish new uniqueness theorems that enable automatic detection of violations in an exchange program by comparing its output with that of a verified program. All proofs are formalized in the Coq proof assistant without adding any axiom to the system. We extract verified OCaml and Haskell programs that can be used by the exchanges and the regulators of the financial markets. We demonstrate the practical applicability of our work by running the verified program on real market data from an exchange to automatically check for violations in the exchange algorithm.
Cite as

Raja Natarajan, Suneel Sarswat, and Abhishek Kr Singh. Verified Double Sided Auctions for Financial Markets. In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{natarajan_et_al:LIPIcs.ITP.2021.28,
  author =	{Natarajan, Raja and Sarswat, Suneel and Singh, Abhishek Kr},
  title =	{{Verified Double Sided Auctions for Financial Markets}},
  booktitle =	{12th International Conference on Interactive Theorem Proving (ITP 2021)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-188-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{193},
  editor =	{Cohen, Liron and Kaliszyk, Cezary},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.28},
  URN =		{urn:nbn:de:0030-drops-139230},
  doi =		{10.4230/LIPIcs.ITP.2021.28},
  annote =	{Keywords: Double Sided Auction, Formal Verification, Financial Markets, Proof Assistant}
}

Natarajan, Vijay

Document
DOI: 10.4230/DagRep.13.5.71
Topological Data Analysis and Applications (Dagstuhl Seminar 23192)

Authors: Ulrich Bauer, Vijay Natarajan, and Bei Wang

Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23192 "Topological Data Analysis and Applications". The seminar brought together researchers with backgrounds in mathematics, computer science, and different application domains with the aim of identifying and exploring emerging directions within computational topology for data analysis. This seminar was designed to be a followup event to two successful Dagstuhl Seminars (17292, July 2017; 19212, May 2019). The list of topics and participants were updated to reflect recent developments and to engage wider participation. Close interaction between the participants during the seminar accelerated the convergence between mathematical and computational thinking in the development of theories and scalable algorithms for data analysis, and the identification of different applications of topological analysis.
Cite as

Ulrich Bauer, Vijay Natarajan, and Bei Wang. Topological Data Analysis and Applications (Dagstuhl Seminar 23192). In Dagstuhl Reports, Volume 13, Issue 5, pp. 71-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{bauer_et_al:DagRep.13.5.71,
  author =	{Bauer, Ulrich and Natarajan, Vijay and Wang, Bei},
  title =	{{Topological Data Analysis and Applications (Dagstuhl Seminar 23192)}},
  pages =	{71--95},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{5},
  editor =	{Bauer, Ulrich and Natarajan, Vijay and Wang, Bei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.5.71},
  URN =		{urn:nbn:de:0030-drops-193652},
  doi =		{10.4230/DagRep.13.5.71},
  annote =	{Keywords: algorithms, applications, computational topology, topological data analysis, visualization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.17
Parallel Computation of Alpha Complexes for Biomolecules

Authors: Talha Bin Masood, Tathagata Ray, and Vijay Natarajan

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
The alpha complex, a subset of the Delaunay triangulation, has been extensively used as the underlying representation for biomolecular structures. We propose a GPU-based parallel algorithm for the computation of the alpha complex, which exploits the knowledge of typical spatial distribution and sizes of atoms in a biomolecule. Unlike existing methods, this algorithm does not require prior construction of the Delaunay triangulation. The algorithm computes the alpha complex in two stages. The first stage proceeds in a bottom-up fashion and computes a superset of the edges, triangles, and tetrahedra belonging to the alpha complex. The false positives from this estimation stage are removed in a subsequent pruning stage to obtain the correct alpha complex. Computational experiments on several biomolecules demonstrate the superior performance of the algorithm, up to a factor of 50 when compared to existing methods that are optimized for biomolecules.
Cite as

Talha Bin Masood, Tathagata Ray, and Vijay Natarajan. Parallel Computation of Alpha Complexes for Biomolecules. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{masood_et_al:LIPIcs.SoCG.2020.17,
  author =	{Masood, Talha Bin and Ray, Tathagata and Natarajan, Vijay},
  title =	{{Parallel Computation of Alpha Complexes for Biomolecules}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.17},
  URN =		{urn:nbn:de:0030-drops-121758},
  doi =		{10.4230/LIPIcs.SoCG.2020.17},
  annote =	{Keywords: Delaunay triangulation, parallel algorithms, biomolecules, GPU}
}
Document
DOI: 10.4230/DagRep.9.5.110
Topology, Computation and Data Analysis (Dagstuhl Seminar 19212)

Authors: Michael Kerber, Vijay Natarajan, and Bei Wang

Published in: Dagstuhl Reports, Volume 9, Issue 5 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19212 "Topology, Computation and Data Analysis". The seminar brought together researchers with mathematical and computational backgrounds in addressing emerging directions within computational topology for data analysis in practice. This seminar was designed to be a followup event after a very successful Dagstuhl Seminar (17292; July 2017). The list of topics and participants were updated to keep the discussions diverse, refreshing, and engaging. This seminar facilitated close interactions among the attendees with the aim of accelerating the convergence between mathematical and computational thinking in the development of theories and scalable algorithms for data analysis.
Cite as

Michael Kerber, Vijay Natarajan, and Bei Wang. Topology, Computation and Data Analysis (Dagstuhl Seminar 19212). In Dagstuhl Reports, Volume 9, Issue 5, pp. 110-131, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{kerber_et_al:DagRep.9.5.110,
  author =	{Kerber, Michael and Natarajan, Vijay and Wang, Bei},
  title =	{{Topology, Computation and Data Analysis (Dagstuhl Seminar 19212)}},
  pages =	{110--131},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{5},
  editor =	{Kerber, Michael and Natarajan, Vijay and Wang, Bei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.5.110},
  URN =		{urn:nbn:de:0030-drops-113832},
  doi =		{10.4230/DagRep.9.5.110},
  annote =	{Keywords: computational topology, topological data analysis, Topology based visualization}
}

Natarajan, Sriraam

Document
DOI: 10.4230/DagSemProc.07161.3
Exploiting prior knowledge in Intelligent Assistants - Combining relational models with hierarchies

Authors: Sriraam Natarajan, Prasad Tadepalli, and Alan Fern

Published in: Dagstuhl Seminar Proceedings, Volume 7161, Probabilistic, Logical and Relational Learning - A Further Synthesis (2008)

Abstract
Statitsical relational models have been successfully used to model static probabilistic relationships between the entities of the domain. In this talk, we illustrate their use in a dynamic decison-theoretic setting where the task is to assist a user by inferring his intentional structure and taking appropriate assistive actions. We show that the statistical relational models can be used to succintly express the system's prior knowledge about the user's goal-subgoal structure and tune it with experience. As the system is better able to predict the user's goals, it improves the effectiveness of its assistance. We show through experiments that both the hierarchical structure of the goals and the parameter sharing facilitated by relational models significantly improve the learning speed.
Cite as

Sriraam Natarajan, Prasad Tadepalli, and Alan Fern. Exploiting prior knowledge in Intelligent Assistants - Combining relational models with hierarchies. In Probabilistic, Logical and Relational Learning - A Further Synthesis. Dagstuhl Seminar Proceedings, Volume 7161, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{natarajan_et_al:DagSemProc.07161.3,
  author =	{Natarajan, Sriraam and Tadepalli, Prasad and Fern, Alan},
  title =	{{Exploiting prior knowledge in Intelligent Assistants - Combining relational models with hierarchies}},
  booktitle =	{Probabilistic, Logical and Relational Learning - A Further Synthesis},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7161},
  editor =	{Luc de Raedt and Thomas Dietterich and Lise Getoor and Kristian Kersting and Stephen H. Muggleton},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07161.3},
  URN =		{urn:nbn:de:0030-drops-13856},
  doi =		{10.4230/DagSemProc.07161.3},
  annote =	{Keywords: Statistical Relational Learning, Intelligent Assistants}
}

Natarajan, Abhiram

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.371
Computational Complexity of Certifying Restricted Isometry Property

Authors: Abhiram Natarajan and Yi Wu

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

Abstract
Given a matrix A with n rows, a number k < n, and 0 < delta < 1, A is (k,delta)-RIP (Restricted Isometry Property) if, for any vector x in R^n, with at most k non-zero co-ordinates, (1-delta)|x|^2 <= |Ax|^2 <= (1+delta)|Ax|^2. In many applications, such as compressed sensing and sparse recovery, it is desirable to construct RIP matrices with a large k and a small delta;. Given the efficacy of random constructions in generating useful RIP matrices, the problem of certifying the RIP parameters of a matrix has become important. In this paper, we prove that it is hard to approximate the RIP parameters of a matrix assuming the Small-Set-Expansion-Hypothesis. Specifically, we prove that for any arbitrarily large constant C>0 and any arbitrarily small constant 0<delta<1, there exists some k such that given a matrix M, it is SSE-Hard to distinguish the following two cases: i) (Highly RIP) M is (k,delta)-RIP; ii) (Far away from RIP) M is not (k/C,1-delta)-RIP. Most of the previous results on the topic of hardness of RIP certification only hold for certification when delta=o(1). In practice, it is of interest to understand the complexity of certifying a matrix with delta being close to sqrt(2) - 1, as it suffices for many real applications to have matrices with delta=sqrt(2)-1. Our hardness result holds for any constant delta. Specifically, our result proves that even if delta is indeed very small, i.e. the matrix is in fact strongly RIP, certifying that the matrix exhibits weak RIP itself is SSE-Hard. In order to prove the hardness result, we prove a variant of the Cheeger's Inequality for sparse vectors.
Cite as

Abhiram Natarajan and Yi Wu. Computational Complexity of Certifying Restricted Isometry Property. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 371-380, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{natarajan_et_al:LIPIcs.APPROX-RANDOM.2014.371,
  author =	{Natarajan, Abhiram and Wu, Yi},
  title =	{{Computational Complexity of Certifying Restricted Isometry Property}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{371--380},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.371},
  URN =		{urn:nbn:de:0030-drops-47092},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.371},
  annote =	{Keywords: Restricted Isometry Property, RIP, RIP Certification, Sparse Cheeger Inequality, SSE Hard}
}

Natarajan, Anand V.

Document
DOI: 10.4230/LIPIcs.CCC.2016.22
Tight SoS-Degree Bounds for Approximate Nash Equilibria

Authors: Aram Harrow, Anand V. Natarajan, and Xiaodi Wu

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
Nash equilibria always exist, but are widely conjectured to require time to find that is exponential in the number of strategies, even for two-player games. By contrast, a simple quasi-polynomial time algorithm, due to Lipton, Markakis and Mehta (LMM), can find approximate Nash equilibria, in which no player can improve their utility by more than epsilon by changing their strategy. The LMM algorithm can also be used to find an approximate Nash equilibrium with near-maximal total welfare. Matching hardness results for this optimization problem re found assuming the hardness of the planted-clique problem (by Hazan and Krauthgamer) and assuming the Exponential Time Hypothesis (by Braverman, Ko and Weinstein). In this paper we consider the application of the sum-squares (SoS) algorithm from convex optimization to the problem of optimizing over Nash equilibria. We show the first unconditional lower bounds on the number of levels of SoS needed to achieve a constant factor approximation to this problem. While it may seem that Nash equilibria do not naturally lend themselves to convex optimization, we also describe a simple LP (linear programming) hierarchy that can find an approximate Nash equilibrium in time comparable to that of the LMM algorithm, although neither algorithm is obviously a generalization of the other. This LP can be viewed as arising from the SoS algorithm at log(n) levels - matching our lower bounds. The lower bounds involve a modification of the Braverman-Ko-Weinstein embedding of CSPs into strategic games and techniques from sum-of-squares proof systems. The upper bound (i.e. analysis of the LP) uses information-theory techniques that have been recently applied to other linear- and semidefinite-programming hierarchies.
Cite as

Aram Harrow, Anand V. Natarajan, and Xiaodi Wu. Tight SoS-Degree Bounds for Approximate Nash Equilibria. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 22:1-22:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{harrow_et_al:LIPIcs.CCC.2016.22,
  author =	{Harrow, Aram and Natarajan, Anand V. and Wu, Xiaodi},
  title =	{{Tight SoS-Degree Bounds for Approximate Nash Equilibria}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{22:1--22:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.22},
  URN =		{urn:nbn:de:0030-drops-58565},
  doi =		{10.4230/LIPIcs.CCC.2016.22},
  annote =	{Keywords: Approximate Nash Equilibrium, Sum of Squares, LP, SDP}
}

Natarajan, Anand

Document
DOI: 10.4230/LIPIcs.CCC.2024.30
The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise

Authors: Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, and Penghui Yao

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
The class MIP^* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP [Babai et al., 1991; Zhengfeng Ji et al., 2020; Zhengfeng Ji et al., 2020]: while MIP = NEXP, the quantum class MIP^* is equal to RE, a class including the halting problem. This is because the provers in MIP^* can share unbounded quantum entanglement. However, recent works [Qin and Yao, 2021; Qin and Yao, 2023] have shown that this advantage is significantly reduced if the provers' shared state contains noise. This paper attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP^*[poly,O(1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) [Qin and Yao, 2021]. We also show that this collapse in power is due to the noise, rather than the O(1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP^*[poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fréchet derivatives or which are Lipschitz continuous.
Cite as

Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, and Penghui Yao. The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 30:1-30:71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dong_et_al:LIPIcs.CCC.2024.30,
  author =	{Dong, Yangjing and Fu, Honghao and Natarajan, Anand and Qin, Minglong and Xu, Haochen and Yao, Penghui},
  title =	{{The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{30:1--30:71},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.30},
  URN =		{urn:nbn:de:0030-drops-204263},
  doi =		{10.4230/LIPIcs.CCC.2024.30},
  annote =	{Keywords: Interactive proofs, Quantum complexity theory, Quantum entanglement, Fourier analysis, Matrix analysis, Invariance principle, Derandomization, PCP, Locally testable code, Positivity testing}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.22
A Distribution Testing Oracle Separating QMA and QCMA

Authors: Anand Natarajan and Chinmay Nirkhe

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
It is a long-standing open question in quantum complexity theory whether the definition of non-deterministic quantum computation requires quantum witnesses (QMA) or if classical witnesses suffice (QCMA). We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes. Previous separations [Aaronson and Kuperberg, 2007; Bill Fefferman and Shelby Kimmel, 2018] required a quantum unitary oracle. The separating problem is deciding whether a distribution supported on regular un-directed graphs either consists of multiple connected components (yes instances) or consists of one expanding connected component (no instances) where the graph is given in an adjacency-list format by the oracle. Therefore, the oracle is a distribution over n-bit boolean functions.
Cite as

Anand Natarajan and Chinmay Nirkhe. A Distribution Testing Oracle Separating QMA and QCMA. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 22:1-22:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{natarajan_et_al:LIPIcs.CCC.2023.22,
  author =	{Natarajan, Anand and Nirkhe, Chinmay},
  title =	{{A Distribution Testing Oracle Separating QMA and QCMA}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{22:1--22:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.22},
  URN =		{urn:nbn:de:0030-drops-182928},
  doi =		{10.4230/LIPIcs.CCC.2023.22},
  annote =	{Keywords: quantum non-determinism, complexity theory}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.5
Quantum Search-To-Decision Reductions and the State Synthesis Problem

Authors: Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen

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

Abstract
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the de facto computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for QMA, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a QMA problem up to inverse polynomial precision by making one query to a PP decision oracle. We complement this result by showing that QMA-search does not reduce to QMA-decision in polynomial-time, relative to a quantum oracle. We also explore the more general state synthesis problem, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson [Aaronson, 2016], who presented a state synthesis algorithm that makes O(n) queries to a classical oracle to prepare an n-qubit state, and asked if the query complexity could be made sublinear.
Cite as

Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum Search-To-Decision Reductions and the State Synthesis Problem. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{irani_et_al:LIPIcs.CCC.2022.5,
  author =	{Irani, Sandy and Natarajan, Anand and Nirkhe, Chinmay and Rao, Sujit and Yuen, Henry},
  title =	{{Quantum Search-To-Decision Reductions and the State Synthesis Problem}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{5:1--5:19},
  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.5},
  URN =		{urn:nbn:de:0030-drops-165674},
  doi =		{10.4230/LIPIcs.CCC.2022.5},
  annote =	{Keywords: Search-to-decision, state synthesis, quantum computing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.10
Algorithms, Bounds, and Strategies for Entangled XOR Games

Authors: Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, and Anand Natarajan

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

Abstract
Entangled games are a quantum analog of constraint satisfaction problems and have had important applications to quantum complexity theory, quantum cryptography, and the foundations of quantum mechanics. Given a game, the basic computational problem is to compute its entangled value: the supremum success probability attainable by a quantum strategy. We study the complexity of computing the (commuting-operator) entangled value omega^* of entangled XOR games with any number of players. Based on a duality theory for systems of operator equations, we introduce necessary and sufficient criteria for an XOR game to have omega^* = 1, and use these criteria to derive the following results: 1) An algorithm for symmetric games that decides in polynomial time whether omega^* = 1 or omega^* < 1, a task that was not previously known to be decidable, together with a simple tensor-product strategy that achieves value 1 in the former case. The only previous candidate algorithm for this problem was the Navascués-Pironio-Acín (also known as noncommutative Sum of Squares or ncSoS) hierarchy, but no convergence bounds were known. 2) A family of games with three players and with omega^* < 1, where it takes doubly exponential time for the ncSoS algorithm to witness this. By contrast, our algorithm runs in polynomial time. 3) Existence of an unsatisfiable phase for random (non-symmetric) XOR games. We show that there exists a constant C_k^{unsat} depending only on the number k of players, such that a random k-XOR game over an alphabet of size n has omega^* < 1 with high probability when the number of clauses is above C_k^{unsat} n. 4) A lower bound of Omega(n log(n)/log log(n)) on the number of levels in the ncSoS hierarchy required to detect unsatisfiability for most random 3-XOR games. This is in contrast with the classical case where the (3n)^{th} level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.
Cite as

Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, and Anand Natarajan. Algorithms, Bounds, and Strategies for Entangled XOR Games. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{benewatts_et_al:LIPIcs.ITCS.2019.10,
  author =	{Bene Watts, Adam and Harrow, Aram W. and Kanwar, Gurtej and Natarajan, Anand},
  title =	{{Algorithms, Bounds, and Strategies for Entangled XOR Games}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{10:1--10:18},
  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.10},
  URN =		{urn:nbn:de:0030-drops-101032},
  doi =		{10.4230/LIPIcs.ITCS.2019.10},
  annote =	{Keywords: Nonlocal games, XOR Games, Pseudotelepathy games, Multipartite entanglement}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.20
Retracted: Two-Player Entangled Games are NP-Hard

Authors: Anand Natarajan and Thomas Vidick

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

Abstract
The article, published on June 4th, 2018 in the CCC 2018 proceedings, has been retracted by agreement between the authors, the editor(s), and the publisher Schloss Dagstuhl / LIPIcs. The retraction has been agreed due to an error in the proof of the main result. This error is carried over from an error in the referenced paper “Three-player entangled XOR games are NP-hard to approximate” by Thomas Vidick (SICOMP ’16). That paper was used in an essential way to obtain the present result, and the error cannot be addressed through an erratum. See Retraction Notice on the last page of the PDF. We show that it is NP-hard to approximate, to within an additive constant, the maximum success probability of players sharing quantum entanglement in a two-player game with classical questions of logarithmic length and classical answers of constant length. As a corollary, the inclusion NEXP subseteq MIP^*, first shown by Ito and Vidick (FOCS'12) with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test of Raz and Safra (STOC'97) against two entangled provers.
Cite as

Anand Natarajan and Thomas Vidick. Retracted: Two-Player Entangled Games are NP-Hard. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{natarajan_et_al:LIPIcs.CCC.2018.20,
  author =	{Natarajan, Anand and Vidick, Thomas},
  title =	{{Retracted: Two-Player Entangled Games are NP-Hard}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{20:1--20:18},
  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.20},
  URN =		{urn:nbn:de:0030-drops-88696},
  doi =		{10.4230/LIPIcs.CCC.2018.20},
  annote =	{Keywords: low-degree testing, entangled nonlocal games, multi-prover interactive proof systems}
}
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 About DROPS Imprint Privacy Contact