On the public citation graph
SDP gaps and UGC-hardness for MAXCUTGAIN
0 signed · 78 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/rsa.20031openalex-snapshot
On the advantage over a random assignment
inferredcites →https://doi.org/10.1006/inco.2000.3011openalex-snapshot
On Weighted vs Unweighted Versions of Combinatorial Optimization Problems
inferredcites →https://doi.org/10.1007/11523468_84openalex-snapshot
A Better Approximation Ratio for the Vertex Cover Problem
inferredcites →https://doi.org/10.1007/3-540-48224-5_18openalex-snapshot
The RPR 2 Rounding Technique for Semidefinite Programs
inferredcites →https://doi.org/10.1007/978-3-0348-8362-7_15openalex-snapshot
Relaxations of Quadratic Programs in Operator Theory and System Analysis
inferredcites →https://doi.org/10.1007/978-3-540-27821-4_11openalex-snapshot
On Systems of Linear Equations with Two Variables per Equation
inferredcites →https://doi.org/10.1007/978-3-642-20212-4openalex-snapshot
Probability in Banach Spaces: Isoperimetry and Processes
inferredcites →https://doi.org/10.1007/bf00532234openalex-snapshot
Geometric bounds on the Ornstein-Uhlenbeck velocity process
inferredcites →https://doi.org/10.1007/bf02790792openalex-snapshot
A new upper bound for the complex Grothendieck constant
inferredcites →https://doi.org/10.1007/s00037-006-0210-9openalex-snapshot
ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT
inferredcites →https://doi.org/10.1007/s00208-005-0745-0openalex-snapshot
Nonembeddability theorems via Fourier analysis
inferredcites →https://doi.org/10.1007/s101070050100openalex-snapshot
On maximization of quadratic form over intersection of ellipsoids with common center
inferredcites →https://doi.org/10.1016/0001-8708(79)90017-3openalex-snapshot
Constantes de Grothendieck et fonctions de type positif sur les sphères
inferredcites →https://doi.org/10.1016/j.jalgor.2004.11.003openalex-snapshot
The RPR2 rounding technique for semidefinite programs
inferredcites →https://doi.org/10.1016/j.jcss.2007.06.019openalex-snapshot
Vertex cover might be hard to approximate to within 2−ε
inferredcites →https://doi.org/10.1023/b:mach.0000033116.57574.95openalex-snapshot
Correlation Clustering
inferredcites →https://doi.org/10.1109/ccc.2002.1004334openalex-snapshot
On the power of unique 2-prover 1-round games
inferredcites →https://doi.org/10.1109/ccc.2003.1214437openalex-snapshot
Vertex cover might be hard to approximate to within 2-ε
inferredcites →https://doi.org/10.1109/focs.2004.39openalex-snapshot
Maximizing Quadratic Programs: Extending Grothendieck's Inequality
inferredcites →https://doi.org/10.1109/sfcs.1995.492573openalex-snapshot
Free bits, PCPs and non-approximability-towards tight results
inferredcites →https://doi.org/10.1109/sfcs.2005.57openalex-snapshot
On Non-Approximability for Quadratic Programs
inferredcites →https://doi.org/10.1109/sfcs.2005.74openalex-snapshot
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1
inferredcites →https://doi.org/10.1137/s0097539704441629openalex-snapshot
Approximating the Cut-Norm via Grothendieck's Inequality
inferredcites →https://doi.org/10.1137/s0097539705447372openalex-snapshot
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
inferredcites →https://doi.org/10.1137/s0097539796302531openalex-snapshot
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
inferredcites →https://doi.org/10.1137/s0097539797328847openalex-snapshot
Gadgets, Approximation, and Linear Programming
inferredcites →https://doi.org/10.1145/1007352.1007355openalex-snapshot
Expander flows, geometric embeddings and graph partitioning
inferredcites →https://doi.org/10.1145/1060590.1060675openalex-snapshot
O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
inferredcites →https://doi.org/10.1145/1109557.1109669openalex-snapshot
Improved lower bounds for embeddings into L 1
inferredcites →https://doi.org/10.1145/1132516.1132547openalex-snapshot
Near-optimal algorithms for unique games
inferredcites →https://doi.org/10.1145/1132516.1132567openalex-snapshot
Conditional hardness for approximate coloring
inferredcites →https://doi.org/10.1145/1374376.1374425openalex-snapshot
An optimal sdp algorithm for max-cut, and equally optimal long code tests
inferredcites →https://doi.org/10.1145/1597036.1597045openalex-snapshot
A better approximation ratio for the vertex cover problem
inferredcites →https://doi.org/10.1145/227683.227684openalex-snapshot
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/380752.380837openalex-snapshot
On the integrality ratio of semidefinite relaxations of MAX CUT
inferredcites →https://doi.org/10.1145/509907.510017openalex-snapshot
On the power of unique 2-prover 1-round games
inferredcites →https://doi.org/10.48550/arxiv.math/0310476openalex-snapshot
A Szemeredi-type regularity lemma in abelian groups, with applications
inferredcites →https://doi.org/10.48550/arxiv.math/0503503openalex-snapshot
Noise stability of functions with low influences: invariance and optimality
inferredcites →https://doi.org/10.5555/1109557.1109669openalex-snapshot
Improved lower bounds for embeddings into L1
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/9781118600207.ch13openalex-snapshot
Inapproximability of Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1002/9781119005353.ch13openalex-snapshot
Inapproximability of Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1007/978-3-319-28031-8_44openalex-snapshot
Online Pairwise Ranking Based on Graph Edge–Connectivity
inferred← citeshttps://doi.org/10.1007/978-3-642-13036-6_23openalex-snapshot
Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
inferred← citeshttps://doi.org/10.1007/978-3-642-31594-7_10openalex-snapshot
On Quadratic Programming with a Ratio Objective
inferred← citeshttps://doi.org/10.1017/cbo9781139814782openalex-snapshot
Analysis of Boolean Functions
inferred← citeshttps://doi.org/10.1109/ccc.2007.39openalex-snapshot
Understanding Parallel Repetition Requires Understanding Foams
inferred← citeshttps://doi.org/10.1109/ccc.2008.20openalex-snapshot
Approximation Resistant Predicates from Pairwise Independence
inferred← citeshttps://doi.org/10.1109/ccc.2010.19openalex-snapshot
On the Unique Games Conjecture (Invited Survey)
inferred← citeshttps://doi.org/10.1109/focs.2007.20openalex-snapshot
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies
inferred← citeshttps://doi.org/10.1109/focs.2007.41openalex-snapshot
Towards Sharp Inapproximability For Any 2-CSP
inferred← citeshttps://doi.org/10.1109/focs.2007.4389503openalex-snapshot
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies
inferred← citeshttps://doi.org/10.1109/focs.2007.47openalex-snapshot
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
inferred← citeshttps://doi.org/10.1109/focs.2007.65openalex-snapshot
On the Advantage over Random for Maximum Acyclic Subgraph
inferred← citeshttps://doi.org/10.1109/focs.2007.73openalex-snapshot
Towards Sharp Inapproximability For Any 2-CSP
inferred← citeshttps://doi.org/10.1109/sfcs.2005.22openalex-snapshot
Approximation Algorithms for Unique Games
inferred← citeshttps://doi.org/10.1137/070711670openalex-snapshot
Towards Sharp Inapproximability for Any 2-CSP
inferred← citeshttps://doi.org/10.1145/1250790.1250818openalex-snapshot
Balanced max 2-sat might not be the hardest
inferred← citeshttps://doi.org/10.1145/1374376.1374379openalex-snapshot
Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling
inferred← citeshttps://doi.org/10.1145/1374376.1374414openalex-snapshot
Optimal algorithms and inapproximability results for every CSP?
inferred← citeshttps://doi.org/10.1145/1374376.1374425openalex-snapshot
An optimal sdp algorithm for max-cut, and equally optimal long code tests
inferred← citeshttps://doi.org/10.1145/1536414.1536452openalex-snapshot
Max cut and the smallest eigenvalue
inferred← citeshttps://doi.org/10.1145/1536414.1536482openalex-snapshot
Conditional hardness for satisfiable 3-CSPs
inferred← citeshttps://doi.org/10.1145/3564246.3585248openalex-snapshot
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
inferred← citeshttps://doi.org/10.1287/moor.1090.0425openalex-snapshot
The UGC Hardness Threshold of the L p Grothendieck Problem
inferred← citeshttps://doi.org/10.4310/cdm.2019.v2019.n1.a2openalex-snapshot
On the proof of the 2-to-2 Games Conjecture
inferred← citeshttps://doi.org/10.48550/arxiv.0806.1978openalex-snapshot
Max Cut and the Smallest Eigenvalue
inferred← citeshttps://doi.org/10.5555/1496770.1496811openalex-snapshot
3-bit dictator testing: 1 vs. 5/8
inferred← citeshttps://doi.org/10.5555/1496770.1496828openalex-snapshot
Towards computing the Grothendieck constant
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.