Mathematics of computation through the lens of linear equations and lattices
From MaRDI portal
Publication:6198651
DOI10.4171/icm2022/178OpenAlexW4389774849MaRDI QIDQ6198651
Publication date: 20 March 2024
Published in: International Congress of Mathematicians (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4171/icm2022/178
Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattices and convex bodies (number-theoretic aspects) (11H06) Complexity of computation (including implicit computational complexity) (03D15) Lattice points in specified regions (11P21) Approximation algorithms (68W25) Linear Diophantine equations (11D04)
Cites Work
- Sub-constant error probabilistically checkable proof of almost-linear size
- Spectral algorithms for unique games
- PCP characterizations of NP: toward a polynomially-small error-probability
- The complete intersection theorem for systems of finite sets
- Stable lattices and the diagonal group
- On the hardness of approximating minimum vertex cover
- Noise stability of functions with low influences: invariance and optimality
- On Lovász' lattice reduction and the nearest lattice point problem
- A hierarchy of polynomial time lattice basis reduction algorithms
- Factoring polynomials with rational coefficients
- Boolean functions with low average sensitivity depend on few coordinates
- New bounds in some transference theorems in the geometry of numbers
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- On the limits of nonapproximability of lattice problems
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On the hardness of approximating Multicut and Sparsest-Cut
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
- Graph expansion and the unique games conjecture
- Near-optimal algorithms for unique games
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Subexponential Algorithms for Unique Games and Related Problems
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Lattice problems in NP ∩ coNP
- Hardness of approximating the shortest vector problem in lattices
- The importance of being biased
- Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures
- Probabilistic checking of proofs
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- On independent sets, 2-to-2 games, and Grassmann graphs
- A reverse Minkowski theorem
- Reducibility among Combinatorial Problems
- Towards a proof of the 2-to-1 games conjecture?
- On non-optimally expanding sets in Grassmann graphs
- Hypercontractivity, sum-of-squares proofs, and their applications
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- The complexity of theorem-proving procedures
- The PCP theorem by gap amplification
- On lattices, learning with errors, random linear codes, and cryptography
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Mathematics of computation through the lens of linear equations and lattices
