Interactive proofs for social graphs

DOI10.1007/978-3-030-56877-1_20zbMath1504.91217OpenAlexW3048591856MaRDI QIDQ2102081

Clara Shikhelman, Liran Katzir, Eylon Yogev

Publication date: 7 December 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-56877-1_20

zbMATH Keywords

interactive proofssuccinct argumentssocial graphs

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Calculating statistics of complex networks through random walks with an application to the on-line social network bebo
• Renormalization group analysis of the small-world network model
• Fiat-Shamir and correlation intractability from strong KDM-secure encryption
• From obfuscation to the security of Fiat-Shamir for proofs
• Fast approximate probabilistically checkable proofs
• Interactive Oracle Proofs
• The small-world phenomenon
• An Efficient Parallel Repetition Theorem
• Random sampling from a search engine's index
• Polylogarithmic independence fools AC ⁰ circuits
• How To Prove Yourself: Practical Solutions to Identification and Signature Problems
• The Knowledge Complexity of Interactive Proof Systems
• Computationally Sound Proofs
• On polynomial approximations to AC
• Estimating Sizes of Social Networks via Biased Sampling
• Communities, Random Walks, and Social Sybil Defense
• On the Complexity of Sampling Vertices Uniformly from a Graph
• The Power of Distributed Verifiers in Interactive Proofs
• Fiat-Shamir: from practice to theory
• Interactive proofs of proximity
• Networks

This page was built for publication: Interactive proofs for social graphs