Quick approximation to matrices and applications
From MaRDI portal
Publication:1125616
DOI10.1007/S004930050052zbMath0933.68061DBLPjournals/combinatorica/FriezeK99OpenAlexW2072858942WikidataQ57401544 ScholiaQ57401544MaRDI QIDQ1125616
Ravindran Kannan, Alan M. Frieze
Publication date: 8 December 1999
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930050052
Related Items (only showing first 100 items - show all)
Removal lemmas and approximate homomorphisms ⋮ Rectilinear approximation and volume estimates for hereditary bodies via [0, 1‐decorated containers] ⋮ A unified view of graph regularity via matrix decompositions ⋮ Lower tails via relative entropy ⋮ Graph sequences sampled from Robinson graphons ⋮ Local-vs-global combinatorics ⋮ An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions ⋮ Asymptotic Structure of Graphs with the Minimum Number of Triangles ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ An Algorithmic Regularity Lemma for $L_p$ Regular Sparse Matrices ⋮ Regularity lemmas in a Banach space setting ⋮ The hypergraph regularity method and its applications ⋮ Norm convergence of multiple ergodic averages for commuting transformations ⋮ Non-Deterministic Graph Property Testing ⋮ Quadratic forms on graphs ⋮ On the continuum limit of epidemiological models on graphs: convergence and approximation results ⋮ THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND ⋮ Testing versus estimation of graph properties, revisited ⋮ Covariance loss, Szemeredi regularity, and differential privacy ⋮ Cycles of length three and four in tournaments ⋮ On the variational problem for upper tails in sparse random graphs ⋮ A note on permutation regularity ⋮ Partitioning problems in dense hypergraphs ⋮ Testing subgraphs in directed graphs ⋮ The cut metric, random graphs, and branching processes ⋮ Regular decomposition of the edge set of a graph with applications ⋮ Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties ⋮ Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach ⋮ On the Complexity of Robust PCA and ℓ1-Norm Low-Rank Matrix Approximation ⋮ A fast new algorithm for weak graph regularity ⋮ An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions ⋮ The regularity method for graphs with few 4‐cycles ⋮ Cut distance identifying graphon parameters over weak* limits ⋮ Random graphons and a weak Positivstellensatz for graphs ⋮ Finitely forcible graph limits are universal ⋮ Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Random sampling and approximation of MAX-CSPs ⋮ On characterizing hypergraph regularity ⋮ Symmetric Graph Properties Have Independent Edges ⋮ The Bipartite QUBO ⋮ Integer and fractional packings in dense 3‐uniform hypergraphs ⋮ Szemerédi's regularity lemma via martingales ⋮ Gaussian bounds for noise correlation of functions ⋮ Simulating Auxiliary Inputs, Revisited ⋮ Convex Relaxations for Permutation Problems ⋮ An improved combinatorial algorithm for Boolean matrix multiplication ⋮ Symmetric graph properties have independent edges ⋮ Regularity Lemma for k-uniform hypergraphs ⋮ Weak regularity and finitely forcible graph limits ⋮ Non-bipartite \(k\)-common graphs ⋮ Cut norm discontinuity of triangular truncation of graphons ⋮ Hardness of fully dense problems ⋮ Additive approximation for edge-deletion problems ⋮ Limits of dense graph sequences ⋮ On replica symmetry of large deviations in random graphs ⋮ Hypergraph limits: A regularity approach ⋮ Integer and fractional packings of hypergraphs ⋮ A noncommutative approach to the graphon Fourier transform ⋮ Uniformity norms, their weaker versions, and applications ⋮ Approximation algorithms for discrete polynomial optimization ⋮ The Ramsey-Turán problem for cliques ⋮ Bounds for graph regularity and removal lemmas ⋮ From quasirandom graphs to graph limits and graphlets ⋮ SVD, discrepancy, and regular structure of contingency tables ⋮ Compact orbit spaces in Hilbert spaces and limits of edge-colouring models ⋮ The resistance perturbation distance: a metric for the analysis of dynamic networks ⋮ Γ-limit of the cut functional on dense graph sequences ⋮ Linear algebraic methods in communication complexity ⋮ Approximating the Rectilinear Crossing Number ⋮ Poset limits and exchangeable random posets ⋮ Testability of minimum balanced multiway cut densities ⋮ Unnamed Item ⋮ Estimating and understanding exponential random graph models ⋮ Convergent sequences of dense graphs. II. Multiway cuts and statistical physics ⋮ Finitely forcible graphons with an almost arbitrary structure ⋮ Limits of randomly grown graph sequences ⋮ The large deviation principle for the Erdős-Rényi random graph ⋮ Limits of kernel operators and the spectral regularity lemma ⋮ Differential calculus on the space of countable labelled graphs ⋮ Hyperfinite graphings and combinatorial optimization ⋮ A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds ⋮ Unnamed Item ⋮ Identifiability for Graphexes and the Weak Kernel Metric ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ FORCING QUASIRANDOMNESS WITH TRIANGLES ⋮ A sparse regular approximation lemma ⋮ Sparse random graphs with clustering ⋮ Bethe states of random factor graphs ⋮ Noisy random graphs and their laplacians ⋮ Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices ⋮ Approximating sparse binary matrices in the cut-norm ⋮ Graph summarization with quality guarantees ⋮ Hypergraph Independent Sets ⋮ Graph Partitioning via Adaptive Spectral Techniques ⋮ An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence ⋮ Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing ⋮ Linear dependence between hereditary quasirandomness conditions ⋮ The critical window for the classical Ramsey-Turán problem ⋮ Sparse exchangeable graphs and their limits via graphon processes ⋮ Spin systems on Bethe lattices
This page was built for publication: Quick approximation to matrices and applications
