:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Gibor, Daniel
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Computational Geometry
Online Access:	https://arxiv.org/abs/2511.14244
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings
by: Vu, Thi Xuan
Published: (2025)

Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
by: Goodrich, Michael T., et al.
Published: (2024)

Approximate Algorithms for Chamfer Distance Under Translation
by: Halevi, Gil, et al.
Published: (2026)

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

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
by: Gokaj, Geri, et al.
Published: (2025)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
by: Bringmann, Karl, et al.
Published: (2024)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Time complexity of the Analyst's Traveling Salesman algorithm
by: Ramirez, Anthony, et al.
Published: (2022)

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

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
by: Tulsiani, Madhur, et al.
Published: (2024)

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)

Query-Efficient Fixpoints of $\ell_p$-Contractions
by: Haslebacher, Sebastian, et al.
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)

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

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)

Bounds for Geometric rank in Terms of Subrank
by: Chen, Qiyuan, et al.
Published: (2025)

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)

Equidistribution for Random Polynomials and Systems of Random Holomorphic Sections
by: Günyüz, Ozan
Published: (2024)

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

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
by: DeJesse, Nicholas, et al.
Published: (2025)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
by: He, Yumeng, et al.
Published: (2024)

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
by: Kosoy, Vanessa, et al.
Published: (2016)

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting
by: Gribanov, Dmitry, et al.
Published: (2026)

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