Cover Image

Query-Efficient Fixpoints of $\ell_p$-Contractions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Haslebacher, Sebastian, Lill, Jonas, Schnider, Patrick, Weber, Simon
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Approximability of Steiner Tree in $\ell_p$-metrics
by: Fleischmann, Henry, et al.
Published: (2023)

Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
by: Borzechowski, Michaela, et al.
Published: (2024)

Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements
by: Borzechowski, Michaela, et al.
Published: (2026)

Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2026)

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
by: Hair, Isaac M, et al.
Published: (2026)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
by: Lill, Jonas, et al.
Published: (2024)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
by: Guruswami, Venkatesan, et al.
Published: (2021)

Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$
by: Hecht, Yahli, et al.
Published: (2025)

On $\ell_p$-Vietoris-Rips complexes
by: Ivanov, Sergei O., et al.
Published: (2024)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

On the Exact Matching Problem in Dense Graphs
by: Maalouly, Nicolas El, et al.
Published: (2024)

The Power of Recursive Embeddings for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2025)

Pathways to Tractability for Geometric Thickness
by: Depian, Thomas, et al.
Published: (2024)

Unfairly Splitting Separable Necklaces
by: Schnider, Patrick, et al.
Published: (2024)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2026)

On Approximability of $\ell_2^2$ Min-Sum Clustering
by: S., Karthik C., et al.
Published: (2024)

Computing $p$-presentation distances is hard
by: Bjerkevik, Håvard Bakke, et al.
Published: (2024)

On Saxe's theorems about the complexity of the Distance Geometry Problem
by: Kupperschmitt, Maël, et al.
Published: (2025)

Minimum Selective Subset on Some Graph Classes
by: Manna, Bubai
Published: (2025)

Counting Triangulations of Fixed Cardinal Degrees
by: Chambers, Erin, et al.
Published: (2025)

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
by: DeStefano, Zachary, et al.
Published: (2025)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Realizing Metric Spaces with Convex Obstacles
by: Kisfaludi-Bak, Sándor, et al.
Published: (2025)

Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
by: Manna, Bubai
Published: (2025)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Geometric Bipartite Matching is in NC
by: Bhore, Sujoy, et al.
Published: (2024)

Complexity of 2D Snake Cube Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

The Parameterized Complexity of Geometric 1-Planarity
by: Firbas, Alexander
Published: (2026)

Constrained Boundary Labeling
by: Depian, Thomas, et al.
Published: (2024)

On the hardness of finding normal surfaces
by: Burton, Benjamin A., et al.
Published: (2019)

Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
by: Boomari, Hossein, et al.
Published: (2018)

The Complexity of Drawing Graphs on Few Lines and Few Planes
by: Chaplick, Steven, et al.
Published: (2016)

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)

Undecidability of Translational Tiling with Three Tiles
by: Yang, Chan, et al.
Published: (2024)

Translational Aperiodic Sets of 7 Polyominoes
by: Yang, Chao, et al.
Published: (2024)

The Borsuk number of a graph
by: Cáceres, José, et al.
Published: (2026)

Deterministic Depth-4 PIT and Normalization
by: Guo, Zeyu, et al.
Published: (2025)

Improved Debordering of Waring Rank
by: Shpilka, Amir
Published: (2025)

Simple Linear Loops: Algebraic Invariants and Applications
by: Manssour, Rida Ait El, et al.
Published: (2024)