BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ashutosh Rai

Ashutosh Rai appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phData Structures and AlgorithmsDiscrete MathematicsInformation Theorymath.ITmath.CO

Catalog footprint

What is connected

19works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2026arXiv

Enhancing Sum Capacity via Quantum and No-Signaling Cooperation Between Transmitters

We consider a communication scenario over a discrete memoryless interference channel or multiple access channel without feedback, where transmitters exploit classical, quantum, or no-signaling cooperation. In this scenario, several previous works have shown that the sum capacities of channels involving pseudo-telepathy games can be enhanced by quantum or no-signaling cooperation. However, a full characterization of which channels admit such an improvement remains open. By focusing on the common characteristics of previously studied channels, we propose a broader class of channels for which quantum or no-signaling cooperation increases the sum capacity. Channels in this class are associated with a pseudo-telepathy game, with channel inputs specified as tuples of questions and answers from the game. In addition, when the channel inputs satisfy the winning condition of the game, the channel decomposes into parallel weakly symmetric sub-channels and is less noisy compared to the case when the inputs do not meet the winning condition.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Parameterized and Exact Algorithms for Class Domination Coloring

A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighbourhood of some vertex. The minimum number of colors required for any cd-coloring of $G$, denoted by $χ_{cd}(G)$, is called the class domination chromatic number (cd-chromatic number) of $G$. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph $G$ on $n$ vertices, find its cd-chromatic number. (2) Given a graph $G$ and integers $k$ and $q$, can we delete at most $k$ vertices such that the cd-chromatic number of the resulting graph is at most $q$? For the first problem, we give an exact algorithm with running time $\Oh(2^n n^4 \log n)$. Also, we show that the problem is \FPT\ with respect to the number $q$ of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with $\Oh(q^3)$ vertices. For the second (deletion) problem, we show \NP-hardness for each $q \geq 2$. Further, on split graphs, we show that the problem is \NP-hard if $q$ is a part of the input and \FPT\ with respect to $k$ and $q$ as combined parameters. As recognizing graphs with cd-chromatic number at most $q$ is \NP-hard in general for $q \geq 4$, the deletion problem is unlikely to be \FPT\ when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for $q \in \{2,3\}$ using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Self-testing quantum states via nonmaximal violation in Hardy's test of nonlocality

Self-testing protocols enable certification of quantum devices without demanding full knowledge about their inner workings. A typical approach in designing such protocols is based on observing nonlocal correlations which exhibit maximum violation in a Bell test. We show that in Bell experiment known as Hardy's test of nonlocality not only the maximally nonlocal correlation self-tests a quantum state, rather a non-maximal nonlocal behavior can serve the same purpose. We, in fact, completely characterize all such behaviors leading to self-test of every pure two qubit entangled state except the maximally entangled ones. Apart from originating a novel self-testing protocol, our method provides a powerful tool towards characterizing the complex boundary of the set of quantum correlations.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem

We develop an FPT algorithm and a bi-kernel for the Weighted Edge Clique Partition (WECP) problem, where a graph with $n$ vertices and integer edge weights is given together with an integer $k$, and the aim is to find $k$ cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into $k$ cliques. It was shown that ECP admits a kernel with~$k^2$ vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP has a runtime of $2^{\mathcal{O}(k^2)}n^{O(1)}$ [Issac, 2019]. For WECP we develop a bi-kernel with $4^k$ vertices, and an algorithm with runtime $2^{\mathcal{O}(k^{3/2}w^{1/2}\log(k/w))}n^{O(1)}$, where $w$ is the maximum edge weight. The latter in particular improves the runtime for ECP to~$2^{\mathcal{O}(k^{3/2}\log k)}n^{O(1)}$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities

One of the fundamental results in quantum foundations is the Kochen-Specker no-go theorem. For the quantum theory, the no-go theorem excludes the possibility of a class of hidden variable models where value attribution is context independent. Recently, the notion of contextuality has been generalized for different operational procedures and it has been shown that preparation contextuality of mixed quantum states can be a useful resource in an information-processing task called parity-oblivious multiplexing. Here, we introduce a new class of information processing tasks, namely d-level parity oblivious random access codes and obtain bounds on the success probabilities of performing such tasks in any preparation noncontextual theory. These bounds constitute noncontextuality inequalities for any value of d. For d=3, using a set of mutually asymmetric biased bases we show that the corresponding noncontextual bound is violated by quantum theory. We also show quantum violation of the inequalities for some other higher values of d. This reveals operational usefulness of preparation contextuality of higher level quantum systems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Parameterized Algorithm for Mixed Cut

The classical Menger's theorem states that in any undirected (or directed) graph $G$, given a pair of vertices $s$ and $t$, the maximum number of vertex (edge) disjoint paths is equal to the minimum number of vertices (edges) needed to disconnect from $s$ and $t$. This min-max result can be turned into a polynomial time algorithm to find the maximum number of vertex (edge) disjoint paths as well as the minimum number of vertices (edges) needed to disconnect $s$ from $t$. In this paper we study a mixed version of this problem, called Mixed-Cut, where we are given an undirected graph $G$, vertices $s$ and $t$, positive integers $k$ and $l$ and the objective is to test whether there exist a $k$ sized vertex set $S \subseteq V(G)$ and an $l$ sized edge set $F \subseteq E(G)$ such that deletion of $S$ and $F$ from $G$ disconnects from $s$ and $t$. We start with a small observation that this problem is NP-complete and then study this problem, in fact a much stronger generalization of this, in the realm of parameterized complexity. In particular we study the Mixed-Multiway Cut-Uncut problem where along with a set of terminals $T$, we are also given an equivalence relation $\mathcal{R}$ on $T$, and the question is whether we can delete at most $k$ vertices and at most $l$ edges such that connectivity of the terminals in the resulting graph respects $\mathcal{R}$. Our main results is a fixed parameter algorithm for Mixed-Multiway Cut-Uncut using the method of recursive understanding introduced by Chitnis et al. (FOCS 2012).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound

Kochen-Specker (KS) theorem lies at the heart of the foundations of quantum mechanics. It establishes impossibility of explaining predictions of quantum theory by any noncontextual ontological model. Spekkens generalized the notion of KS contextuality in [Phys. Rev. A 71, 052108 (2005)] for arbitrary experimental procedures (preparation, measurement, and transformation procedure). Interestingly, later on it was shown that preparation contextuality powers parity-oblivious multiplexing [Phys. Rev. Lett. 102, 010401 (2009)], a two party information theoretic game. Thus, using resources of a given operational theory, the maximum success probability achievable in such a game suffices as a \emph{bona-fide} measure of preparation contextuality for the underlying theory. In this work we show that preparation contextuality in quantum theory is more restricted compared to a general operational theory known as \emph{box world}. Moreover, we find that this limitation of quantum theory implies the quantitative bound on quantum nonlocality as depicted by the Cirel'son bound.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A testable prediction of the no-signalling condition using a variant of the EPR-Bohm example

Predictive power of the no-signalling condition (NSC) is demonstrated in a testable situation involving a non-ideal Stern-Gerlach (SG) device in one of the two wings of the EPR-Bohm entangled pairs. In this wing, for two types of measurement in the other wing, we consider the spin state of a selected set of particles that are confined to a particular half of the plane while emerging from the SG magnetic field region. Due to non-idealness of the SG setup, this spin state will have superposing components involving a relative phase for which a testable quantitative constraint is obtained by invoking NSC, thereby providing a means for precision testing of this fundamentally significant principle.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Local Orthogonality provides better upper bound for Hardy's nonlocality

The amount of nonlocality in quantum theory is limited compared to that allowed in generalized no-signaling theory [Found. Phys. 24, 379 (1994)]. This feature, for example, gets manifested in the amount of Bell inequality violation as well as in the degree of success probability of Hardy's (Cabello's) nonlocality argument. Physical principles like information causality and macroscopic locality have been proposed for analyzing restricted nonlocality in quantum mechanics---viz. explaining the Cirel'son bound. However, these principles are not that much successful in explaining the maximum success probability of Hardy's as well as Cabello's argument in quantum theory. Here we show that, a newly proposed physical principle namely Local Orthogonality does better by providing a tighter upper bound on the success probability for Hardy's nonlocality. This bound is relatively closer to the corresponding quantum value compared to the bounds achieved from other principles.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Macroscopic locality with equal bias reproduces with high fidelity a quantum distribution achieving the Tsirelson's bound

Two physical principles, Macroscopic Locality (ML) and Information Causality (IC), so far, have been most successful in distinguishing quantum correlations from post-quantum correlations. However, there are also some post-quantum probability distributions which cannot be distinguished with the help of these principles. Thus, it is interesting to see whether consideration of these two principles, separately, along with some additional physically plausible constraints, can explain some interesting quantum features which are otherwise hard to reproduce. In this paper we show that, in a Bell-CHSH scenario, ML along with constraint of equal-biasness for the concerned observables, almost reproduces the quantum joint probability distribution corresponding to maximal quantum Bell violation, which is unique up to relabeling. From this example and earlier work of Cavalcanti, Salles and Scarani, we conclude that IC and ML are in-equivalent physical principles; satisfying one does not imply that the other is satisfied.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Polynomial Kernels for λ-extendible Properties Parameterized Above the Poljak-Turzík Bound

Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < λ < 1 and λ-extendible property Π, any connected graph G on n vertices and m edges contains a spanning subgraph H in Π with at least λm + (1-λ)(n-1)/2 edges. The property of being bipartite is λ-extendible for λ = 1/2, and so the Poljak-Turzik bound generalizes the well-known Edwards-Erdos bound for Max-Cut. Other examples of λ-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some integer q. Mnich et. al. (FSTTCS 2012) defined the closely related notion of strong λ-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly λ-extendible property Π is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound - does there exist a spanning subgraph H of a connected graph G such that H in Π and H has at least λm + (1-λ)(n-1)/2 + k edges? - subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when λ = 1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Hardy's nonlocality argument as witness for post-quantum correlation

Recently, Gallego et.al. [Phys. Rev. Lett 107, 210403 (2011)] proved that any future information principle aiming at distinguishing between quantum and post-quantum correlation must be intrinsically multipartite in nature. We establish similar result by using device independent success probability of Hardy's nonlocality argument for tripartite quantum system. We construct an example of a tri-partite Hardy correlation which is post-quantum but satisfies not only all bipartite information principle but also the GYNI inequality.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Local simulation of singlet statistics for restricted set of measurement

The essence of Bell's theorem is that, in general, quantum statistics cannot be reproduced by local hidden variable (LHV) model. This impossibility is strongly manifested while analyzing the singlet state statistics for Bell-CHSH violations. In this work, we provide various subsets of two outcome POVMs for which a local hidden variable model can be constructed for singlet state.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Maximum tri-partite Hardy's nonlocality respecting all bi-partite principles

The set of multiparty correlations that respect all bi-partite principles has been conjectured to be same as the set of time-ordered-bi-local correlations. Based on this conjuncture we find the maximum value of success probability of tri-partite Hardy's correlation respecting all bi-partite physical principles. Unlike in quantum mechanics, the no-signaling principle does not reveal any gap in Hardy's maximum success probability for bi-partite and tri-partite system. Information causality principle is shown to be successful in qualitatively revealing this quantum feature and this result is independent of the conjecture mentioned above.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal free-will on one side in reproducing the singlet correlation

Bell's theorem teaches us that there are quantum correlations that can not be simulated by just shared randomness (Local Hidden variable). There are some recent results which simulate singlet correlation by using either 1 cbit or a binary (no-signaling) correlation which violate Bell's inequality maximally. But there is one more possible way to simulate quantum correlation by relaxing the condition of independency of measurement on shared randomness. Recently, MJW Hall showed that the statistics of singlet state can be generated by sacrificing measurement independence where underlying distribution of hidden variables depend on measurement direction of both parties [Phys. Rev. Lett.105 250404 (2010)]. He also proved that for any model of singlet correlation, 86% measurement independence is optimal. In this paper, we show that 59% measurement independence is optimal for simulating singlet correlation when the underlying distribution of hidden variables depend only on measurements of one party. We also show that a distribution corresponding to this optimal lack of free will, already exists in literature which first appeared in the context of detection efficiency loophole.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A complementary relation between classical bits and randomness in local part in simulating singlet state

Recently Leggett's proposal of non-local model generates new interest in simulating the statistics of singlet state. Singlet state statistics can be simulated by 1 bit of classical communication without using any further nonlocal correlation. But, interestingly, singlet state statistics can also be simulated with no classical cost if a non-local box is used. In the first case, the output is completely unbiased whereas in second case outputs are completely random. We suggest a new (possibly) signaling correlation resource which successfully simulates singlet statistics and this result suggests a new complementary relation between required classical bits and randomness in local output when the classical communication is limited by 1 cbit. This result reproduces the above two models of simulation as extreme cases. This also explains why Leggett's non-local model and the model presented by Branciard et.al. should fail to reproduce the statistics of a singlet.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Leggett-type nonlocal realist inequalities without any constraint on the geometrical alignment of measurement settings

Leggett-type nonlocal realist inequalities that have been derived to date are all contingent upon suitable geometrical constraints to be strictly satisfied by the spatial arrangement of the relevant measurement settings. This undesirable restriction is removed in the present work by deriving appropriate forms of nonlocal realist inequalities, one of which involve the least number of settings compared to all such inequalities derived earlier. The way such inequalities would provide a logically firmer basis for a clearer testing of Leggett-type nonlocal realist model vis-a-vis quantum mechanics is explained.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Bound on Hardy's non-locality from the principle of Information Causality

Recently,the principle of nonviolation of information causality [Nature 461,1101 (2009)], has been proposed as one of the foundational properties of nature. We explore the Hardy's nonlocality theorem for two qubit systems, in the context of generalised probability theory, restricted by the principle of nonviolation of information causality. Applying, a sufficient condition for information causality violation, we derive an upper bound on the maximum success probability of Hardy's nonlocality argument. We find that the bound achieved here is higher than that allowed by quantum mechanics,but still much less than what the nosignaling condition permits. We also study the Cabello type nonlocality argument (a generalization of Hardy's argument) in this context.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Local randomness in Hardy's correlations: Implications from information causality principle

Study of nonlocal correlations in term of Hardy's argument has been quite popular in quantum mechanics. Recently Hardy's argument of non-locality has been studied in the context of generalized non-signaling theory as well as theory respecting information causality. Information causality condition significantly reduces the success probability for Hardy's argument when compared to the result based on non-signaling condition. Here motivated by the fact that maximally entangled state in quantum mechanics does not exhibit Hardy's non-local correlation, we do a qualitative study of the property of local randomness of measured observable on each side reproducing Hardy's non-locality correlation,in the context of information causality condition. On applying the necessary condition for respecting the principle of information causality, we find that there are severe restrictions on the local randomness of measured observable in contrast to results obtained from no-signaling condition.Still, there are some restrictions imposed by quantum mechanics that are not obtained from information causality condition.

0 citations0 reviewsNo code linkedOpen access