On the advantage over a random assignment

No abstract is available for this paper.

• Publication year

  2002

• Venue

  Symposium on the Theory of Computing

• Publication date

  2002-05-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/509907.509916
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Probabilistic Method

  2015cited by this paper
• Algorithms with large domination ratio

  2004cited by this paper
• The Probabilistic Method: Alon/Probabilistic Method

  2004cited by this paper
• Towards optimal lower bounds for clique and chromatic number

  2003cited by this paper
• Hardness results for approximate hypergraph coloring

  2002influential reference
• Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring

  2001cited by this paper
• Some optimal inapproximability results

  2001influential reference
• Noise-tolerant learning, the parity problem, and the statistical query model

  2000cited by this paper
• Clique Is Hard to Approximate within n1-o(1)

  2000cited by this paper
• The Probabilistic Method

  1998cited by this paper
• Probabilistic checking of proofs: a new characterization of NP

  1998cited by this paper
• Clique is hard to approximate within n 1 − ǫ

  1996cited by this paper
• Free bits, PCPs and non-approximability-towards tight results

  1995cited by this paper
• A parallel repetition theorem

  1995influential reference
• The complexity of approximating a nonlinear program

  1995influential reference
• Proof verification and hardness of approximation problems

  1992cited by this paper
• Inequalities in Fourier analysis

  1975cited by this paper
• Étude des coefficients de Fourier des fonctions de $L^p(G)$

  1970cited by this paper
• Ramanujan Graphs

  1965influential reference

• New SDP Roundings and Certifiable Approximation for Cubic Optimization

  2023cites this paper
• HamLib: A Library of Hamiltonians for Benchmarking Quantum Algorithms and Hardware

  2023cites this paper
• On the Consistent Path Problem

  2020cites this paper
• Proposal On the Approximability of Injective Tensor Norms

  2019cites this paper
• Improved 3LIN Hardness via Linear Label Cover

  2019cites this paper
• Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad

  2019influential citation
• How Far From a Worst Solution a Random Solution of a kCSP Instance Can Be?

  2018influential citation
• Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

  2016cites this paper
• Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere

  2016cites this paper
• Dynamical Systems and Interaction Networks

  2016cites this paper
• Kernelization: MaxLin Above Average.

  2016cites this paper
• Computing the partition function of a polynomial on the Boolean cube

  2015cites this paper
• Beating the random assignment on constraint satisfaction problems of bounded degree

  2015cites this paper
• Satisfying more than half of a system of linear equations over GF(2): A multivariate approach

  2014cites this paper
• Kernelization Methods for Fixed-Parameter Tractability

  2014cites this paper
• Algorithms for parameterized constraint satisfaction problems

  2013influential citation
• Multipartite entanglement in XOR games

  2013influential citation
• A Complete Bibliography of The Bell System Technical Journal , 1960 – 1969

  2013cites this paper
• Kernelization - Preprocessing with a Guarantee

  2012cites this paper
• A Probabilistic Approach to Problems Parameterized above or below Tight Bounds a Probabilistic Approach to Problems Parameterized above or below Tight Bounds

  2011cites this paper
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey

  2011cites this paper
• Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average

  2011cites this paper
• Grothendieck inequalities , nonlocal games and optimization

  2011cites this paper
• Simultaneously Satisfying Linear Equations Over $\mathbb{F}_2$: MaxLin2 and Max-$r$-Lin2 Parameterized Above Average

  2011influential citation
• Grothendieck Inequalities, Nonlocal Games and Optimization

  2011cites this paper
• UvA-DARE ( Digital Academic Repository ) Grothendieck inequalities , nonlocal games and optimization

  2011cites this paper
• Grothendieck‐Type Inequalities in Combinatorial Optimization

  2011cites this paper
• Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width

  2011cites this paper
• Algorithms in moderately exponential time

  2010cites this paper
• Parameterized algorithms on digraph and constraint satisfaction problems

  2010cites this paper
• Systems of Linear Equations over F2 and Problems Parameterized above Average

  2010cites this paper
• The Approximability of Learning and Constraint Satisfaction Problems

  2010cites this paper
• PARAMETERIZING FROM THE EXTREMES: FEASIBLE PARAMETERIZATIONS OF SOME NP-OPTIMIZATION PROBLEMS

  2010cites this paper
• A probabilistic approach to problems parameterized above or below tight bounds

  2009cites this paper
• Ordinal Embedding Relaxations Parameterized Above Tight Lower Bound

  2009cites this paper
• MULTIPLAYER XOR GAMES AND QUANTUM COMMUNICATION COMPLEXITY WITH CLIQUE-WISE ENTANGLEMENT

  2009cites this paper
• A Probabilistic Approach to Problems Parameterized Above Tight Lower Bound

  2009cites this paper
• Betweenness parameterized above tight lower bound

  2009influential citation
• Parameterizing above or below guaranteed values

  2009cites this paper
• A Probabilistic Approach to Problems Parameterized Above or Below Tight Lower Bounds

  2009influential citation
• Solving MAX-r-SAT Above a Tight Lower Bound

  2009cites this paper
• D S ] 1 8 A ug 2 00 9 A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds ∗

  2009influential citation
• Note on Max Lin-2 above Average

  2009influential citation
• Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies

  2008influential citation
• An optimal sdp algorithm for max-cut, and equally optimal long code tests

  2008cites this paper
• Quadratic forms on graphs and their applications

  2008cites this paper
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem

  2007cites this paper
• Strongly History-Independent Hashing with Applications

  2007influential citation
• Superresolution and P-Optimality in Boolean MAX-CSP Solvers

  2007cites this paper
• On the Advantage over Random for Maximum Acyclic Subgraph

  2007cites this paper
• Confronting hardness using a hybrid approach

  2006influential citation
• Parameterizing MAX SNP Problems Above Guaranteed Values

  2006cites this paper
• SDP gaps and UGC-hardness for MAXCUTGAIN

  2006cites this paper
• Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems

  2005cites this paper
• Algorithms with large domination ratio

  2004influential citation
• Defying hardness with a hybrid approach

  2004influential citation
• Maximizing quadratic programs: extending Grothendieck's inequality

  2004cites this paper
• Algorithm selection for orthogonal complexity measures

  2004influential citation
• Hardness results for approximate hypergraph coloring

  2002influential citation
• Algorithms with large domination ratio

  year unknowncites this paper