scientific article; zbMATH DE number 1775419
From MaRDI portal
Publication:4542552
zbMATH Open1028.68065MaRDI QIDQ4542552FDOQ4542552
Authors: Sanjeev Arora
Publication date: 1 August 2002
Title of this publication is not available (Why is that?)
Recommendations
Cited In (33)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some recent strong inapproximability results
- The Fault Tolerance of NP-Hard Problems
- Embracing the giant component
- Interactive and probabilistic proof-checking
- On the hardness of approximating minimization problems
- The inapproximability of non-NP-hard optimization problems.
- Relation between the hardness of a problem and the number of its solutions
- Approximation algorithms for NP-hard problems
- On Unapproximable Versions of $NP$-Complete Problems
- A computational-level explanation of the speed of goal inference
- On the Effective Enumerability of NP Problems
- The hardness of approximation: Gap location
- Approximate counting and NP search problems
- Title not available (Why is that?)
- The work of Subhash Khot
- Rational analysis, intractability, and the prospects of `as if'-explanations
- Title not available (Why is that?)
- Approximate solution of NP optimization problems
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- The NP-completeness column: the many limits on approximation
- Improved approximations for hard optimization problems via problem instance classification
- Hardness of fully dense problems
- NP-completeness of the Hamming salesman problem
- Inapproximability of combinatorial optimization problems
- A computational complexity analysis of tunable type inference for Generic Universe Types
- Title not available (Why is that?)
- A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations
- Algebraic testing and weight distributions of codes.
- UG-hardness to NP-hardness by losing half
- Easy NP-hardness Proofs of Some Subset Choice Problems
- The Complexity and Distribution of Hard Problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4542552)