Cover Image

Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Asadi, Ali, Chatterjee, Krishnendu, Lurie, David, Saona, Raimundo
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Systems and Control Optimization and Control Probability F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Prophet Inequalities: Separating Random Order from Order Selection
by: Giambartolomei, Giordano, et al.
Published: (2023)

IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
by: Giambartolomei, Giordano, et al.
Published: (2024)

The Complexity of Blocking All Solutions
by: Grüne, Christoph, et al.
Published: (2025)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
by: Grüne, Christoph, et al.
Published: (2023)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
by: Grüne, Christoph, et al.
Published: (2024)

Linear Equations with Min and Max Operators: Computational Complexity
by: Chatterjee, Krishnendu, et al.
Published: (2024)

Uniform Value and Decidability in Ergodic Blind Stochastic Games
by: Chatterjee, Krishnendu, et al.
Published: (2024)

Approximating the Uniform Value in Hidden Stochastic Games with Doeblin Conditions
by: Chatterjee, Krishnendu, et al.
Published: (2026)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
by: Liao, Chao, et al.
Published: (2022)

Limit-sure reachability for small memory policies in POMDPs is NP-complete
by: Asadi, Ali, et al.
Published: (2024)

On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
by: Diaby, Moustapha, et al.
Published: (2023)

Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard
by: Moseley, Benjamin, et al.
Published: (2026)

Direct Sums for Parity Decision Trees
by: Besselman, Tyler, et al.
Published: (2024)

Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem
by: Boveroux, Laurie, et al.
Published: (2025)

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes
by: Gamarnik, David
Published: (2025)

Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization
by: Jin, Ruiyang, et al.
Published: (2025)

Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms
by: Bhargav, Jayanth, et al.
Published: (2024)

Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
by: Emmerich, Michael T. M., et al.
Published: (2026)

Online matching and market imbalance
by: Barrientos, Benjamin, et al.
Published: (2025)

How Low Can We Go? Minimizing Interaction Samples for Configurable Systems
by: Krupke, Dominik, et al.
Published: (2025)

A Bi-Level Optimization Approach to Joint Trajectory Optimization for Redundant Manipulators
by: Fried, Jonathan, et al.
Published: (2024)

A hybrid solution approach for the Integrated Healthcare Timetabling Competition 2024
by: Guericke, Daniela, et al.
Published: (2025)

Subgradient Method for System Identification with Non-Smooth Objectives
by: Yalcin, Baturalp, et al.
Published: (2025)

Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
by: Emmerich, Michael T. M., et al.
Published: (2026)

Benders Cut Filtering for Affine Potential-Based Flow Problems with Robustness Scenarios and Topology Switching
by: Donkiewicz, Tim, et al.
Published: (2026)

A Digital Twin-Based Simulation Framework for Safe Curve Speed Estimation Using Unity
by: Rahman, Araf, et al.
Published: (2025)

FRIDAY: Real-time Learning DNN-based Stable LQR controller for Nonlinear Systems under Uncertain Disturbances
by: Fujimori, Takahito
Published: (2024)

A biased random-key genetic algorithm with variable mutants to solve a vehicle routing problem
by: Festa, Paola, et al.
Published: (2024)

Finite horizon stochastic $H_2/H_\infty$ control for continuous-time mean-field systems with Poisson jumps
by: Han, Huimin, et al.
Published: (2025)

Learning POMDPs with Linear Function Approximation and Finite Memory
by: Kara, Ali Devran
Published: (2025)

Thin Tree Verification is coNP-Complete
by: Moayyedi, Alice
Published: (2025)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
by: Kiatchaipipat, Nattapol, et al.
Published: (2025)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
by: Gupta, Chetan, et al.
Published: (2025)

A Feedback Control Framework for Incentivised Suburban Parking Utilisation and Urban Core Traffic Relief
by: Satti, Abdul Baseer, et al.
Published: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
by: Fritsch, Timo, et al.
Published: (2026)

Fast Simulation of Cellular Automata by Self-Composition
by: Natal, Joseph, et al.
Published: (2024)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

Neuromorphic Deployment of Spiking Neural Networks for Cognitive Load Classification in Air Traffic Control
by: An, Jiahui, et al.
Published: (2025)

Software Implementation of Digital Filtering via Tustin's Bilinear Transform
by: Herron, Connor W.
Published: (2024)

Dynamic Layered Decoding Scheduling for LDPC Codes Aided by Check Node Error Probabilities
by: Jia, Chenyuan, et al.
Published: (2025)