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

Recognition: no theorem link

On the Limits of PAC Learning of Networks from Opinion Dynamics

Dmitry Chistikov , Luisa Estrada , Mike Paterson , Paolo Turrini

Authors on Pith no claims yet

Pith reviewed 2026-05-15 03:05 UTC · model grok-4.3

classification 💻 cs.SI cs.CC

keywords PAC learningopinion dynamicssocial networksthreshold modelsmajority rulenetwork reconstructioncomputational complexity

0 comments

The pith

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.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that when agents flip opinions only if a fixed bounded number of their influencers all agree (as in unanimity or quasi-unanimity rules), the underlying influence network can be recovered with high probability from a polynomial number of synchronous update examples. This matters because many real social systems hide their exact influence edges, and the result shows those edges become recoverable without assuming full observability. By contrast, when agents instead follow a strict majority of their influencers, no polynomial-time PAC learner exists assuming standard complexity separations. The authors also supply a practical heuristic that finds consistent networks in over 98 percent of tested random instances.

Core claim

If the opinion dynamics follow a threshold rule in which a fixed number of influencers prevent opinion change (for example unanimity and quasi-unanimity), there exists an efficient PAC learning algorithm provided the number of influencers per agent is bounded; if instead agents follow the majority of their influencers, then no efficient PAC learning algorithm exists under standard computational complexity assumptions.

What carries the argument

PAC learning of the directed influence graph from samples of synchronous deterministic threshold opinion updates, with bounded in-degree for the positive case.

If this is right

The influence graph can be recovered exactly with high probability using polynomially many samples when the threshold prevents change unless all or nearly all influencers agree and in-degree is bounded.
Majority dynamics render network recovery computationally intractable in the PAC sense.
A simple polynomial-time heuristic recovers consistent networks in over 98 percent of simulations on random graphs and never fails under certain conditions on agent count and sample size.
Learning succeeds precisely when the observed updates are generated by the exact synchronous deterministic rule with no external noise.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The result implies that social-media platforms might deliberately favor high-threshold rules if they wish to make hidden influence structures harder to infer from public activity logs.
Empirical tests on real opinion-trace datasets could check whether observed dynamics are closer to the learnable unanimity regime or the hard majority regime.
Extending the positive algorithm to tolerate small amounts of asynchronous updates or observation noise would be a direct next step that preserves the bounded-influencer premise.
The hardness proof for majority suggests that similar intractability may hold for other low-threshold rules, opening a classification of which threshold values permit efficient network learning.

Load-bearing premise

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

What would settle it

A concrete polynomial-time algorithm that PAC-learns the network under majority dynamics from update samples, or a family of graphs where the proposed heuristic fails to return a consistent network with non-negligible probability.

read the original abstract

Agents in social networks with threshold-based dynamics change opinions when influenced by sufficiently many peers. Existing literature typically assumes that the network structure and dynamics are fully known, which is often unrealistic. In this work, we ask how to learn a network structure from samples of the agents' synchronous opinion updates. Firstly, 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. Secondly, under standard computational complexity assumptions, we prove that if agents' opinions follow the majority of their influencers, then there is no efficient PAC learning algorithm. We propose a polynomial-time heuristic that successfully learns consistent networks in over $98\%$ of our simulations on random graphs, with no failures for some specified conditions on the numbers of agents and opinion diffusion examples.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

PAC learnability splits between high-threshold rules with bounded influencers and majority dynamics, with a working heuristic for the latter.

read the letter

This paper shows that network recovery from synchronous opinion updates is tractable for certain restrictive threshold rules but intractable for majority under standard complexity assumptions. The positive side gives a polynomial-time PAC algorithm when each agent needs a bounded number of influencers to block a change, as in unanimity or quasi-unanimity. The algorithm works by using the rare flip events to pin down exact neighbor sets from the observed traces. The negative side proves that majority dynamics yield no efficient learner, via a reduction that preserves the PAC guarantee. They also include a simple heuristic that finds consistent networks in over 98 percent of random-graph trials, with zero failures under some parameter regimes. That practical note is worth having even though it sits outside the worst-case analysis. The model assumptions are tight: deterministic synchronous updates, no noise, and exact threshold behavior. The bounded-influencer condition is necessary for the positive result and may limit applicability to real networks. The hardness holds only for exact majority, not for nearby rules. Without the body of the paper I cannot inspect the proof details or the precise sample complexity, but the abstract statements line up internally and do not rely on fitted parameters or circular definitions. This is aimed at researchers who combine learning theory with network dynamics. A reader who already works on PAC results for graphs or influence inference will find the separation useful. Send it for peer review; the split between the two regimes is clean enough to merit checking the reductions and the simulation setup.

Referee Report

2 major / 2 minor

Summary. The paper studies PAC learnability of network structures from samples of synchronous opinion updates under deterministic threshold dynamics. It gives a constructive efficient algorithm for high-threshold rules (unanimity and quasi-unanimity) when each agent has a bounded number of influencers, proves that no efficient PAC algorithm exists for majority dynamics under standard complexity assumptions, and presents a polynomial-time heuristic whose empirical success rate exceeds 98% on random graphs with no failures under certain parameter regimes.

Significance. If the algorithmic and hardness results hold, the work sharply delineates the boundary between efficiently learnable and intractable opinion-dynamics models, supplying both a positive constructive algorithm that exploits restrictive update conditions and a hardness reduction that relies on external complexity assumptions rather than internal circularity. The heuristic's simulation performance on random graphs provides practical evidence of utility even though it lacks worst-case guarantees.

major comments (2)

[Algorithm description (following the abstract claim)] The positive PAC result for bounded-influencer high-threshold rules is load-bearing for the central claim yet the manuscript provides no explicit sample-complexity bound in terms of the influencer bound k, number of agents n, and failure probability; the efficiency statement therefore remains qualitative rather than quantitative.
[Heuristic and simulation section] The heuristic is presented as polynomial-time and empirically successful in >98% of trials, but the manuscript contains no analysis of its approximation ratio, failure probability, or the precise conditions on n and number of diffusion examples that guarantee zero failures; this gap directly affects the practical contribution.

minor comments (2)

[Preliminaries] Notation for the threshold parameter and the influencer set should be introduced once and used consistently; occasional reuse of symbols for different quantities reduces readability.
[Experimental evaluation] The simulation setup (graph model, number of trials, exact parameter ranges for the 'no failures' regime) should be stated in a single table or paragraph rather than scattered across the text.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive recommendation of minor revision and for the constructive comments that help clarify the presentation of our results. We address each major comment below.

read point-by-point responses

Referee: [Algorithm description (following the abstract claim)] The positive PAC result for bounded-influencer high-threshold rules is load-bearing for the central claim yet the manuscript provides no explicit sample-complexity bound in terms of the influencer bound k, number of agents n, and failure probability; the efficiency statement therefore remains qualitative rather than quantitative.

Authors: We appreciate the referee highlighting this point. Our algorithm is fully constructive: for each agent it enumerates all possible influencer sets of size at most k and retains only those consistent with the observed synchronous updates. This immediately yields a polynomial-time procedure once k is treated as a fixed constant. While the manuscript states that the procedure is efficient, we acknowledge that an explicit sample-complexity expression (in terms of k, n, ε, and δ) was not written out. In the revision we will add the derivation: a standard Hoeffding-plus-union-bound argument over the O(n · binom(n,k)) candidate hypotheses produces an explicit PAC sample bound that is polynomial in n and 1/ε for any fixed k. This makes the efficiency claim quantitative without altering the algorithm itself. revision: yes
Referee: [Heuristic and simulation section] The heuristic is presented as polynomial-time and empirically successful in >98% of trials, but the manuscript contains no analysis of its approximation ratio, failure probability, or the precise conditions on n and number of diffusion examples that guarantee zero failures; this gap directly affects the practical contribution.

Authors: We agree that the heuristic is presented purely as a practical polynomial-time method without worst-case guarantees. It is a simple greedy procedure that iteratively adds the smallest set of edges consistent with observed opinion flips; no approximation ratio or high-probability failure bound is claimed or proved. In the revised manuscript we will explicitly state these limitations and supply the exact simulation parameters (graph size n, number of diffusion traces m, and threshold values) under which zero failures were observed. We believe the >98 % empirical success rate on random graphs still provides useful practical evidence, but we will clarify that the contribution is empirical rather than theoretical. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's positive PAC result follows from an explicit constructive algorithm that recovers bounded-influence neighbor sets by exploiting the restrictive threshold update rules (unanimity/quasi-unanimity) on observed synchronous flips; the negative result for majority dynamics is a standard complexity reduction under external assumptions. No derivation step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation chain. The model assumptions (deterministic synchronous updates, no noise) are stated upfront and the heuristic is presented only as an empirical supplement, not as a theoretical claim. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Results rest on the standard PAC learning model, the assumption that dynamics are exactly deterministic threshold functions, and standard complexity assumptions for the hardness part. No free parameters or invented entities are introduced.

axioms (2)

domain assumption Opinion updates follow a deterministic threshold rule with a fixed number of influencers per agent
Central to both the positive algorithm and the hardness reduction.
domain assumption Standard computational complexity assumptions (e.g., P ≠ NP or similar)
Invoked for the no-efficient-PAC-learning claim under majority dynamics.

pith-pipeline@v0.9.0 · 5456 in / 1267 out tokens · 52495 ms · 2026-05-15T03:05:54.382190+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages · 1 internal anchor

[1]

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

Jackson, M.O., Watts, A.: The Evolution of Social and Economic Networks. Jour- nal of Economic Theory106(2), 265–295 (2002) https://doi.org/10.1006/jeth. 2001.2903

work page doi:10.1006/jeth 2002
[3]

Election Manipulation on Social Networks with Messages on Multiple Candidates

Castiglioni, M., Ferraioli, D., Landriani, G., Gatti, N.: Election Manipulation on Social Networks with Messages on Multiple Candidates. CoRRabs/1902.03779 (2019). arXiv: 1902.03779

work page internal anchor Pith review Pith/arXiv arXiv 1902
[4]

In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery And Data Mining

Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., Glance, N.: Cost-Effective Outbreak Detection in Networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery And Data Mining. KDD ’07, pp. 420–429. Association for Computing Machinery, New York, NY, USA (2007). https://doi.org/10.1145/1281192.128123...

work page doi:10.1145/1281192.1281239 2007
[5]

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

Deligkas, A., Eiben, E., Goldsmith, T.-L., Skretas, G.: Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source. In: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. AAMAS ’23, pp. 2222–2230. International Foun- dation for Autonomous Agents and Multiagent Sys...

work page 2023
[6]

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

Fogarty, L., Creanza, N., Feldman, M.W.: The role of cultural transmission in human demographic change: An age-structured model. Theoretical Population Biology88, 68–77 (2013) https://doi.org/10.1016/j.tpb.2013.06.006

work page doi:10.1016/j.tpb.2013.06.006 2013
[7]

Journal of The Royal Society Interface20(2023) https://doi.org/10.1098/rsif.2022.0736

Galesic, M., Barkoczi, D., Berdahl, A.M., Biro, D., Carbone, G., Giannoccaro, I., Goldstone, R.L., Gonzalez, C., Kandler, A., Kao, A.B., Kendal, R., Kline, M., Lee, E., Massari, G.F., Mesoudi, A., Olsson, H., Pescetelli, N., Sloman, S.J., Smaldino, P.E., Stein, D.L.: Beyond collective intelligence: Collective adaptation. Journal of The Royal Society Inter...

work page doi:10.1098/rsif.2022.0736 2023
[8]

Reconstructing Waddington’s landscape from data

Ammar, M., Fogarty, L., Kandler, A.: Social learning and memory. Proceedings of the National Academy of Sciences120(33) (2023) https://doi.org/10.1073/pnas. 2310033120 . Publisher: Proceedings of the National Academy of Sciences

work page doi:10.1073/pnas 2023
[9]

Nature communications 5, 3526 (2014) https://doi.org/10.1038/ncomms4526

Gavrilets, S., Fortunato, L.: A Solution to the Collective Action Problem in Between-Group Conflict and Within-Group Inequality. Nature communications 5, 3526 (2014) https://doi.org/10.1038/ncomms4526

work page doi:10.1038/ncomms4526 2014
[10]

Proceedings of the AAAI Conference on Artificial Intelligence34(05), 7103–7110 (2020) https://doi.org/10.1609/aaai.v34i05.6197

Chistikov, D., Lisowski, G., Paterson, M., Turrini, P.: Convergence of Opinion 26 Diffusion is PSPACE-Complete. Proceedings of the AAAI Conference on Artificial Intelligence34(05), 7103–7110 (2020) https://doi.org/10.1609/aaai.v34i05.6197

work page doi:10.1609/aaai.v34i05.6197 2020
[11]

Journal of Statistical Physics181(2020) https: //doi.org/10.1007/s10955-020-02625-w

Mukhopadhyay, A., Mazumdar, R., Roy, R.: Voter and Majority Dynamics with Biased and Stubborn Agents. Journal of Statistical Physics181(2020) https: //doi.org/10.1007/s10955-020-02625-w

work page doi:10.1007/s10955-020-02625-w 2020
[12]

In: Markakis, E., Sch¨ afer, G

Auletta, V., Caragiannis, I., Ferraioli, D., Galdi, C., Persiano, G.: Minority Becomes Majority in Social Networks. In: Markakis, E., Sch¨ afer, G. (eds.) Web and Internet Economics, pp. 74–88. Springer, Berlin, Heidelberg (2015)

work page 2015
[13]

In: Proceedings of the Ninth ACM SIGKDD Inter- national Conference on Knowledge Discovery And Data Mining

Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the Spread of Influence through a Social Network. In: Proceedings of the Ninth ACM SIGKDD Inter- national Conference on Knowledge Discovery And Data Mining. KDD ’03, pp. 137–146. Association for Computing Machinery, New York, NY, USA (2003). https://doi.org/10.1145/956750.956769 . event-place: Washington, D...

work page doi:10.1145/956750.956769 2003
[14]

In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp

Bredereck, R., Elkind, E.: Manipulating Opinion Diffusion in Social Networks. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 894–900 (2017). https://doi.org/10.24963/ijcai.2017/ 124 .https://doi.org/10.24963/ijcai.2017/124

work page doi:10.24963/ijcai.2017/ 2017
[15]

Government Information Quarterly 39(3), 101709 (2022) https://doi.org/10.1016/j.giq.2022.101709

Kushwaha, A.K., Kar, A.K., Roy, S.K., Ilavarasan, P.V.: Capricious opinions: A study of polarization of social media groups. Government Information Quarterly 39(3), 101709 (2022) https://doi.org/10.1016/j.giq.2022.101709

work page doi:10.1016/j.giq.2022.101709 2022
[16]

In: Pro- ceedings of the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling Of Computer Systems

Netrapalli, P., Sanghavi, S.: Learning the Graph of Epidemic Cascades. In: Pro- ceedings of the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling Of Computer Systems. SIGMET- RICS ’12, pp. 211–222. Association for Computing Machinery, New York, NY, USA (2012). https://doi.org/10.1145/2254756.2254783 . event-place: ...

work page doi:10.1145/2254756.2254783 2012
[17]

Proceedings of the AAAI Conference on Artificial Intelligence32(1) (2018) https://doi.org/10.1609/aaai.v32i1.11585

Wilder, B., Immorlica, N., Rice, E., Tambe, M.: Maximizing Influence in an Unknown Social Network. Proceedings of the AAAI Conference on Artificial Intelligence32(1) (2018) https://doi.org/10.1609/aaai.v32i1.11585

work page doi:10.1609/aaai.v32i1.11585 2018
[18]

IEEE Control Systems Magazine41(5), 61–103 (2021) https://doi.org/10.1109/MCS.2021.3092810

Ravazzi, C., Dabbene, F., Lagoa, C., Proskurnikov, A.V.: Learning Hidden Influ- ences in Large-Scale Dynamical Social Networks: A Data-Driven Sparsity-Based Approach, in Memory of Roberto Tempo. IEEE Control Systems Magazine41(5), 61–103 (2021) https://doi.org/10.1109/MCS.2021.3092810

work page doi:10.1109/mcs.2021.3092810 2021
[19]

In: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

Chistikov, D., Estrada, L., Paterson, M., Turrini, P.: Learning a Social Network by Influencing Opinions. In: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems. AAMAS ’24, pp. 363–371. Inter- national Foundation for Autonomous Agents and Multiagent Systems, Richland, 27 SC (2024). event-place: Auckland, New Zealand

work page 2024
[20]

Artificial Intelligence284, 103288 (2020) https://doi.org/10.1016/j.artint.2020.103288

Auletta, V., Ferraioli, D., Greco, G.: On the complexity of reasoning about opin- ion diffusion under majority dynamics. Artificial Intelligence284, 103288 (2020) https://doi.org/10.1016/j.artint.2020.103288

work page doi:10.1016/j.artint.2020.103288 2020
[21]

In: NIPS (2010).https://api.semanticscholar.org/CorpusID:6812407

Myers, S.A., Leskovec, J.: On the Convexity of Latent Social Network Inference. In: NIPS (2010).https://api.semanticscholar.org/CorpusID:6812407

work page 2010
[22]

In: Proceedings of the 28th International Con- ference on International Conference on Machine Learning

Gomez-Rodriguez, M., Balduzzi, D., Scholkopf, B.: Uncovering the Temporal Dynamics of Diffusion Networks. In: Proceedings of the 28th International Con- ference on International Conference on Machine Learning. ICML’11, pp. 561–568. Omnipress, Madison, WI, USA (2011). event-place: Bellevue, Washington, USA

work page 2011
[23]

Games11(4) (2020) https://doi.org/10.3390/g11040065

Grabisch, M., Rusinowska, A.: A Survey on Nonstrategic Models of Opinion Dynamics. Games11(4) (2020) https://doi.org/10.3390/g11040065

work page doi:10.3390/g11040065 2020
[24]

Physica A: Statistical Mechanics and its Applications623, 128811 (2023) https://doi.org/10.1016/j.physa.2023.128811

Baldassarri, S., Gallo, A., Jacquier, V., Zocca, A.: Ising model on clustered net- works: A model for opinion dynamics. Physica A: Statistical Mechanics and its Applications623, 128811 (2023) https://doi.org/10.1016/j.physa.2023.128811

work page doi:10.1016/j.physa.2023.128811 2023
[25]

Classics in Mathematics

Liggett, T.M.: Interacting Particle Systems. Classics in Mathematics. Springer, ??? (2004).https://books.google.co.uk/books?id=I3aNPR1FursC

work page 2004
[26]

In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M

Kempe, D., Kleinberg, J.M., Tardos, E.: Influential Nodes in a Diffusion Model for Social Networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings. Lec- ture Notes in Computer Science, vol. 3580, p...

work page doi:10.1007/11523468 2005
[27]

In: Proceedings of the 15th ACM SIGKDD Interna- tional Conference on Knowledge Discovery And Data Mining

Chen, W., Wang, Y., Yang, S.: Efficient Influence Maximization in Social Networks. In: Proceedings of the 15th ACM SIGKDD Interna- tional Conference on Knowledge Discovery And Data Mining. KDD ’09, pp. 199–208. Association for Computing Machinery, New York, NY, USA (2009). https://doi.org/10.1145/1557019.1557047 . event-place: Paris, France. https://doi.o...

work page doi:10.1145/1557019.1557047 2009
[28]

In: Proceedings of the 2015 ACM SIGMOD Inter- national Conference on Management of Data

Tang, Y., Shi, Y., Xiao, X.: Influence Maximization in Near-Linear Time: A Martingale Approach. In: Proceedings of the 2015 ACM SIGMOD Inter- national Conference on Management of Data. SIGMOD ’15, pp. 1539–1554. Association for Computing Machinery, New York, NY, USA (2015). https:// doi.org/10.1145/2723372.2723734 . event-place: Melbourne, Victoria, Austr...

work page doi:10.1145/2723372.2723734 2015
[29]

28 In: Proceedings of the 29th International Conference on Neural Information Pro- cessing Systems - Volume 2

Narasimhan, H., Parkes, D.C., Singer, Y.: Learnability of influence in networks. 28 In: Proceedings of the 29th International Conference on Neural Information Pro- cessing Systems - Volume 2. NIPS’15, pp. 3186–3194. MIT Press, Cambridge, MA, USA (2015). event-place: Montreal, Canada

work page 2015
[30]

Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (2010)

Gomez-Rodriguez, M., Leskovec, J., Krause, A.: Inferring networks of diffusion and influence. Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (2010)

work page 2010
[31]

Qiu, Z., Adiga, A., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E., Vullikanti, A.: Learning the topology and behavior of discrete dynamical systems. In: Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educ...

work page doi:10.1609/aaai.v38i13.29390 2024
[32]

MIT Press, Cambridge, MA, USA (1994)

Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA (1994)

work page 1994
[33]

Journal of Machine Learning Research17(38), 1–15 (2016)

Hanneke, S.: The Optimal Sample Complexity of PAC Learning. Journal of Machine Learning Research17(38), 1–15 (2016)

work page 2016
[34]

Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM36, 929–965 (1989)

work page 1989
[35]

Information and Computation 82(3), 247–261 (1989) https://doi.org/10.1016/0890-5401(89)90002-3

Ehrenfeucht, A., Haussler, D., Kearns, M., Valiant, L.: A general lower bound on the number of examples needed for learning. Information and Computation 82(3), 247–261 (1989) https://doi.org/10.1016/0890-5401(89)90002-3

work page doi:10.1016/0890-5401(89)90002-3 1989
[36]

Cambridge University Press, USA (1992)

Anthony, M., Biggs, N.: Computational Learning Theory: an Introduction. Cambridge University Press, USA (1992)

work page 1992
[37]

McGraw- Hill, Inc., USA (2006)

Dasgupta, S., Papadimitriou, C.H., Vazirani, U.: Algorithms, 1st edn. McGraw- Hill, Inc., USA (2006)

work page 2006
[38]

Theoretical Computer Science Stack Exchange (2017)

Rudoy, M.: NP-hardness of finding 0-1 vector to maximize rows of -1, +1 matrix. Theoretical Computer Science Stack Exchange (2017). https://cstheory. stackexchange.com/q/39786

work page 2017
[39]

Discrete Math- ematics13(4), 383–390 (1975) https://doi.org/10.1016/0012-365X(75)90058-8

Lov´ asz, L.: On the ratio of optimal integral and fractional covers. Discrete Math- ematics13(4), 383–390 (1975) https://doi.org/10.1016/0012-365X(75)90058-8

work page doi:10.1016/0012-365x(75)90058-8 1975
[40]

Feige, U.: A threshold of ln n for approximating set cover. J. ACM45(4), 634– 652 (1998) https://doi.org/10.1145/285055.285059 . Place: New York, NY, USA Publisher: Association for Computing Machinery 29

work page doi:10.1145/285055.285059 1998
[41]

eprint: 2305.05565 (2023)

Arpino, G., Dmitriev, D., Grometto, N.: Greedy Heuristics and Linear Relax- ations for the Random Hitting Set Problem. eprint: 2305.05565 (2023). https: //arxiv.org/abs/2305.05565 30

work page arXiv 2023