Imagen de Portada

Mind the Gap? Not for SVP Hardness under ETH!

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Aggarwal, Divesh, Gupta, Rishav, Morolia, Aditya, Zhang, Chuanqi
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity Cryptography and Security Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Improved Hardness of BDD and SVP Under Gap-(S)ETH
por: Bennett, Huck, et al.
Publicado: (2021)

Hardness Amplification for (Sparse) LPN
por: Aggarwal, Divesh, et al.
Publicado: (2026)

Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking
por: Dolev, Shlomi
Publicado: (2025)

The Planted Orthogonal Vectors Problem
por: Kühnemann, David, et al.
Publicado: (2025)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
por: Guruswami, Venkatesan, et al.
Publicado: (2025)

Perfect Zero-Knowledge PCPs for #P
por: Gur, Tom, et al.
Publicado: (2024)

On the Maximum Distance Sublattice Problem and Closest Vector Problem
por: Kumar, Rajendra, et al.
Publicado: (2018)

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
por: Epasto, Alessandro, et al.
Publicado: (2026)

On the instance optimality of detecting collisions and subgraphs
por: Ben-Eliezer, Omri, et al.
Publicado: (2023)

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
por: Aggarwal, Divesh, et al.
Publicado: (2020)

InstaHide's Sample Complexity When Mixing Two Private Images
por: Huang, Baihe, et al.
Publicado: (2020)

Privately Estimating Black-Box Statistics
por: Steinke, Günter F., et al.
Publicado: (2025)

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
por: Kothari, Robin, et al.
Publicado: (2025)

Average-Case Complexity of Quantum Stabilizer Decoding
por: Khesin, Andrey Boris, et al.
Publicado: (2025)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
por: Golowich, Noah, et al.
Publicado: (2024)

The NISQ Complexity of Collision Finding
por: Hamoudi, Yassine, et al.
Publicado: (2022)

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
por: Dvijotham, Krishnamurthy, et al.
Publicado: (2024)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
por: Aggarwal, Divesh, et al.
Publicado: (2025)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
por: Kisfaludi-Bak, Sándor, et al.
Publicado: (2020)

Treedepth Inapproximability and Exponential ETH Lower Bound
por: Bonnet, Édouard, et al.
Publicado: (2025)

Computational Hardness of Private Coreset
por: Ghazi, Badih, et al.
Publicado: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
por: Guruswami, Venkatesan, et al.
Publicado: (2023)

Separating Oblivious and Adaptive Differential Privacy under Continual Observation
por: Bun, Mark, et al.
Publicado: (2026)

Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
por: Hillebrand, Quentin, et al.
Publicado: (2024)

Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation
por: Jain, Palak, et al.
Publicado: (2023)

Self-referential instances of the dominating set problem are irreducible
por: Zhou, Guangyan
Publicado: (2026)

Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation
por: Jain, Palak, et al.
Publicado: (2024)

Hardness of Dynamic Core and Truss Decompositions
por: Couto, Yan S., et al.
Publicado: (2025)

Algorithms and Hardness for Estimating Statistical Similarity
por: Bhattacharyya, Arnab, et al.
Publicado: (2025)

Sampling Permutations with Cell Probes is Hard
por: Alekseev, Yaroslav, et al.
Publicado: (2025)

Improved Hardness-of-Approximation for Token Swapping
por: Hiken, Sam, et al.
Publicado: (2024)

k-SUM Hardness Implies Treewidth-SETH
por: Lampis, Michael
Publicado: (2025)

Hardness and Algorithmic Results for Roman \{3\}-Domination
por: Reddy, Sangam Balchandar
Publicado: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
por: Kleinberg, Robert, et al.
Publicado: (2026)

Sumplete is Hard, Even with Two Different Numbers
por: Ruangwises, Suthee
Publicado: (2023)

Hardness Results on Characteristics for Elastic-Degenerated Strings
por: Köppl, Dominik, et al.
Publicado: (2024)

K-stars LDP: A Novel Framework for (p, q)-clique Enumeration under Local Differential Privacy
por: Sun, Henan, et al.
Publicado: (2024)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
por: Gadekar, Ameet, et al.
Publicado: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
por: Gaikwad, Ajinkya, et al.
Publicado: (2026)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
por: Curticapean, Radu, et al.
Publicado: (2024)