Definable Inapproximability: New Challenges for Duplicator
From MaRDI portal
Publication:5079727
Recommendations
Cites work
- scientific article; zbMATH DE number 5485476 (Why is no real title available?)
- scientific article; zbMATH DE number 1330032 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- A Parallel Repetition Theorem
- A combinatorial characterization of resolution width
- A definability dichotomy for finite valued CSPs
- Affine systems of equations and counting infinitary logic
- Computational Complexity
- Definability of semidefinite programming and Lasserre lower bounds for CSPs
- Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
- Logical hierarchies in PTIME
- On sufficient conditions for unsatisfiability of random formulas
- On the hardness of approximating minimum vertex cover
- Optimization, approximation, and complexity classes
- Proof verification and the hardness of approximation problems
- Short proofs are narrow—resolution made simple
- Solving linear programs without breaking abstractions
- Some optimal inapproximability results
- The pebbling comonad in finite model theory
Cited in
(3)
This page was built for publication: Definable Inapproximability: New Challenges for Duplicator
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5079727)