The projection games conjecture and the hardness of approximation of Super-SAT and related problems
DOI10.1016/j.jcss.2021.09.002zbMath1472.68064arXiv1907.05548OpenAlexW2957320394WikidataQ113871640 ScholiaQ113871640MaRDI QIDQ2237900
Publication date: 28 October 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.05548
shortest vector probleminapproximabilityclosest vector problemnearest codeword problemlearning halfspace problemprojection games conjecture
Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)
Cites Work
- Factoring polynomials with rational coefficients
- Improved low-density subset sum algorithms
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- On the limits of nonapproximability of lattice problems
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- Approximating CVP to within almost-polynomial factors is NP-hard
- The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
- Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
- Lattice-based FHE as secure as PKE
- Integer Programming with a Fixed Number of Variables
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
- Lattice problems in NP ∩ coNP
- Hardness of approximating the shortest vector problem in lattices
- Two-query PCP with subconstant error
- Probabilistic checking of proofs
- A Parallel Repetition Theorem
- Hardness of approximating the minimum distance of a linear code
- Fully homomorphic encryption using ideal lattices
- (Gap/S)ETH hardness of SVP
- Covering cubes and the closest vector problem
- Classical hardness of learning with errors
- On lattices, learning with errors, random linear codes, and cryptography
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The projection games conjecture and the hardness of approximation of Super-SAT and related problems
