An official website of the United States government
In a recent work, Moshkovitz [FOCS '14] presented a transformation on two-player games called ``fortification'', and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an \emph{analytic reformulation} of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show \emph{any} game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, two problems which have recently received much attention. An important component of our work is a variant of the fortification transformation, called ``ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.
more »
« less
Parallel Repetition of k-Player Projection Games
We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with a value less than 1.
more »
« less
- PAR ID:
- 10554558
- Editor(s):
- Kumar, Amit; Ron-Zewi, Noga
- Publisher / Repository:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Date Published:
- Volume:
- 317
- ISSN:
- 1868-8969
- ISBN:
- 978-3-95977-348-5
- Page Range / eLocation ID:
- 317-317
- Subject(s) / Keyword(s):
- Parallel Repetition Multiplayer games Projection games Theory of computation → Interactive proof systems
- Format(s):
- Medium: X Size: 16 pages; 816326 bytes Other: application/pdf
- Size(s):
- 16 pages 816326 bytes
- Right(s):
- Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate --- in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called \emph{anchoring}, inspired in part by the Feige-Kilian transformation, that turns \emph{any} (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture.more » « less
-
Abstract The systems for multiphoton 3D nanoprinting are rapidly increasing in print speed for larger throughput and scale, unfortunately without also improvement in resolution. Separately, the process of photoinhibition lithography has been demonstrated to enhance the resolution of multiphoton printing through the introduction of a secondary laser source. The photo-chemical dynamics and interactions for achieving photoinhibition in the various multiphoton photoinitiator systems are complex and still not well understood. Here, we examine the photoinhibition process of the common photoinitiator 7-diethylamino 3-thenoylcoumarin (DETC) with inhibition lasers near or at the multiphoton printing laser wavelength in typical low peak intensity, high repetition rate 3D nanoprinting processes. We demonstrate the clear inhibition of the polymerization process consistent with a triplet absorption deactivation mechanism for a DETC photoresist as well as show inhibition for several other photoresist systems. Additionally, we explore options to recover the photoinhibition process when printing with high intensity, low repetition rate lasers. Finally, we demonstrate photoinhibition in a projection multiphoton printing system. This investigation of photoinhibition lithography with common photoinitiators elucidates the possibility for photoinhibition occurring in many resist systems with typical high repetition rate multiphoton printing lasers as well as for high-speed projection multiphoton printing.more » « less
-
This article concerns the use of parallel transport to create a diabatic basis. The advantages of the parallel-transported basis include the facility with which Taylor series expansions can be carried out in the neighborhood of a point or a manifold such as a seam (the locus of degeneracies of the electronic Hamiltonian), and the close relationship between the derivative couplings and the curvature in this basis. These are important for analytic treatments of the nuclear Schrödinger equation in the neighborhood of degeneracies. The parallel-transported basis bears a close relationship to the singular-value basis; in this article, both are expanded in power series about a reference point and are shown to agree through second order but not beyond. Taylor series expansions are effected through the projection operator, whose expansion does not involve energy denominators or any type of singularity and in terms of which both the singular-value basis and the parallel-transported basis can be expressed. The parallel-transported basis is a version of Poincaré gauge, well known in electromagnetism, which provides a relationship between the derivative couplings and the curvature and which, along with a formula due to Mead, affords an efficient method for calculating Taylor series of the basis states and the derivative couplings. The case in which fine structure effects are included in the electronic Hamiltonian is covered.more » « less
-
In this paper, we study the total displacement statistic of parking functionsfrom the perspective of cooperative game theory. We introduce parking games,which are coalitional cost-sharing games in characteristic function formderived from the total displacement statistic. We show that parking games aresupermodular cost-sharing games, indicating that cooperation is difficult(i.e., their core is empty). Next, we study their Shapley value, whichformalizes a notion of fair cost-sharing and amounts to charging each car forits expected marginal displacement under a random arrival order. Our maincontribution is a polynomial-time algorithm to compute the Shapley value ofparking games, in contrast with known hardness results on computing the Shapleyvalue of arbitrary games. The algorithm leverages the permutation-invariance oftotal displacement, combinatorial enumeration, and dynamic programming. Weconclude with open questions around an alternative solution concept forsupermodular cost-sharing games and connections to other areas incombinatorics.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.54
