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.
Madhusudan, and Mahesh Visw anathan
4 Pith papers cite this work, alongside 7 external citations. Polarity classification is still indexing.
4
Pith papers citing it
7
external citations · Crossref
representative citing papers
Introduces a distributed stochastic setting for graph optimization and supplies fast approximation algorithms for matching, vertex cover, and dominating set that surpass non-stochastic lower bounds.
An algorithm classifies visibly pushdown languages as AC^0, ACC^0-hard, or constant-depth equivalent to unions of newly defined intermediate VPLs.
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.
citing papers explorer
-
On the Limits of PAC Learning of Networks from Opinion Dynamics
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.
-
Distributed Stochastic Graph Algorithms
Introduces a distributed stochastic setting for graph optimization and supplies fast approximation algorithms for matching, vertex cover, and dominating set that surpass non-stochastic lower bounds.
-
The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
An algorithm classifies visibly pushdown languages as AC^0, ACC^0-hard, or constant-depth equivalent to unions of newly defined intermediate VPLs.
-
Equilibria in Multiplayer Graph Games: An Algorithmic Study
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.