Interactive proofs for social graphs

DOI10.1007/978-3-030-56877-1_20MaRDI QIDQ2102081zbMATH OpenOpenAlexFDO

Authors Liran Katzir, Clara Shikhelman, 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 proofssocial graphssuccinct arguments

Mathematics Subject Classification ID

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

Recommendations

• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• Interactive proofs and the hardness of approximating cliques
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
• Interactive and automated proofs for graph transformations
• Labelled graph rewriting meets social networks
• scientific article; zbMATH DE number 1231506
• A Framework for Interactive Proof
• Graph profile realizations and applications to social networks
• scientific article; zbMATH DE number 2077106

Cites work

• An efficient parallel repetition theorem
• Calculating statistics of complex networks through random walks with an application to the on-line social network bebo
• Communities, Random Walks, and Social Sybil Defense
• Computationally Sound Proofs
• Estimating sizes of social networks via biased sampling
• Fast approximate probabilistically checkable proofs
• Fiat-Shamir and correlation intractability from strong KDM-secure encryption
• Fiat-Shamir: from practice to theory
• From obfuscation to the security of Fiat-Shamir for proofs
• How large is your graph?
• How To Prove Yourself: Practical Solutions to Identification and Signature Problems
• Interactive oracle proofs
• Interactive proofs of proximity: delegating computation in sublinear time
• Networks, crowds and markets. Reasoning about a highly connected world.
• Networks. An introduction.
• On polynomial approximations to \(\mathrm{AC}^0\)
• On the Complexity of Sampling Vertices Uniformly from a Graph
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• Random sampling from a search engine's index
• Renormalization group analysis of the small-world network model
• The Knowledge Complexity of Interactive Proof Systems
• The mixing time of the Newman-Watts small world
• The power of distributed verifiers in interactive proofs
• The small-world phenomenon: an algorithmic perspective
• Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)

Cited in

(1)

• Hamming weight proofs of proximity with one-sided error

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2102081)