Cover Image

Bounded Distance Decoding for Random Lattices

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Gao, Shuhong
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity 68Q25 (primary), 11H06 (secondary) F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Conserved active information
by: Chen, Yanchen, et al.
Published: (2025)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

Parallel Algorithms for Group Isomorphism via Code Equivalence
by: Levet, Michael
Published: (2026)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
by: Filmus, Yuval, et al.
Published: (2020)

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

A Classifying Topos for the Spectrum of Equivalences
by: Oggad, Kenan
Published: (2026)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)

Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
by: Alpay, Faruk, et al.
Published: (2026)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
by: von Liechtenstein, Maximilian R. P.
Published: (2025)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
by: Lela, Marko
Published: (2025)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

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

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
by: DasGupta, Bhaskar, et al.
Published: (2026)

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

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

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

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
by: Phillips, Reed
Published: (2026)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
by: Bodirsky, Manuel, et al.
Published: (2023)

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

Complexity Classification Transfer for CSPs via Algebraic Products
by: Bodirsky, Manuel, et al.
Published: (2022)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2024)

Multi-variable Quantification of BDDs in External Memory using Nested Sweeping (Extended Paper)
by: Sølvsten, Steffan Christ, et al.
Published: (2024)

Symbolic Model Checking in External Memory
by: Sølvsten, Steffan Christ, et al.
Published: (2025)

Lattices of type $A_n$, $D_n$, $E_n$ and codes
by: Higa, Riku
Published: (2025)

On Finding Randomly Planted Cliques in Arbitrary Graphs
by: Agrimonti, Francesco, et al.
Published: (2025)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

Efficient Binary Decision Diagram Manipulation in External Memory
by: Sølvsten, Steffan Christ, et al.
Published: (2021)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Amalgamation in Semilinear Residuated Lattices
by: Fussner, Wesley, et al.
Published: (2024)

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

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Tempered Perfect Lattices in the Binary Case
by: Bahnson, Erik, et al.
Published: (2023)

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

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Local Well-Posedness of a Model for Stress-Driven Growth in the Presence of Nutrients
by: Abels, Helmut, et al.
Published: (2026)