On the advantage over a random assignment

DOI10.1002/RSA.20031MaRDI QIDQ5894908zbMATH OpenOpenAlexWikidataFDO

Authors Johan Hastad, S. Venkatesh

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 problemsinpproximabilitymeasure of approximation

Mathematics Subject Classification ID

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

Recommendations

• Automata, Languages and Programming
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Randomized approximation of the constraint satisfaction problem
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem

Cites work

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

Cited in

(13)

• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Grothendieck-type inequalities in combinatorial optimization
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• A probabilistic approach to problems parameterized above or below tight bounds
• Computing the partition function of a polynomial on the Boolean cube
• On the consistent path problem
• scientific article; zbMATH DE number 7650076 (Why is no real title available?)
• A probabilistic approach to problems parameterized above or below tight bounds
• Solving MAX-\(r\)-SAT above a tight lower bound
• Note on Max Lin-2 above average
• Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
• From worst case to the average: structural guarantees in k-CSP approximation via orthogonal arrays
• Optimizing alphabet reduction pairs of arrays

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5894908)