Spectral techniques applied to sparse random graphs
From MaRDI portal
Publication:5318249
DOI10.1002/RSA.20089zbMATH Open1076.05073OpenAlexW4243880374WikidataQ105583242 ScholiaQ105583242MaRDI QIDQ5318249FDOQ5318249
Authors: Eran Ofek, Uriel Feige 
Publication date: 22 September 2005
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20089
Recommendations
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) Combinatorial probability (60C05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Relations between average case complexity and approximation complexity
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Certifying unsatisfiability of random \(2k\)-SAT formulas using approximation techniques.
Cited In (81)
- Spectral Compressed Sensing via Projected Gradient Descent
- The spectral gap of sparse random digraphs
- Mean-Field Approximations for Stochastic Population Processes with Heterogeneous Interactions
- On an anti-Ramsey threshold for random graphs
- On the Laplacian Eigenvalues of Gn,p
- Community detection and stochastic block models: recent developments
- Spectral statistics of sparse Erdős-Rényi graph Laplacians
- Why almost all \(k\)-colorable graphs are easy to color
- Spectral radii of sparse random matrices
- On semidefinite relaxations for the block model
- Optimal and algorithmic norm regularization of random matrices
- Empirical spectral distributions of sparse random graphs
- Consistency of spectral clustering in stochastic block models
- The Hopfield model on a sparse Erdös-Renyi graph
- Swarming on random graphs. II
- Algebraic and combinatorial expansion in random simplicial complexes
- Efficient Simulation of Sparse Graphs of Point Processes
- Graph partitioning via adaptive spectral techniques
- Spectral norm bounds for block Markov chain random matrices
- Title not available (Why is that?)
- Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
- Analysis of crowdsourced sampling strategies for HodgeRank with sparse random graphs
- The theta number of simplicial complexes
- Clustering in block Markov chains
- Strong consistency, graph Laplacians, and the stochastic block model
- Convex relaxation methods for community detection
- Universality of the mean-field for the Potts model
- Spectral edge in sparse random graphs: upper and lower tail large deviations
- Sparse regular random graphs: spectral density and eigenvectors
- Vertices cannot be hidden from quantum spatial search for almost all random graphs
- Extremal eigenvalues of critical Erdős-Rényi graphs
- Distributed user profiling via spectral methods
- Probability of graphs with large spectral gap by multicanonical Monte Carlo
- Sparse random tensors: concentration, regularization and applications
- Sampling based succinct matrix approximation
- Outliers in spectrum of sparse Wigner matrices
- On the second eigenvalue of random bipartite biregular graphs
- A Simple SVD Algorithm for Finding Hidden Partitions
- On the spectrum of dense random geometric graphs
- The spectra of random mixed graphs
- On the spectra of general random mixed graphs
- Sparse random graphs: eigenvalues and eigenvectors
- Sparse topologies with small spectrum size
- Role of normalization in spectral clustering for stochastic blockmodels
- Spectral algorithms for unique games
- Constructive regularization of the random matrix norm
- Loose Laplacian spectra of random hypergraphs
- Recognizing more random unsatisfiable 3-SAT instances efficiently
- Functional limit theorems for random regular graphs
- Spectral clustering in the dynamic stochastic block model
- Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
- Size biased couplings and the spectral gap for random regular graphs
- Message passing algorithms for MLS-3LIN problem
- Detection thresholds in very sparse matrix completion
- Spectra of edge-independent random graphs
- Fluctuations in mean-field Ising models
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Norms of random matrices: local and global problems
- Faster least squares approximation
- Capacity of an associative memory model on random graph architectures
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- Community detection in sparse networks via Grothendieck's inequality
- An \({\ell_p}\) theory of PCA and spectral clustering
- Finding one community in a sparse graph
- A Global synchronization theorem for oscillators on a random graph
- Title not available (Why is that?)
- Sherali-adams strikes back
- The skew spectral radius and skew Randić spectral radius of general random oriented graphs
- Expansion and Lack Thereof in Randomly Perturbed Graphs
- Simplex links in determinantal hypertrees
- A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
- Second largest eigenpair statistics for sparse graphs
- Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
- Simplicial Kirchhoff index of random complexes
- On the efficacy of higher-order spectral clustering under weighted stochastic block models
- The spectral gap of a random subgraph of a graph
- Title not available (Why is that?)
- Recovering structured probability matrices
- Large Rainbow Cliques in Randomly Perturbed Dense Graphs
- Non-backtracking spectra of weighted inhomogeneous random graphs
- Detecting structured signals in Ising models
Uses Software
This page was built for publication: Spectral techniques applied to sparse random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5318249)
