Source author record

Monika Rosicka

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO quant-ph

Catalog footprint

Research overview

5works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Gadget structures in proofs of the Kochen-Specker theorem

The Kochen-Specker theorem is a fundamental result in quantum foundations that has spawned massive interest since its inception. We show that within every Kochen-Specker graph, there exist interesting subgraphs which we term $01$ -gadgets, that capture the essential contradiction necessary to prove the Kochen-Specker theorem, i.e,. every Kochen-Specker graph contains a $01$ -gadget and from every $01$ -gadget one can construct a proof of the Kochen-Specker theorem. Moreover, we show that the $01$ -gadgets form a fundamental primitive that can be used to formulate state-independent and state-dependent statistical Kochen-Specker arguments as well as to give simple constructive proofs of an "extended" Kochen-Specker theorem first considered by Pitowsky.

preprint2019arXiv

Generalized XOR non-locality games with graph description on a square lattice

We propose a family of non-locality unique games for 2 parties based on a square lattice on an arbitrary surface. We show that, due to structural similarities with error correction codes of Kitaev for fault tolerant quantum computation, the games have classical values computable in polynomial time for $d=2$ measurement outcomes. By representing games in their graph form, for arbitrary $d$ and underlying surface we provide their classification into equivalence classes with respect to relabeling of measurement outcomes, for a selected set of permutations which define the winning conditions. A case study of games with periodic boundary conditions is presented in order to verify their impact on classical and quantum values of the family of games. It suggests that quantum values suffer independently from presence of different winning conditions that can be imposed due to periodicity, as long as no local restrictions are in place.

preprint2016arXiv

Permutation graphs and unique games

We study the value of unique games as a graph-theoretic parameter. This is obtained by labeling edges with permutations. We describe the classical value of a game as well as give a necessary and sufficient condition for the existence of an optimal assignment based on a generalisation of permutation graphs and graph bundles. In considering some special cases, we relate XOR games to EDGE BIPARTIZATION, and define an edge-labeling with permutations from Latin squares.

preprint2015arXiv

Linear game non-contextuality and Bell inequalities - a graph-theoretic approach

We study the classical and quantum values of one- and two-party linear games, an important class of unique games that generalizes the well-known XOR games to the case of non-binary outcomes. We introduce a ``constraint graph" associated to such a game, with the constraints defining the linear game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of more general XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lovász theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. Linear games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite linear game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions.

preprint2013arXiv

Graphs with $C_3_-free vertices are not universal fixers

A non-isolated vertex $x\in V(G)$ is called $C_{3}$ -free if $x$ belongs to no triangle of $G$ . In \cite{BMW} Burger, Mynhardt and Weakley introduced the idea of universal fixers. Let $G=(V,E)$ be a graph with $n$ vertices and $G'$ a copy of $G$ . For a bijective function $π:V(G)\mapsto V (G')$ , we define the prism $πG$ of $G$ as follows: $V(πG)=V(G)\cup V(G')$ and $E(πG)=E(G)\cup E(G')\cup M_π$ , where $M_π=\{uπ(u): u\in V(G)\}$ . Let $γ(G)$ be the domination number of $G$ . If $γ(πG)=γ(G)$ for any bijective function $π$ , then $G$ is called a universal fixer. In \cite{MX} it is conjectured that the only universal fixer is the edgeless graph $\bar{K_n}$ . In this note, we prove that any graph $G$ with $C_3$ -free vertices is not a universal fixer graph.

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.