Quick approximation to matrices and applications
From MaRDI portal
Publication:1125616
DOI10.1007/s004930050052zbMath0933.68061OpenAlexW2072858942WikidataQ57401544 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
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, THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND, 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, 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, Testing hypergraph colorability, Sublinear-time Algorithms, An analytic approach to stability, Unnamed Item, Finitely forcible graphons, Sparse graphs: Metrics and random models, Modularity spectra, eigen-subspaces, and structure of weighted graphs, Testing for Dense Subsets in a Graph via the Partition Function, Generalized quasirandom properties of expanding graph sequences, Consistent nonparametric estimation for heavy-tailed sparse graphs, Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems, A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma, On the Average-Case Complexity of Property Testing, Multigraph limits, unbounded kernels, and Banach space decorated graphs, An introduction to large deviations for random graphs, Duality in inhomogeneous random graphs, and the cut metric, Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits, Optimal graphon estimation in cut distance, Stability‐type results for hereditary properties, Weak regularity and finitely forcible graph limits, The Cut Metric for Probability Distributions, On the Query Complexity of Estimating the Distance to Hereditary Graph Properties, Estimating parameters associated with monotone properties, Cycles of length three and four in tournaments, Binary Component Decomposition Part I: The Positive-Semidefinite Case, The quasi-randomness of hypergraph cut properties, Approximating the rectilinear crossing number, Tournaments and Semicomplete Digraphs, Ramsey numbers of books and quasirandomness, Linear embeddings of graphs and graph limits, A randomized approximation scheme for metric MAX-CUT, A relative Szemerédi theorem
