Lattice problems in NP ∩ coNP

DOI10.1145/1089023.1089025zbMath1286.68218OpenAlexW2037426925WikidataQ57567999 ScholiaQ57567999MaRDI QIDQ3546284

Dorit Aharonov, Oded Regev

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1089023.1089025

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Improved hardness results for unique shortest vector problem, Progress in quantum algorithms, Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!, New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors, Lifts for Voronoi cells of lattices, A polynomial time algorithm for GapCVPP in \(l_1\) norm, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Revisiting lattice tiling decomposition and dithered quantisation, Mathematics of computation through the lens of linear equations and lattices, Explicit Hard Instances of the Shortest Vector Problem, Pseudo-deterministic Proofs, The Reductions for the Approximating Covering Radius Problem, Discrete Gaussian Distributions via Theta Functions, The projection games conjecture and the hardness of approximation of Super-SAT and related problems, On a certain class of positive definite functions and measures on locally compact abelian groups and inner-product spaces, A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices, Hermite’s Constant and Lattice Algorithms, Approximate Voronoi cells for lattices, revisited, Asymptotically Efficient Lattice-Based Digital Signatures, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Cryptographic hardness for learning intersections of halfspaces, An Average Case NP-complete Graph Colouring Problem, Round-optimal blind signatures in the plain model from classical and quantum standard assumptions, Advanced lattice sieving on GPUs, with tensor cores, Computational complexity, Newton polytopes, and Schubert polynomials, Kissing Numbers and Transference Theorems from Generalized Tail Bounds, The Restricted Isometry Property of Subsampled Fourier Matrices, Measure inequalities and the transference theorem in the geometry of numbers, The Complexity of Public-Key Cryptography, The remote set problem on lattices