On the public citation graph
Smoothed Analysis of Local Search for the Maximum-Cut Problem
0 signed · 35 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.1007/978-3-642-10631-6_103openalex-snapshot
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences
inferredcites →https://doi.org/10.1007/s00453-013-9801-4openalex-snapshot
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
inferredcites →https://doi.org/10.1007/s00454-011-9340-1openalex-snapshot
k-means Requires Exponentially Many Iterations Even in the Plane
inferredcites →https://doi.org/10.1016/j.tcs.2012.02.033openalex-snapshot
Convergence and approximation in potential games
inferredcites →https://doi.org/10.1016/s0022-0000(05)80063-7openalex-snapshot
On the complexity of the parity argument and other inefficient proofs of existence
inferredcites →https://doi.org/10.1109/focs.2006.55openalex-snapshot
On the Impact of Combinatorial Structure on Congestion Games
inferredcites →https://doi.org/10.1137/0220004openalex-snapshot
Simple Local Search Problems that are Hard to Solve
inferredcites →https://doi.org/10.1137/070683921openalex-snapshot
Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
inferredcites →https://doi.org/10.1145/1007352.1007445openalex-snapshot
The complexity of pure Nash equilibria
inferredcites →https://doi.org/10.1145/1386790.1386832openalex-snapshot
Fast convergence to nearly optimal solutions in potential games
inferredcites →https://doi.org/10.1145/1807342.1807353openalex-snapshot
Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games
inferredcites →https://doi.org/10.1145/2027216.2027217openalex-snapshot
Smoothed Analysis of the k-Means Method
inferredcites →https://doi.org/10.1145/990308.990310openalex-snapshot
Smoothed analysis of algorithms
inferredcites →https://doi.org/10.1524/itit.2011.0654openalex-snapshot
Smoothed Analysis: Analysis of Algorithms Beyond Worst Case
inferredcites →https://doi.org/10.20382/jocg.v4i1a5openalex-snapshot
Worst-case and smoothed analysis of k-means clustering with Bregman divergences
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-64348-5_14openalex-snapshot
Smoothed Analysis of Leader Election in Distributed Networks
inferred← citeshttps://doi.org/10.1007/s00500-023-09230-5openalex-snapshot
Finding local Max-Cut in graphs in randomized polynomial time
inferred← citeshttps://doi.org/10.1007/s10107-020-01577-zopenalex-snapshot
Smoothed analysis for tensor methods in unsupervised learning
inferred← citeshttps://doi.org/10.1016/j.aam.2023.102489openalex-snapshot
Phase transition of degeneracy in minor-closed families
inferred← citeshttps://doi.org/10.1063/1.5020662openalex-snapshot
Local optima of the Sherrington-Kirkpatrick Hamiltonian
inferred← citeshttps://doi.org/10.1109/access.2020.2983473openalex-snapshot
A Fast Efficient Local Search-Based Algorithm for Multi-Objective Supply Chain Configuration Problem
inferred← citeshttps://doi.org/10.1109/focs.2018.00023openalex-snapshot
PPP-Completeness with Connections to Cryptography
inferred← citeshttps://doi.org/10.1109/focs.2019.00043openalex-snapshot
Smoothed Analysis in Unsupervised Learning via Decoupling
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00099openalex-snapshot
Smoothing the gap between NP and ER
inferred← citeshttps://doi.org/10.1137/20m1385287openalex-snapshot
Smoothing the Gap Between NP and ER
inferred← citeshttps://doi.org/10.1137/21m1430042openalex-snapshot
Settling the Complexity of Nash Equilibrium in Congestion Games
inferred← citeshttps://doi.org/10.1145/3188745.3188968openalex-snapshot
A converse to Banach's fixed point theorem and its CLS-completeness
inferred← citeshttps://doi.org/10.1145/3357713.3384325openalex-snapshot
Smoothed complexity of local max-cut and binary max-CSP
inferred← citeshttps://doi.org/10.1145/3564246.3585220openalex-snapshot
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
inferred← citeshttps://doi.org/10.1145/3670865.3673615openalex-snapshot
A Smoothed FPTAS for Equilibria in Congestion Games
inferred← citeshttps://doi.org/10.1287/moor.2024.0610openalex-snapshot
On the Smoothed Complexity of Combinatorial Local Search
inferred← citeshttps://doi.org/10.2139/ssrn.7370109openalex-snapshot
Pivoting Local Max-Cut: Deactivation Fan-Out and Subpolynomial Degree
inferred← citeshttps://doi.org/10.3788/col202523.032501openalex-snapshot
Smoothed analysis-based noise manipulation for spatial photonic Ising machines
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.