Pith Number

pith:BEB4DDRJ

pith:2026:BEB4DDRJN7AFW7KX65CHFB2NRE

not attested not anchored not stored refs resolved

On the Limits of PAC Learning of Networks from Opinion Dynamics

Dmitry Chistikov, Luisa Estrada, Mike Paterson, Paolo Turrini

Networks with unanimity-style opinion updates can be learned efficiently from samples via PAC algorithms when each agent has a bounded number of influencers, but majority updates make efficient learning impossible under standard complexity.

arxiv:2605.15033 v1 · 2026-05-14 · cs.SI · cs.CC

Open paper page JSON Open Graph Bundle Merged state What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{BEB4DDRJN7AFW7KX65CHFB2NRE}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

if the opinion dynamics follow a threshold rule in which a fixed number of influencers prevent opinion change (e.g., unanimity and quasi-unanimity), we provide an efficient PAC learning algorithm provided that the number of influencers per agent is bounded. ... if agents' opinions follow the majority of their influencers, then there is no efficient PAC learning algorithm.

C2weakest assumption

The opinion updates exactly follow a deterministic threshold rule with a fixed number of influencers per agent (or exactly majority), and the samples are drawn from the synchronous update process without noise or hidden variables.

C3one line summary

PAC learning of networks from threshold opinion dynamics is efficient when influencers per agent are bounded but computationally hard for majority rules, with a heuristic succeeding in over 98% of simulations.

References

40 extracted · 40 resolved · 1 Pith anchors

[1] Jour- nal of Economic Theory106(2), 265–295 (2002) https://doi.org/10.1006/jeth 2002 · doi:10.1006/jeth

[3] Election Manipulation on Social Networks with Messages on Multiple Candidates 1902 · arXiv:1902.03779

[4] In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery And Data Mining 2007 · doi:10.1145/1281192.1281239

[5] In: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems 2023

[6] Theoretical Population Biology88, 68–77 (2013) https://doi.org/10.1016/j.tpb.2013.06.006 2013 · doi:10.1016/j.tpb.2013.06.006

Receipt and verification

First computed	2026-05-17T23:38:54.562030Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

0903c18e296fc05b7d57f74472874d89307f3d845eea9021ce67a40b74c09b75

Aliases

arxiv: 2605.15033 · arxiv_version: 2605.15033v1 · doi: 10.48550/arxiv.2605.15033 · pith_short_12: BEB4DDRJN7AF · pith_short_16: BEB4DDRJN7AFW7KX · pith_short_8: BEB4DDRJ

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/BEB4DDRJN7AFW7KX65CHFB2NRE \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 0903c18e296fc05b7d57f74472874d89307f3d845eea9021ce67a40b74c09b75

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "52c1e8a910aefe1279267a1cc1ad20129a6ae1e88b1d2e6a810592c42a17e735",
    "cross_cats_sorted": [
      "cs.CC"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.SI",
    "submitted_at": "2026-05-14T16:29:05Z",
    "title_canon_sha256": "184bbdd36d52031bdfcaebc1d21b401e029f3d55951a9c52bb22ca8503e30074"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.15033",
    "kind": "arxiv",
    "version": 1
  }
}