Quick Approximation to Matrices and Applications

1999/02/01 by Alan Frieze, Ravi Kannan · 19 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods

paper · doi:10.1007/s004930050052

crossref issued 1999/02/01 · crossref published 1999/02/01 · crossref published-print 1999/02/01 · openalex publication_date 1999/02/01 · crossref created 2002/08/25 · crossref deposited 2019/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31 · crossref indexed 2026/08/03

Citations

• Proof verification and hardness of approximation problems

Cited by

• Approximating the cut-norm via Grothendieck's inequality
• The Cut Metric, Random Graphs, and Branching Processes
• Efficient Learning on Large Graphs using a Densifying Regularity Lemma
• Hardness of fully dense problems
• Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
• How to rank with few errors
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Bounds for graph regularity and removal lemmas
• The counting lemma for regulark‐uniform hypergraphs
• Regularity Lemma for k‐uniform hypergraphs
• The Regularity Lemma and Its Applications in Graph Theory
• A Deterministic Algorithm for the Frieze–Kannan Regularity Lemma
• Szemerédi’s Lemma for the Analyst
• Regularity Lemmas and Combinatorial Algorithms
• Random sampling and approximation of MAX-CSPs
• Subexponential Algorithms for Unique Games and Related Problems
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• Matrix norm [wikipedia]
• Szemerédi regularity lemma [wikipedia]