More Like this

1. Errors are Robustly Tamed in Cumulative Knowledge Processes

   Brandenberger, Anna M; Marcussen, Cassandra; Mossel, Elchanan; Sudan, Madhu (June 2024, PMLR)

   We study processes of societal knowledge accumulation, where the validity of a new unit of knowledge depends both on the correctness of its derivation and on the validity of the units it depends on. A fundamental question in this setting is: If a constant fraction of the new derivations is wrong, can investing a constant fraction, bounded away from one, of effort ensure that a constant fraction of knowledge in society is valid? Ben-Eliezer, Mikulincer, Mossel, and Sudan (ITCS 2023) introduced a concrete probabilistic model to analyze such questions and showed an affirmative answer to this question. Their study, however, focuses on the simple case where each new unit depends on just one existing unit, and units attach according to a {\em preferential attachment rule}. In this work, we consider much more general families of cumulative knowledge processes, where new units may attach according to varied attachment mechanisms and depend on multiple existing units. We also allow a (random) fraction of insertions of adversarial nodes. We give a robust affirmative answer to the above question by showing that for \textit{all} of these models, as long as many of the units follow simple heuristics for checking a bounded number of units they depend on, all errors will be eventually eliminated. Our results indicate that preserving the quality of large interdependent collections of units of knowledge is feasible, as long as careful but not too costly checks are performed when new units are derived/deposited. 

   more » « less
2. Is This Correct? Let's Check!

   Ben-Eliezer, Omri; Mikulincer, Dan; Mossel, Elchanan; Sudan, Madhu (January 2023, 14th Innovations in Theoretical Computer Science Conference, {ITCS} 2023)

   Kaiai, Yael Tauman (Ed.)

   Societal accumulation of knowledge is a complex process. The correctness of new units of knowledge depends not only on the correctness of new reasoning, but also on the correctness of old units that the new one builds on. The errors in such accumulation processes are often remedied by error correction and detection heuristics. Motivating examples include the scientific process based on scientific publications, and software development based on libraries of code. Natural processes that aim to keep errors under control, such as peer review in scientific publications, and testing and debugging in software development, would typically check existing pieces of knowledge - both for the reasoning that generated them and the previous facts they rely on. In this work, we present a simple process that models such accumulation of knowledge and study the persistence (or lack thereof) of errors. We consider a simple probabilistic model for the generation of new units of knowledge based on the preferential attachment growth model, which additionally allows for errors. Furthermore, the process includes checks aimed at catching these errors. We investigate when effects of errors persist forever in the system (with positive probability) and when they get rooted out completely by the checking process. The two basic parameters associated with the checking process are the probability of conducting a check and the depth of the check. We show that errors are rooted out if checks are sufficiently frequent and sufficiently deep. In contrast, shallow or infrequent checks are insufficient to root out errors. 

   more » « less
3. Bi-Sobolev Extensions

   https://doi.org/10.1007/s12220-023-01363-1  

   Koski, Aleksis; Onninen, Jani (July 2023, The Journal of Geometric Analysis)

   Abstract We give a full characterization of circle homeomorphisms which admit a homeomorphic extension to the unit disk with finite bi-Sobolev norm. As a special case, a bi-conformal variant of the famous Beurling–Ahlfors extension theorem is obtained. Furthermore we show that the existing extension techniques such as applying either the harmonic or the Beurling–Ahlfors operator work poorly in the degenerated setting. This also gives an affirmative answer to a question of Karafyllia and Ntalampekos. 

   more » « less
4. Network Causal Effect Estimation In Graphical Models Of Contagion And Latent Confounding

   Wu, Yufeng; Bhattacharya, Rohit (May 2025, Proceedings of Machine Learning Research)

   A key question in many network studies is whether the observed correlations between units are primarily due to contagion or latent confounding. Here, we study this question using a segregated graph (Shpitser, 2015) representation of these mechanisms, and examine how uncertainty about the true underlying mechanism impacts downstream computation of network causal effects, particularly under full interference---settings where we only have a single realization of a network and each unit may depend on any other unit in the network. Under certain assumptions about asymptotic growth of the network, we derive likelihood ratio tests that can be used to identify whether different sets of variables---confounders, treatments, and outcomes---across units exhibit dependence due to contagion or latent confounding. We then propose network causal effect estimation strategies that provide unbiased and consistent estimates if the dependence mechanisms are either known or correctly inferred using our proposed tests. Together, the proposed methods allow network effect estimation in a wider range of full interference scenarios that have not been considered in prior work. We evaluate the effectiveness of our methods with synthetic data and the validity of our assumptions using real-world networks. 

   more » « less
5. Maximizing Truth Learning in a Social Network is NP-Hard

   Uradnik, Filip; Wang, Amanda; Gao, Jie (May 2025, Proceedings of the 24th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS))

   Sequential learning models situations where agents predict a ground truth in sequence, by using their private, noisy measurements, and the predictions of agents who came earlier in the sequence. We study sequential learning in a social network, where agents only see the actions of the previous agents in their own neighborhood. The fraction of agents who predict the ground truth correctly depends heavily on both the network topology and the ordering in which the predictions are made. A natural question is to find an ordering, with a given network, to maximize the (expected) number of agents who predict the ground truth correctly. In this paper, we show that it is in fact NP-hard to answer this question for a general network, with both the Bayesian learning model and a simple majority rule model. Finally, we show that even approximating the answer is hard. 

   more » « less