Copertina

Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Lubiw, Anna, Schaefer, Marcus
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Geometry 68Q17, 05C62 F.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

DAG Scheduling in the BSP Model
di: Papp, Pál András, et al.
Pubblicazione: (2023)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
di: Lobe, Elisabeth, et al.
Pubblicazione: (2021)

Folding One Polyhedral Metric Graph into Another
di: Chung, Lily, et al.
Pubblicazione: (2024)

Graph polynomials: some questions on the edge
di: Farr, Graham, et al.
Pubblicazione: (2024)

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

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
di: Philip, Geevarghese, et al.
Pubblicazione: (2026)

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

On (In)approximability of MaxMin Independent Set Reconfiguration
di: Hoang, Hung P., et al.
Pubblicazione: (2026)

Beyond the Existential Theory of the Reals
di: Schaefer, Marcus, et al.
Pubblicazione: (2022)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
di: Eua-anant, Pakapim, et al.
Pubblicazione: (2025)

On Small-depth Frege Proofs for PHP
di: Håstad, Johan
Pubblicazione: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
di: Levin, Leonid A.
Pubblicazione: (2022)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2024)

A Fiber Criterion for Representation Identifiability in Supervised Learning
di: Sevetlidis, Vasileios
Pubblicazione: (2026)

Computing shortest closed curves on non-orientable surfaces
di: Bulavka, Denys, et al.
Pubblicazione: (2024)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
di: Emmerich, Michael T. M., et al.
Pubblicazione: (2026)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
di: Demaine, Erik D., et al.
Pubblicazione: (2024)

QuIC: A Training-Free Quantum Graph Embedding from Ideal Analysis to Practical Hardware Evaluation
di: Miller, Luke, et al.
Pubblicazione: (2026)

Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach
di: Chimani, Markus, et al.
Pubblicazione: (2024)

Robust Bichromatic Classification using Two Lines
di: Glazenburg, Erwin, et al.
Pubblicazione: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
di: Kelley, Zander, et al.
Pubblicazione: (2023)

Human Supervision as an Information Bottleneck: A Unified Theory of Error Floors in Human-Guided Learning
di: Dominguez, Alejandro Rodriguez
Pubblicazione: (2026)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
di: Bannach, Max, et al.
Pubblicazione: (2025)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
di: Lagerkvist, Victor, et al.
Pubblicazione: (2026)

How Hard is it to be a Star? Convex Geometry and the Real Hierarchy
di: Schaefer, Marcus, et al.
Pubblicazione: (2025)

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

The Gallai Vertex Problem is $Θ_2^p$-Complete
di: Nikabadi, Amir, et al.
Pubblicazione: (2026)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
di: Golovach, Petr A., et al.
Pubblicazione: (2022)

The Impact of Partial Computations on the Red-Blue Pebble Game
di: Papp, Pál András, et al.
Pubblicazione: (2025)

Pliability and Approximating Max-CSPs
di: Romero, Miguel, et al.
Pubblicazione: (2019)

Computational Hardness of Reinforcement Learning with Partial $q^π$-Realizability
di: Karimi, Shayan, et al.
Pubblicazione: (2025)

Optimal Portfolio Compression for Priority-Proportional Clearing with Defaulting Costs
di: Csáji, Gergely, et al.
Pubblicazione: (2026)

Batched Nonparametric Bandits via k-Nearest Neighbor UCB
di: Arya, Sakshi
Pubblicazione: (2025)

Hive is PSPACE-Hard
di: Andel, Daniël, et al.
Pubblicazione: (2025)

Maximum Matchings in Geometric Intersection Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2019)

Monotone Arc Diagrams with few Biarcs
di: Chaplick, Steven, et al.
Pubblicazione: (2024)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
di: Böhnlein, Toni, et al.
Pubblicazione: (2024)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
di: Levet, Michael, et al.
Pubblicazione: (2023)

Closed-Form Beta Distribution Estimation from Sparse Statistics with Random Forest Implicit Regularization
di: Landers, Jonathan R.
Pubblicazione: (2025)

Maximum Centre-Disjoint Mergeable Disks
di: Rudi, Ali Gholami
Pubblicazione: (2023)