On the advantage over a random assignment

DOI10.1002/RSA.20031zbMath1078.68159OpenAlexW1990184247WikidataQ56958935 ScholiaQ56958935MaRDI QIDQ5894908

No author found.

Publication date: 12 January 2005

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20031

zbMATH Keywords

approximation algorithmsconstraint satisfaction problemsmeasure of approximationinpproximability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (11)

Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ Unnamed Item ⋮ A probabilistic approach to problems parameterized above or below tight bounds ⋮ Computing the Partition Function of a Polynomial on the Boolean Cube ⋮ Solving MAX-\(r\)-SAT above a tight lower bound ⋮ Note on Max Lin-2 above average ⋮ On the Consistent Path Problem ⋮ Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width ⋮ A Probabilistic Approach to Problems Parameterized above or below Tight Bounds

Cites Work

• Inequalities in Fourier analysis
• Derandomized graph products
• Towards optimal lower bounds for clique and chromatic number.
• The complexity of approximating a nonlinear program
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• A Parallel Repetition Theorem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Algorithms with large domination ratio
• Some optimal inapproximability results
• Noise-tolerant learning, the parity problem, and the statistical query model

This page was built for publication: On the advantage over a random assignment