On the public citation graph

Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion

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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/bf02392825openalex-snapshot
Clique is hard to approximate within n1−ε
inferredcites →https://doi.org/10.1016/s0304-3975(02)00535-2openalex-snapshot
Towards optimal lower bounds for clique and chromatic number
inferredcites →https://doi.org/10.1109/ccc.1996.507690openalex-snapshot
Zero knowledge and the chromatic number
inferredcites →https://doi.org/10.1109/ccc.2001.933891openalex-snapshot
Simple analysis of graph tests for linearity and PCP
inferredcites →https://doi.org/10.1109/sfcs.1996.548522openalex-snapshot
Clique is hard to approximate within n/sup 1-ε/
inferredcites →https://doi.org/10.1109/sfcs.2001.959936openalex-snapshot
Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring
inferredcites →https://doi.org/10.1109/sffcs.1999.814620openalex-snapshot
Hardness of approximating the minimum distance of a linear code
inferredcites →https://doi.org/10.1109/tit.2002.806118openalex-snapshot
Hardness of approximating the minimum distance of a linear code
inferredcites →https://doi.org/10.1137/s0097539794266407openalex-snapshot
On Unapproximable Versions of $NP$-Complete Problems
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
inferredcites →https://doi.org/10.1137/s089548010240415xopenalex-snapshot
Approximating Maximum Clique by Removing Subgraphs
inferredcites →https://doi.org/10.1145/1132516.1132519openalex-snapshot
Gowers uniformity, influence of variables, and PCPs
inferredcites →https://doi.org/10.1145/167088.167174openalex-snapshot
Efficient probabilistically checkable proofs and applications to approximations
inferredcites →https://doi.org/10.1145/195058.195128openalex-snapshot
Two prover protocols
inferredcites →https://doi.org/10.1145/195058.195129openalex-snapshot
Improved non-approximability results
inferredcites →https://doi.org/10.1145/225058.225281openalex-snapshot
Randomized graph products, chromatic numbers, and Lovasz j-function
inferredcites →https://doi.org/10.1145/226643.226652openalex-snapshot
Interactive proofs and the hardness of approximating cliques
inferredcites →https://doi.org/10.1145/237814.237820openalex-snapshot
Testing of the long code and hardness for clique
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/273865.273901openalex-snapshot
Probabilistic checking of proofs
inferredcites →https://doi.org/10.1145/278298.278306openalex-snapshot
Proof verification and the hardness of approximation problems
inferredcites →https://doi.org/10.1145/335305.335322openalex-snapshot
The value of strong inapproximability results for clique
inferredcites →https://doi.org/10.1145/335305.335329openalex-snapshot
A PCP characterization of NP with optimal amortized query complexity
inferredcites →https://doi.org/10.1145/380752.380839openalex-snapshot
Non-approximability results for optimization problems on bounded degree instances
inferredcites →https://doi.org/10.1145/509907.510017openalex-snapshot
On the power of unique 2-prover 1-round games
inferredcites →https://doi.org/10.37236/1193openalex-snapshot
The Sandwich Theorem

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-030-60440-0_4openalex-snapshot
Parameterized Inapproximability of Independent Set in H-Free Graphs
inferred← citeshttps://doi.org/10.1007/978-3-031-81396-2_14openalex-snapshot
Approximate Min-Sum Subset Convolution
inferred← citeshttps://doi.org/10.1007/978-3-032-17156-6_20openalex-snapshot
Exact Recovery of Planted Cliques in Semi-random Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-68711-7_4openalex-snapshot
Efficient Rational Proofs for Space Bounded Computations
inferred← citeshttps://doi.org/10.1007/978-3-540-73545-8_9openalex-snapshot
Improved Exact Algorithms for Counting 3- and 4-Colorings
inferred← citeshttps://doi.org/10.1007/978-3-642-04128-0_8openalex-snapshot
Approximability of Sparse Integer Programs
inferred← citeshttps://doi.org/10.1007/978-3-642-31265-6_34openalex-snapshot
On Approximating String Selection Problems with Outliers
inferred← citeshttps://doi.org/10.1007/978-3-642-31594-7_38openalex-snapshot
Streaming and Communication Complexity of Clique Approximation
inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_25openalex-snapshot
New and Improved Bounds for the Minimum Set Cover Problem
inferred← citeshttps://doi.org/10.1007/978-3-662-44777-2_20openalex-snapshot
Nearly Tight Approximability Results for Minimum Biclique Cover and Partition
inferred← citeshttps://doi.org/10.1007/978-3-662-46078-8_2openalex-snapshot
Progress (and Lack Thereof) for Graph Coloring Approximation Problems
inferred← citeshttps://doi.org/10.1007/s00453-010-9431-zopenalex-snapshot
Approximability of Sparse Integer Programs
inferred← citeshttps://doi.org/10.1007/s00453-018-0512-8openalex-snapshot
New Tools and Connections for Exponential-Time Approximation
inferred← citeshttps://doi.org/10.1007/s00453-022-01052-5openalex-snapshot
Parameterized Inapproximability of Independent Set in H-Free Graphs
inferred← citeshttps://doi.org/10.1007/s40305-018-00237-6openalex-snapshot
Competitive and Collaborative Influence in Social Networks
inferred← citeshttps://doi.org/10.1016/j.dam.2008.06.007openalex-snapshot
On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems
inferred← citeshttps://doi.org/10.1016/j.engappai.2015.01.020openalex-snapshot
A GRASP-based memetic algorithm with path relinking for the far from most string problem
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.06.008openalex-snapshot
Finding large cliques in sparse semi-random graphs by simple randomized search heuristics
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.05.037openalex-snapshot
On approximating string selection problems with outliers
inferred← citeshttps://doi.org/10.1017/cbo9780511666209.008openalex-snapshot
On the efficient approximability of constraint satisfaction problems
inferred← citeshttps://doi.org/10.1109/ccc.2009.38openalex-snapshot
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
inferred← citeshttps://doi.org/10.1109/focs.2006.51openalex-snapshot
New Results for Learning Noisy Parities and Halfspaces
inferred← citeshttps://doi.org/10.1109/focs.2008.37openalex-snapshot
Hardness of Minimizing and Learning DNF Expressions
inferred← citeshttps://doi.org/10.1109/focs.2011.62openalex-snapshot
A Two Prover One Round Game with Strong Soundness
inferred← citeshttps://doi.org/10.1109/focs.2012.75openalex-snapshot
Hardness of Finding Independent Sets in Almost q-Colorable Graphs
inferred← citeshttps://doi.org/10.1109/infocom53939.2023.10229078openalex-snapshot
An Approximation for Job Scheduling on Cloud with Synchronization and Slowdown Constraints
inferred← citeshttps://doi.org/10.1137/070684914openalex-snapshot
On Agnostic Learning of Parities, Monomials, and Halfspaces
inferred← citeshttps://doi.org/10.1137/1.9781611973105.112openalex-snapshot
Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More
inferred← citeshttps://doi.org/10.1137/1.9781611973730.1openalex-snapshot
Approximating independent sets in sparse graphs
inferred← citeshttps://doi.org/10.1137/1.9781611977073.61openalex-snapshot
Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
inferred← citeshttps://doi.org/10.1145/1159892.1159901openalex-snapshot
The NP-completeness column
inferred← citeshttps://doi.org/10.1145/1536414.1536457openalex-snapshot
CSP gaps and reductions in the lasserre hierarchy
inferred← citeshttps://doi.org/10.1145/1706591.1706594openalex-snapshot
Amplifying lower bounds by means of self-reducibility
inferred← citeshttps://doi.org/10.1145/2213977.2214004openalex-snapshot
2 log1-ε n hardness for the closest vector problem with preprocessing
inferred← citeshttps://doi.org/10.1145/2611462.2611476openalex-snapshot
Beyond geometry
inferred← citeshttps://doi.org/10.1145/2746539.2746607openalex-snapshot
On the Lovász Theta function for Independent Sets in Sparse Graphs
inferred← citeshttps://doi.org/10.1145/3055399.3055487openalex-snapshot
Algorithms for stable and perturbation-resilient problems
inferred← citeshttps://doi.org/10.1145/3392724openalex-snapshot
Improved Dynamic Graph Coloring
inferred← citeshttps://doi.org/10.1145/3494539openalex-snapshot
Fully Dynamic (Δ +1)-Coloring in O (1) Update Time
inferred← citeshttps://doi.org/10.1145/3564246.3585111openalex-snapshot
Improved Dynamic Colouring of Sparse Graphs
inferred← citeshttps://doi.org/10.1145/3618260.3649606openalex-snapshot
Near Optimal Alphabet-Soundness Tradeoff PCPs
inferred← citeshttps://doi.org/10.17877/de290r-31openalex-snapshot
Design und Analyse randomisierter Suchheuristiken
inferred← citeshttps://doi.org/10.3390/a11010010openalex-snapshot
Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis
inferred← citeshttps://doi.org/10.3929/ethz-b-000378784openalex-snapshot
Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem
inferred← citeshttps://doi.org/10.4086/toc.2011.v007a003openalex-snapshot
inferred← citeshttps://doi.org/10.4086/toc.2013.v009a028openalex-snapshot
inferred← citeshttps://doi.org/10.4086/toc.2015.v011a007openalex-snapshot
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2020.11openalex-snapshot
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models
inferred← citeshttps://doi.org/10.48550/arxiv.1202.2820openalex-snapshot
On Approximating String Selection Problems with Outliers
inferred← citeshttps://doi.org/10.48550/arxiv.1402.5003openalex-snapshot
Beyond Geometry : Towards Fully Realistic Wireless Models
inferred← citeshttps://doi.org/10.48550/arxiv.1910.02063openalex-snapshot
Fully Dynamic $(Δ+1)$-Coloring in Constant Update Time
inferred← citeshttps://doi.org/10.5555/2634074.2634191openalex-snapshot
Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs
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.