On the public citation graph
Heuristics for Semirandom Graph Problems
0 signed · 172 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/(sici)1098-2418(199701/03)10:1/2<5::aid-rsa2>3.0.co;2-zopenalex-snapshot
Algorithmic theory of random graphs
inferredcites →https://doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-wopenalex-snapshot
Finding a large hidden clique in a random graph
inferredcites →https://doi.org/10.1002/(sici)1098-2418(200003)16:2<195::aid-rsa5>3.0.co;2-aopenalex-snapshot
Finding and certifying a large hidden clique in a semirandom graph
inferredcites →https://doi.org/10.1006/jagm.1995.1034openalex-snapshot
Coloring Random and Semi-Random k-Colorable Graphs
inferredcites →https://doi.org/10.1006/jcss.1998.1587openalex-snapshot
Zero Knowledge and the Chromatic Number
inferredcites →https://doi.org/10.1007/3-540-45687-2_16openalex-snapshot
Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming
inferredcites →https://doi.org/10.1007/bf01196133openalex-snapshot
Randomized graph products, chromatic numbers, and the Lov�sz ?-function
inferredcites →https://doi.org/10.1007/bf01581168openalex-snapshot
Approximating the independence number via theϑ-function
inferredcites →https://doi.org/10.1007/bf01994876openalex-snapshot
Approximating maximum independent sets by excluding subgraphs
inferredcites →https://doi.org/10.1007/bf02392825openalex-snapshot
Clique is hard to approximate within n1−ε
inferredcites →https://doi.org/10.1007/bf02579329openalex-snapshot
The eigenvalues of random symmetric matrices
inferredcites →https://doi.org/10.1016/0020-0190(93)90246-6openalex-snapshot
A still better performance guarantee for approximate graph coloring
inferredcites →https://doi.org/10.1016/s0020-0190(96)00190-1openalex-snapshot
An algorithm for 3-colorable graphs
inferredcites →https://doi.org/10.1109/sfcs.1987.22openalex-snapshot
Eigenvalues and graph bisection: An average-case analysis
inferredcites →https://doi.org/10.1109/sfcs.1988openalex-snapshot
[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
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.2000.892070openalex-snapshot
A polylogarithmic approximation of the minimum bisection
inferredcites →https://doi.org/10.1109/tit.1979.1055985openalex-snapshot
On the Shannon capacity of a graph
inferredcites →https://doi.org/10.1137/0805002openalex-snapshot
Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
inferredcites →https://doi.org/10.1137/0805024openalex-snapshot
Nonpolyhedral Relaxations of Graph-Bisection Problems
inferredcites →https://doi.org/10.1137/s0097539794270248openalex-snapshot
A Spectral Technique for Coloring Random 3-Colorable Graphs
inferredcites →https://doi.org/10.1145/225058.225281openalex-snapshot
Randomized graph products, chromatic numbers, and Lovasz j-function
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/274787.274791openalex-snapshot
Approximate graph coloring by semidefinite programming
inferredcites →https://doi.org/10.1145/335305.335370openalex-snapshot
Approximating the minimum bisection size (extended abstract)
inferredcites →https://doi.org/10.1147/rd.175.0420openalex-snapshot
Lower Bounds for the Partitioning of Graphs
inferredcites →https://doi.org/10.5555/251040.251043openalex-snapshot
Algorithmic theory of random graphs
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/rsa.20007openalex-snapshot
Exact and approximative algorithms for coloring G(n,p)
inferred← citeshttps://doi.org/10.1002/rsa.20089openalex-snapshot
Spectral techniques applied to sparse random graphs
inferred← citeshttps://doi.org/10.1002/rsa.20116openalex-snapshot
A spectral heuristic for bisecting random graphs
inferred← citeshttps://doi.org/10.1002/rsa.20172openalex-snapshot
The diameter of randomly perturbed digraphs and some applications
inferred← citeshttps://doi.org/10.1002/rsa.20181openalex-snapshot
Improved algorithms for the random cluster graph model
inferred← citeshttps://doi.org/10.1007/11538462_24openalex-snapshot
Finding a Maximum Independent Set in a Sparse Random Graph
inferred← citeshttps://doi.org/10.1007/11602613_49openalex-snapshot
Smoothed Analysis of Binary Search Trees
inferred← citeshttps://doi.org/10.1007/11821069_18openalex-snapshot
Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities
inferred← citeshttps://doi.org/10.1007/3-540-36494-3_43openalex-snapshot
Colouring Random Graphs in Expected Polynomial Time
inferred← citeshttps://doi.org/10.1007/3-540-36494-3_45openalex-snapshot
Finding Large Independent Sets in Polynomial Expected Time
inferred← citeshttps://doi.org/10.1007/3-540-44985-x_2openalex-snapshot
Coping with the NP-Hardness of the Graph Bandwidth Problem
inferred← citeshttps://doi.org/10.1007/3-540-45471-3_24openalex-snapshot
Improved Algorithms for the Random Cluster Graph Model
inferred← citeshttps://doi.org/10.1007/3-540-45687-2_16openalex-snapshot
Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming
inferred← citeshttps://doi.org/10.1007/3-540-45726-7_12openalex-snapshot
Finding Sparse Induced Subgraphs of Semirandom Graphs
inferred← citeshttps://doi.org/10.1007/978-3-030-56877-1_6openalex-snapshot
Nearly Optimal Robust Secret Sharing Against Rushing Adversaries
inferred← citeshttps://doi.org/10.1007/978-3-030-64946-3_14openalex-snapshot
Revenue Monotonicity Under Misspecified Bidders
inferred← citeshttps://doi.org/10.1007/978-3-030-83508-8_38openalex-snapshot
Independent Sets in Semi-random Hypergraphs
inferred← citeshttps://doi.org/10.1007/978-3-030-97127-4_1openalex-snapshot
Notes on Computational Hardness of Hypothesis Testing: Predictions Using the Low-Degree Likelihood Ratio
inferred← citeshttps://doi.org/10.1007/978-3-031-06901-7_4openalex-snapshot
The Simultaneous Semi-random Model for TSP
inferred← citeshttps://doi.org/10.1007/978-3-031-93112-3_20openalex-snapshot
Semirandom Planted Clique via 1-Norm Isometry Property
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-0348-8211-8_11openalex-snapshot
Coloring Random Graphs — an Algorithmic Perspective
inferred← citeshttps://doi.org/10.1007/978-3-319-69802-1_4openalex-snapshot
Multisection in the Stochastic Block Model Using Semidefinite Programming
inferred← citeshttps://doi.org/10.1007/978-3-540-27821-4_31openalex-snapshot
The Diameter of Randomly Perturbed Digraphs and Some Applications
inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_34openalex-snapshot
Coloring Semirandom Graphs Optimally
inferred← citeshttps://doi.org/10.1007/978-3-540-30217-9_3openalex-snapshot
Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization
inferred← citeshttps://doi.org/10.1007/978-3-540-45198-3_20openalex-snapshot
The Lovász Number of Random Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_30openalex-snapshot
The Smoothed Complexity of Edit Distance
inferred← citeshttps://doi.org/10.1007/978-3-540-70918-3_11openalex-snapshot
Why Almost All k-Colorable Graphs Are Easy
inferred← citeshttps://doi.org/10.1007/978-3-642-32589-2_20openalex-snapshot
Smoothed Complexity Theory
inferred← citeshttps://doi.org/10.1007/s00224-009-9231-5openalex-snapshot
Why Almost All k-Colorable Graphs Are Easy to Color
inferred← citeshttps://doi.org/10.1007/s00453-012-9646-2openalex-snapshot
PASS Approximation: A Framework for Analyzing and Designing Heuristics
inferred← citeshttps://doi.org/10.1007/s10107-023-02011-wopenalex-snapshot
The simultaneous semi-random model for TSP
inferred← citeshttps://doi.org/10.1007/s10208-016-9341-9openalex-snapshot
Random Laplacian Matrices and Convex Relaxations
inferred← citeshttps://doi.org/10.1007/s10208-025-09707-9openalex-snapshot
Local Geometry Determines Global Landscape in Low-Rank Factorization for Synchronization
inferred← citeshttps://doi.org/10.1007/s10951-005-6811-3openalex-snapshot
A Hard Dial-a-Ride Problem that is Easy on Average
inferred← citeshttps://doi.org/10.1016/j.automatica.2017.06.024openalex-snapshot
Spectral and structural properties of random interdependent networks
inferred← citeshttps://doi.org/10.1016/j.crma.2015.11.009openalex-snapshot
A note on probably certifiably correct algorithms
inferred← citeshttps://doi.org/10.1016/j.ifacol.2015.10.339openalex-snapshot
Robustness and Algebraic Connectivity of Random Interdependent Networks
inferred← citeshttps://doi.org/10.1016/j.ipl.2008.04.011openalex-snapshot
On the tractability of coloring semirandom graphs
inferred← citeshttps://doi.org/10.1016/j.jalgor.2004.07.003openalex-snapshot
Solving NP-hard semirandom graph problems in polynomial expected time
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.02.035openalex-snapshot
Smoothed analysis of binary search trees
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.1017/9781316882177openalex-snapshot
Algorithmic Aspects of Machine Learning
inferred← citeshttps://doi.org/10.1017/9781316882177.003openalex-snapshot
Nonnegative Matrix Factorization
inferred← citeshttps://doi.org/10.1017/9781316882177.004openalex-snapshot
Tensor Decompositions: Algorithms
inferred← citeshttps://doi.org/10.1017/9781316882177.005openalex-snapshot
Tensor Decompositions: Applications
inferred← citeshttps://doi.org/10.1017/s0963548304006303openalex-snapshot
Max Cut for Random Graphs with a Planted Partition
inferred← citeshttps://doi.org/10.1017/s0963548306007553openalex-snapshot
Finding Large Independent Sets in Polynomial Expected Time
inferred← citeshttps://doi.org/10.1017/s0963548306007917openalex-snapshot
Colouring Semirandom Graphs
inferred← citeshttps://doi.org/10.1017/s096354830600798xopenalex-snapshot
On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem
inferred← citeshttps://doi.org/10.1017/s0963548309990514openalex-snapshot
Graph Partitioning via Adaptive Spectral Techniques
inferred← citeshttps://doi.org/10.1073/pnas.1523097113openalex-snapshot
Phase transitions in semidefinite relaxations
inferred← citeshttps://doi.org/10.1093/imaiai/iaaf012openalex-snapshot
Nonconvex landscapes for Z2 synchronization and graph clustering are benign near exact recovery thresholds
inferred← citeshttps://doi.org/10.1109/acssc.2015.7421303openalex-snapshot
Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model
inferred← citeshttps://doi.org/10.1109/focs.2007.59openalex-snapshot
Planning for Fast Connectivity Updates
inferred← citeshttps://doi.org/10.1109/focs.2011.78openalex-snapshot
How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00022openalex-snapshot
List Decodable Mean Estimation in Nearly Linear Time
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00058openalex-snapshot
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00046openalex-snapshot
Robust recovery for stochastic block models
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00083openalex-snapshot
Minimax Rates for Robust Community Detection
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00026openalex-snapshot
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00064openalex-snapshot
Semirandom Planted Clique and the Restricted Isometry Property
inferred← citeshttps://doi.org/10.1109/icassp.2019.8682223openalex-snapshot
Exact Recovery by Semidefinite Programming in the Binary Stochastic Block Model with Partially Revealed Side Information
inferred← citeshttps://doi.org/10.1109/isit.2019.8849686openalex-snapshot
Community Detection with Side Information via Semidefinite Programming
inferred← citeshttps://doi.org/10.1109/isit63088.2025.11195596openalex-snapshot
Semidefinite Programming for the Asymmetric Stochastic Block Model
inferred← citeshttps://doi.org/10.1109/jsait.2020.3037170openalex-snapshot
Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
inferred← citeshttps://doi.org/10.1109/sampta.2017.8024399openalex-snapshot
A semidefinite program for unbalanced multisection in the stochastic block model
inferred← citeshttps://doi.org/10.1109/smartnets50376.2021.9555421openalex-snapshot
Node Clustering in Binary Asymmetric Stochastic Block Model with Noisy Label Attributes via SDP
inferred← citeshttps://doi.org/10.1109/tit.2016.2546280openalex-snapshot
Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
inferred← citeshttps://doi.org/10.1109/tit.2016.2594812openalex-snapshot
Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
inferred← citeshttps://doi.org/10.1109/tit.2018.2839677openalex-snapshot
Exponential Error Rates of SDP for Block Models: Beyond Grothendieck’s Inequality
inferred← citeshttps://doi.org/10.1109/tit.2020.2966438openalex-snapshot
Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
inferred← citeshttps://doi.org/10.1109/tnse.2021.3078612openalex-snapshot
Semidefinite Programming for Community Detection With Side Information
inferred← citeshttps://doi.org/10.1137/1.9781611972962.4openalex-snapshot
Semirandom Models as Benchmarks for Coloring Algorithms
inferred← citeshttps://doi.org/10.1137/1.9781611973402.67openalex-snapshot
Bilu–Linial Stable Instances of Max Cut and Minimum Multiway Cut
inferred← citeshttps://doi.org/10.1137/1.9781611975994.45openalex-snapshot
A New Algorithm for the Robust Semi-random Independent Set Problem
inferred← citeshttps://doi.org/10.1137/1.9781611976465.28openalex-snapshot
Strongly refuting all semi-random Boolean CSPs
inferred← citeshttps://doi.org/10.1137/1.9781611976465.79openalex-snapshot
Local Statistics, Semidefinite Programming, and Community Detection
inferred← citeshttps://doi.org/10.1137/151002496openalex-snapshot
Smoothed Analysis on Connected Graphs
inferred← citeshttps://doi.org/10.1137/18m1217644openalex-snapshot
On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
inferred← citeshttps://doi.org/10.1137/23m1545203openalex-snapshot
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs
inferred← citeshttps://doi.org/10.1137/24m1680489openalex-snapshot
Finding Planted Cliques Using Gradient Descent
inferred← citeshttps://doi.org/10.1142/s0129054123470020openalex-snapshot
Online Predictions for Online TSP on the Line
inferred← citeshttps://doi.org/10.1145/1060590.1060656openalex-snapshot
On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem
inferred← citeshttps://doi.org/10.1145/1143997.1144099openalex-snapshot
How randomized search heuristics find maximum cliques in planar graphs
inferred← citeshttps://doi.org/10.1145/2213977.2214013openalex-snapshot
Approximation algorithms for semi-random partitioning problems
inferred← citeshttps://doi.org/10.1145/2344422.2344434openalex-snapshot
The smoothed complexity of edit distance
inferred← citeshttps://doi.org/10.1145/2591796.2591841openalex-snapshot
Constant factor approximation for balanced cut in the PIE model
inferred← citeshttps://doi.org/10.1145/2688073.2688082openalex-snapshot
The Computational Benefit of Correlated Instances
inferred← citeshttps://doi.org/10.1145/2897518.2897561openalex-snapshot
On the effect of randomness on planted 3-coloring models
inferred← citeshttps://doi.org/10.1145/2897518.2897573openalex-snapshot
How robust are reconstruction thresholds for community detection?
inferred← citeshttps://doi.org/10.1145/3519935.3519989openalex-snapshot
Testing thresholds for high-dimensional sparse random geometric graphs
inferred← citeshttps://doi.org/10.1145/3564246.3585184openalex-snapshot
Algorithms Approaching the Threshold for Semi-random Planted Clique
inferred← citeshttps://doi.org/10.1145/3618260.3649761openalex-snapshot
Robust Recovery for Stochastic Block Models, Simplified and Generalized
inferred← citeshttps://doi.org/10.1145/3717823.3718137openalex-snapshot
Rounding Large Independent Sets on Expanders
inferred← citeshttps://doi.org/10.1145/3770855.3818135openalex-snapshot
Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries
inferred← citeshttps://doi.org/10.1162/evco_a_00032openalex-snapshot
Finding Mount Everest and Handling Voids
inferred← citeshttps://doi.org/10.1287/moor.2021.1216openalex-snapshot
Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
inferred← citeshttps://doi.org/10.1287/moor.2022.0201openalex-snapshot
Rank-One Boolean Tensor Factorization and the Multilinear Polytope
inferred← citeshttps://doi.org/10.1561/0100000067openalex-snapshot
Community Detection and Stochastic Block Models
inferred← citeshttps://doi.org/10.17877/de290r-31openalex-snapshot
Design und Analyse randomisierter Suchheuristiken
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.4230/lipics.approx-random.2015.710openalex-snapshot
The Minimum Bisection in the Planted Bisection Model
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2019.28openalex-snapshot
Approximation Algorithms for Partially Colorable Graphs
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2019.23openalex-snapshot
Planted Models for $k$-way Edge and Vertex Expansion
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2020.27openalex-snapshot
Planted Models for the Densest $k$-Subgraph Problem
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2013.526openalex-snapshot
On the practically interesting instances of MAXCUT
inferred← citeshttps://doi.org/10.48550/arxiv.0806.4652openalex-snapshot
A Fixed-Parameter Algorithm for Random Instances of Weighted d-CNF Satisfiability
inferred← citeshttps://doi.org/10.48550/arxiv.1104.3806openalex-snapshot
How to Play Unique Games against a Semi-Random Adversary
inferred← citeshttps://doi.org/10.48550/arxiv.1104.4803openalex-snapshot
Clustering Partially Observed Graphs via Convex Optimization
inferred← citeshttps://doi.org/10.48550/arxiv.1205.2234openalex-snapshot
Approximation Algorithms for Semi-random Graph Partitioning Problems
inferred← citeshttps://doi.org/10.48550/arxiv.1406.5665openalex-snapshot
Constant Factor Approximation for Balanced Cut in the PIE model
inferred← citeshttps://doi.org/10.48550/arxiv.1409.5834openalex-snapshot
Tight Error Bounds for Structured Prediction
inferred← citeshttps://doi.org/10.48550/arxiv.1412.6156openalex-snapshot
Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
inferred← citeshttps://doi.org/10.48550/arxiv.1602.04426openalex-snapshot
On the low-rank approach for semidefinite programs arising in synchronization and community detection
inferred← citeshttps://doi.org/10.48550/arxiv.1606.05374openalex-snapshot
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction
inferred← citeshttps://doi.org/10.48550/arxiv.1803.10846openalex-snapshot
Non-Convex Matrix Completion Against a Semi-Random Adversary
inferred← citeshttps://doi.org/10.48550/arxiv.1804.10696openalex-snapshot
Low Rank Approximation in the Presence of Outliers
inferred← citeshttps://doi.org/10.48550/arxiv.1908.06130openalex-snapshot
Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
inferred← citeshttps://doi.org/10.48550/arxiv.1911.07352openalex-snapshot
Robust Algorithms for the Secretary Problem
inferred← citeshttps://doi.org/10.48550/arxiv.2005.08099openalex-snapshot
Reducibility and Statistical-Computational Gaps from Secret Leakage
inferred← citeshttps://doi.org/10.48550/arxiv.2008.01722openalex-snapshot
Fast and Near-Optimal Diagonal Preconditioning
inferred← citeshttps://doi.org/10.48550/arxiv.2012.02243openalex-snapshot
Average-Case Integrality Gap for Non-Negative Principal Component Analysis
inferred← citeshttps://doi.org/10.5555/1283383.1283495openalex-snapshot
Spectral clustering with limited independence
inferred← citeshttps://doi.org/10.5555/2634074.2634141openalex-snapshot
Bilu-linial stable instances of max cut and minimum multiway cut
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.