Image de couverture de livre

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Guruswami, Venkatesan, Hsieh, Jun-Ting, Raghavendra, Prasad
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms Computational Complexity Metric Geometry
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Time complexity of the Analyst's Traveling Salesman algorithm
par: Ramirez, Anthony, et autres
Publié: (2022)

Nearly-Tight Bounds for Zonotope Containment and Beyond
par: Eisenbrand, Friedrich, et autres
Publié: (2026)

On optimal distinguishers for Planted Clique
par: Nagda, Ansh, et autres
Publié: (2025)

Scheduling Problems with Constrained Rejections
par: Davies, Sami, et autres
Publié: (2025)

Hardness of Learning Boolean Functions from Label Proportions
par: Guruswami, Venkatesan, et autres
Publié: (2024)

Lower bounds for the universal TSP on the plane
par: Kravaris, Cosmas
Publié: (2024)

Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
par: Bai, Xingjian, et autres
Publié: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
par: Guruswami, Venkatesan, et autres
Publié: (2023)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
par: Guruswami, Venkatesan, et autres
Publié: (2025)

The Power of Recursive Embeddings for $\ell_p$ Metrics
par: Krauthgamer, Robert, et autres
Publié: (2025)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
par: Krauthgamer, Robert, et autres
Publié: (2026)

Fine-Grained Complexity of Continuous Euclidean k-Center
par: Blank, Lotte, et autres
Publié: (2026)

On connections between k-coloring and Euclidean k-means
par: Aman, Enver, et autres
Publié: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
par: Kisfaludi-Bak, Sándor, et autres
Publié: (2020)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Time warping with Hellinger elasticity
par: Billig, Yuly
Publié: (2026)

Fitting trees to $\ell_1$-hyperbolic distances
par: Yim, Joon-Hyeok, et autres
Publié: (2024)

Random zero sets with local growth guarantees
par: Chang, Alan, et autres
Publié: (2024)

Beyond Bits: An Introduction to Computation over the Reals
par: Miltzow, Tillmann
Publié: (2026)

Universal Solvability for Robot Motion Planning on Graphs
par: Dhar, Anubhav, et autres
Publié: (2025)

Rounding Large Independent Sets on Expanders
par: Bafna, Mitali, et autres
Publié: (2024)

The communication complexity of distributed estimation
par: Gopalan, Parikshit, et autres
Publié: (2025)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
par: Brakensiek, Joshua, et autres
Publié: (2026)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
par: Rao, Satish
Publié: (2025)

O(1)-Distortion Planar Emulators for String Graphs
par: Chang, Hsien-Chih, et autres
Publié: (2025)

The Quasi-Polynomial Low-Degree Conjecture is False
par: Buhai, Rares-Darius, et autres
Publié: (2025)

Semirandom Planted Clique via 1-norm Isometry Property
par: Guruswami, Venkatesan, et autres
Publié: (2025)

Solving Random Planted CSPs below the $n^{k/2}$ Threshold
par: Basu, Arpon, et autres
Publié: (2025)

The Planted Orthogonal Vectors Problem
par: Kühnemann, David, et autres
Publié: (2025)

Complexity of Local Search for Euclidean Clustering Problems
par: Manthey, Bodo, et autres
Publié: (2023)

Inapproximability of Maximum Diameter Clustering for Few Clusters
par: Fleischmann, Henry, et autres
Publié: (2023)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
par: Khanna, Sanjeev, et autres
Publié: (2025)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
par: Bringmann, Karl, et autres
Publié: (2024)

Improved Hardness of Approximation for Geometric Bin Packing
par: Ray, Arka, et autres
Publié: (2023)

Recognizing 2-Layer and Outer $k$-Planar Graphs
par: Kobayashi, Yasuaki, et autres
Publié: (2024)

Subcoloring of (Unit) Disk Graphs
par: Marin, Malory, et autres
Publié: (2025)

Fast and simple multiplication of bounded twin-width matrices
par: Kozma, László, et autres
Publié: (2026)

Computational Complexities of Folding
par: Eppstein, David
Publié: (2024)

Hardness of Median and Center in the Ulam Metric
par: Fischer, Nick, et autres
Publié: (2025)