Cover Image

Complexity of Unambiguous Problems in $Σ^P_2$

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gilboa, Matan, Goldberg, Paul W., Koutsoupias, Elias, Nisan, Noam
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Computer Science and Game Theory F.2; F.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
by: Cheval, Vincent, et al.
Published: (2025)

Simple Stochastic Stopping Games: A Generator and Benchmark Library
by: Rudich, Avi, et al.
Published: (2024)

A Characterization of Complexity in Public Goods Games
by: Gilboa, Matan
Published: (2023)

The Complexity of Graph Exploration Games
by: Fuchs, Janosch, et al.
Published: (2023)

Verification Cost Asymmetry in Cognitive Warfare: A Complexity-Theoretic Framework
by: Luberisse, Joshua
Published: (2025)

Learning to Maximize Gains From Trade in Small Markets
by: Babaioff, Moshe, et al.
Published: (2024)

The Computational Complexity of Variational Inequalities and Applications in Game Theory
by: Kapron, Bruce M., et al.
Published: (2024)

The Complexity of Strategic Behavior in Primary Elections
by: Cleveland, Colin, et al.
Published: (2026)

Anyone but Him: The Complexity of Precluding an Alternative
by: Hemaspaandra, Edith, et al.
Published: (2005)

A Note On The Natural Range Of Unambiguous-SAT
by: Pay, Tayfun
Published: (2023)

Constructibility and the P versus NP problem
by: Hole, Arne
Published: (2024)

Search versus Search for Collapsing Electoral Control Types
by: Carleton, Benjamin, et al.
Published: (2022)

The Degree of Fairness in Efficient House Allocation
by: Hosseini, Hadi, et al.
Published: (2024)

Graph-Based Deterministic Polynomial Framwork for NP Problems
by: Lee, Changryeol
Published: (2025)

Low communication protocols for fair allocation of indivisible goods
by: Feige, Uriel
Published: (2024)

Computation as a Game
by: Bilokon, Paul Alexander
Published: (2025)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games
by: Bullinger, Martin, et al.
Published: (2024)

Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity
by: Caragiannis, Ioannis, et al.
Published: (2024)

Designing Rules for Choosing a Winner in a Debate
by: Heckett, Alexander, et al.
Published: (2025)

Matching Markets with Chores
by: Garg, Jugal, et al.
Published: (2024)

Bribery Can Get Harder in Structured Multiwinner Approval Election
by: Kusek, Bartosz, et al.
Published: (2022)

Matroid Bayesian Online Selection
by: DeHaan, Ian, et al.
Published: (2024)

Randomized Strategyproof Mechanisms with Best of Both Worlds Fairness and Efficiency
by: Sun, Ankang, et al.
Published: (2024)

A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?
by: Li, Bo, et al.
Published: (2024)

A Note on the NP-Hardness of PARTITION Via First-Order Projections
by: Iturralde, Paúl Risco
Published: (2025)

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
by: Fan, Austen, et al.
Published: (2026)

Coverage Games
by: Kupferman, Orna, et al.
Published: (2026)

Nonuniform Deterministic Finite Automata over finite algebraic structures
by: Idziak, Paweł M., et al.
Published: (2025)

On the Welfare of EIP-1559 with Patient Bidders
by: Babaioff, Moshe, et al.
Published: (2025)

Domination-Avoiding Learning Agents Cannot Collude
by: Nisan, Noam, et al.
Published: (2026)

Consumable Data via Quantum Communication
by: Gilboa, Dar, et al.
Published: (2024)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

Zero Carbon V2X Tariffs for Non-Domestic Customers
by: Shamash, Elisheva S, et al.
Published: (2025)

EF1 Allocations for Identical Trilean and Separable Single-Peaked Valuations
by: Bhaskar, Umang, et al.
Published: (2024)

Equilibrium Computation in the Hotelling-Downs Model of Spatial Competition
by: Bhaskar, Umang, et al.
Published: (2024)

Reactive Synthesis for Expected Impacts
by: Chini, Emanuele, et al.
Published: (2024)

Two-player Domino games
by: de Menibus, Benjamin Hellouin, et al.
Published: (2023)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
by: Kazakov, Yevgeny, et al.
Published: (2009)