Decompositions of Triangle-Dense Graphs

DOI10.1137/140955331zbMath1332.05114arXiv1309.7440OpenAlexW2292677754MaRDI QIDQ2796209

Tim Roughgarden, Rishi Gupta, C. Seshadhri

Publication date: 23 March 2016

Published in: SIAM Journal on Computing, Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.7440

zbMATH Keywords

clusteringgraph algorithmssocial and information networks

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Related Items (7)

Unnamed Item ⋮ Finding Cliques in Social Networks: A New Distribution-Free Model ⋮ Unnamed Item ⋮ Regularity lemmas for clustering graphs ⋮ Unnamed Item ⋮ Decompositions of Triangle-Dense Graphs ⋮ Testing for high-dimensional geometry in random graphs

Uses Software

• KronFit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Connected components in random graphs with given expected degree sequences
• From the Cover: The structure of scientific collaboration networks
• Decompositions of Triangle-Dense Graphs
• (Leveled) fully homomorphic encryption without bootstrapping
• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Emergence of Scaling in Random Networks
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• The small-world phenomenon
• Trapdoors for hard lattices and new cryptographic constructions
• Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
• Evaluating Branching Programs on Encrypted Data
• On the Hardness of Optimization in Power Law Graphs
• Bounds for Width Two Branching Programs
• A Separator Theorem for Planar Graphs
• Community structure in social and biological networks
• Wedge sampling for computing clustering coefficients and triangle counts on large graphs^†
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
• Collective dynamics of ‘small-world’ networks
• New lattice-based cryptographic constructions
• The average distances in random graphs with given expected degrees
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Decompositions of Triangle-Dense Graphs