Research map / Learning theory and algorithms / Sample complexity
Learning Broadcast Protocols
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that fine broadcast protocols (BPs with no hidden states and a finite cutoff) can be inferred from samples via an SMT-based algorithm, that minimal BPs are obtained from characteristic sets, and proves negative results (exponential characteristic sets, NP-hard consistency, not polynomially predictable).
Problem
Learning a distributed system (broadcast protocol) with an arbitrary number of processes from examples, when only the existence of a cutoff is assumed and no fixed number of processes is known.
Approach
Passive learning of fine broadcast protocols: an SMT (EUF) constraint encoding of a sample of (word, number of processes, label) triples yields a BP consistent with the sample; a characteristic-set generation procedure over cutoff-indexed trees, combined with an iff-variant of the constraints, yields a minimal equivalent BP when the sample is complete.
Key results
- Inference algorithm via SMT constraints returns a BP consistent with any sample consistent with some fine BP.
- Characteristic sets of exponential size exist for a family of fine BPs (shortest distinguishing word has length exponential in BP size).
- BP consistency is NP-hard, and fine BPs are not polynomially predictable under standard cryptographic assumptions.
Surprising findings
- Characteristic sets for fine BPs may be inevitably exponential in the number of states.
- Fine BPs can be exponentially smaller than the minimal DFA for the same language.
Limitations
- Restricted to fine BPs: no hidden states and assumed existence of a cutoff.
- Negative results: exponential characteristic sets and NP-hard consistency limit practical efficiency.
- No experimental evaluation of the inference algorithm is reported.
Experimental setup
Builds on: Esparza et al. broadcast protocols Angluin DFA learning Angluin and Kharitonov cryptographic hardness of predictability
Closest papers by meaning
- Distributed Event-Based Learning via ADMM (ICML 2025 · similarity 0.84)
- Communication Bounds for the Distributed Experts Problem (NeurIPS 2024 · similarity 0.83)
- PDUDT: Provable Decentralized Unlearning under Dynamic Topologies (ICML 2025 · similarity 0.83)
- Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework (NeurIPS 2024 · similarity 0.82)
- The Sample-Communication Complexity Trade-off in Federated Q-Learning (NeurIPS 2024 · similarity 0.82)
- On the Expressive Power and Limitations of Multi-Layer SSMs (NeurIPS 2026 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.