Madhu Sudan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Madhu Sudan has a total of 73 co-authors. Here are the top co-authors by number of shared publications:
- Sanjeev Khanna
School of Engineering and Applied Sciences University of Pennsylvania Philadelphia PA
5 shared publications - Aaron Putterman
School of Engineering and Applied Sciences Harvard University Cambridge Massachusetts USA
4 shared publications - Alexander Golovnev
Georgetown University
4 shared publications - Elchanan Mossel
Massachusetts Institute of Technology, Cambridge, USA
4 shared publications - Mrinal Kumar
Tata Institute of Fundamental Research, Mumbai, India
4 shared publications - Prahladh Harsha
Tata Institute of Fundamental Research Mumbai India
4 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1092-1103
Ideals, Macaulay Bases, and PCPs
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1092-1103
Open AccessIdeals, Macaulay Bases, and PCPs
- Open Access
Markov Chains with Rewinding
Motivated by techniques developed in recent progress on lower bounds for sublinear time algorithms (Behnezhad, Roghani and Rubinstein, STOC 2023, FOCS 2023, and STOC 2024) we introduce and study a new class of randomized algorithmic processes that we call Markov Chains with Rewinding. In this setting, an algorithm interacts with a (partially observable) Markovian random evolution by strategically rewinding the Markov chain to previous states. Depending on the application, this may lead the evolution to desired states faster, or allow the agent to efficiently learn or test properties of the underlying Markov chain that may be infeasible or inefficient with passive observation. We study the task of identifying the initial state in a given partially observable Markov chain. Analysis of this question in specific Markov chains is the central ingredient in the above cited works and we aim to systematize the analysis in our work. Our first result is that any pair of states distinguishable with any rewinding strategy can also be distinguished with a non-adaptive rewinding strategy (one whose rewinding choices are determined before observing any outcomes of the chain). Therefore, while rewinding strategies can be shown to be strictly more powerful than passive strategies (those that do not rewind back to previous states), adaptivity does not give additional power to a rewinding strategy in the absence of efficiency considerations. The difference becomes apparent however when we introduce a natural efficiency measure, namely the query complexity (i.e., the number of observations they need to identify distinguishable states). Our second main contribution is to quantify this efficiency gap. We present a non-adaptive rewinding strategy whose query complexity is within a polynomial of that of the optimal (adaptive) strategy, and show that such a polynomial loss is necessary in general.
Open AccessMarkov Chains with Rewinding
Motivated by techniques developed in recent progress on lower bounds for sublinear time algorithms (Behnezhad, Roghani and Rubinstein, STOC 2023, FOCS 2023, and STOC 2024) we introduce and study a new class of randomized algorithmic processes that we call Markov Chains with Rewinding. In this setting, an algorithm interacts with a (partially observable) Markovian random evolution by strategically rewinding the Markov chain to previous states. Depending on the application, this may lead the evolution to desired states faster, or allow the agent to efficiently learn or test properties of the underlying Markov chain that may be infeasible or inefficient with passive observation. We study the task of identifying the initial state in a given partially observable Markov chain. Analysis of this question in specific Markov chains is the central ingredient in the above cited works and we aim to systematize the analysis in our work. Our first result is that any pair of states distinguishable with any rewinding strategy can also be distinguished with a non-adaptive rewinding strategy (one whose rewinding choices are determined before observing any outcomes of the chain). Therefore, while rewinding strategies can be shown to be strictly more powerful than passive strategies (those that do not rewind back to previous states), adaptivity does not give additional power to a rewinding strategy in the absence of efficiency considerations. The difference becomes apparent however when we introduce a natural efficiency measure, namely the query complexity (i.e., the number of observations they need to identify distinguishable states). Our second main contribution is to quantify this efficiency gap. We present a non-adaptive rewinding strategy whose query complexity is within a polynomial of that of the optimal (adaptive) strategy, and show that such a polynomial loss is necessary in general.
- Open Access
Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
We consider random walks on ``balanced multislices'' of any ``grid'' that respects the ``symmetries'' of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form $\mathcal{S}^n$ for finite $\mathcal{S}$, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in $\mathcal{S}$. A walk respects symmetries if the probability of going from $u = (u_1,\ldots,u_n)$ to $v = (v_1,\ldots,v_n)$ is invariant under simultaneous permutations of the coordinates of $u$ and $v$.) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost $\mathcal{O}(1)$-wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound. We give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for $d$-junta-sums mapping an arbitrary grid $\mathcal{S}^n$ to an Abelian group, correcting from a near-optimal $(\frac{1}{|\mathcal{S}|^{d}} - \varepsilon)$ fraction of errors for every $\varepsilon > 0$, where a $d$-junta-sum is a sum of (arbitrarily many) $d$-juntas (and a $d$-junta is a function that depends on only $d$ of the $n$ variables). Our proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis.Open AccessEigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
We consider random walks on ``balanced multislices'' of any ``grid'' that respects the ``symmetries'' of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form $\mathcal{S}^n$ for finite $\mathcal{S}$, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in $\mathcal{S}$. A walk respects symmetries if the probability of going from $u = (u_1,\ldots,u_n)$ to $v = (v_1,\ldots,v_n)$ is invariant under simultaneous permutations of the coordinates of $u$ and $v$.) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost $\mathcal{O}(1)$-wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound. We give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for $d$-junta-sums mapping an arbitrary grid $\mathcal{S}^n$ to an Abelian group, correcting from a near-optimal $(\frac{1}{|\mathcal{S}|^{d}} - \varepsilon)$ fraction of errors for every $\varepsilon > 0$, where a $d$-junta-sum is a sum of (arbitrarily many) $d$-juntas (and a $d$-junta is a function that depends on only $d$ of the $n$ variables). Our proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis. - Open Access
A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field $\mathbb{F}$ are non-zero over any "grid" $S^n$ for finite subset $S \subseteq \mathbb{F}$, with probability at least $\max\{|S|^{-d/(|S|-1)},1-d/|S|\}$ over the choice of random point from the grid. In particular, over the Boolean cube ($S = \{0,1\} \subseteq \mathbb{F}$), the lemma asserts non-zero polynomials are non-zero with probability at least $2^{-d}$. In this work we extend the ODLSZ lemma optimally (up to lower-order terms) to "Boolean slices" i.e., points of Hamming weight exactly $k$. We show that non-zero polynomials on the slice are non-zero with probability $(t/n)^{d}(1 - o_{n}(1))$ where $t = \min\{k,n-k\}$ for every $d\leq k\leq (n-d)$. As with the ODLSZ lemma, our results extend to polynomials over Abelian groups. This bound is tight (upto the error term) as evidenced by degree d multilinear monomials. A particularly interesting case is the "balanced slice" ($k=n/2$) where our lemma asserts that non-zero polynomials are non-zero with roughly the same probability on the slice as on the whole cube. The behaviour of low-degree polynomials over Boolean slices has received much attention in recent years. However, the problem of proving a tight version of the ODLSZ lemma does not seem to have been considered before, except for a recent work of Amireddy, Behera, Paraashar, Srinivasan and Sudan (SODA 2025) who established a sub-optimal bound of approximately $((k/n)\cdot(1-(k/n)))^d$ using a proof similar to that of the standard ODLSZ lemma. While the statement of our result mimics that of the ODLSZ lemma, our proof is significantly more intricate and involves spectral reasoning which is employed to show that a natural way of embedding a copy of the Boolean cube inside a balanced Boolean slice is a good sampler.Open AccessA Near-Optimal Polynomial Distance Lemma Over Boolean Slices
The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field $\mathbb{F}$ are non-zero over any "grid" $S^n$ for finite subset $S \subseteq \mathbb{F}$, with probability at least $\max\{|S|^{-d/(|S|-1)},1-d/|S|\}$ over the choice of random point from the grid. In particular, over the Boolean cube ($S = \{0,1\} \subseteq \mathbb{F}$), the lemma asserts non-zero polynomials are non-zero with probability at least $2^{-d}$. In this work we extend the ODLSZ lemma optimally (up to lower-order terms) to "Boolean slices" i.e., points of Hamming weight exactly $k$. We show that non-zero polynomials on the slice are non-zero with probability $(t/n)^{d}(1 - o_{n}(1))$ where $t = \min\{k,n-k\}$ for every $d\leq k\leq (n-d)$. As with the ODLSZ lemma, our results extend to polynomials over Abelian groups. This bound is tight (upto the error term) as evidenced by degree d multilinear monomials. A particularly interesting case is the "balanced slice" ($k=n/2$) where our lemma asserts that non-zero polynomials are non-zero with roughly the same probability on the slice as on the whole cube. The behaviour of low-degree polynomials over Boolean slices has received much attention in recent years. However, the problem of proving a tight version of the ODLSZ lemma does not seem to have been considered before, except for a recent work of Amireddy, Behera, Paraashar, Srinivasan and Sudan (SODA 2025) who established a sub-optimal bound of approximately $((k/n)\cdot(1-(k/n)))^d$ using a proof similar to that of the standard ODLSZ lemma. While the statement of our result mimics that of the ODLSZ lemma, our proof is significantly more intricate and involves spectral reasoning which is employed to show that a natural way of embedding a copy of the Boolean cube inside a balanced Boolean slice is a good sampler. - Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 407-416
Efficient Algorithms and New Characterizations for CSP Sparsification
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 407-416
Open AccessEfficient Algorithms and New Characterizations for CSP Sparsification
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1648-1656
Improved PIR Schemes using Matching Vectors and Derivatives
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1648-1656
Open AccessImproved PIR Schemes using Matching Vectors and Derivatives
- Open Access
Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
We study the problem of constructing hypergraph cut sparsifiers in the streaming model where a hypergraph on $n$ vertices is revealed either via an arbitrary sequence of hyperedge insertions alone ({\em insertion-only} streaming model) or via an arbitrary sequence of hyperedge insertions and deletions ({\em dynamic} streaming model). For any $ε\in (0,1)$, a $(1 \pm ε)$ hypergraph cut-sparsifier of a hypergraph $H$ is a reweighted subgraph $H'$ whose cut values approximate those of $H$ to within a $(1 \pm ε)$ factor. Prior work shows that in the static setting, one can construct a $(1 \pm ε)$ hypergraph cut-sparsifier using $\tilde{O}(nr/ε^2)$ bits of space [Chen-Khanna-Nagda FOCS 2020], and in the setting of dynamic streams using $\tilde{O}(nr\log m/ε^2)$ bits of space [Khanna-Putterman-Sudan FOCS 2024]; here the $\tilde{O}$ notation hides terms that are polylogarithmic in $n$, and we use $m$ to denote the total number of hyperedges in the hypergraph. Up until now, the best known space complexity for insertion-only streams has been the same as that for the dynamic streams. This naturally poses the question of understanding the complexity of hypergraph sparsification in insertion-only streams. Perhaps surprisingly, in this work we show that in \emph{insertion-only} streams, a $(1 \pm ε)$ cut-sparsifier can be computed in $\tilde{O}(nr/ε^2)$ bits of space, \emph{matching the complexity} of the static setting. As a consequence, this also establishes an $Ω(\log m)$ factor separation between the space complexity of hypergraph cut sparsification in insertion-only streams and dynamic streams, as the latter is provably known to require $Ω(nr \log m)$ bits of space.Open AccessNear-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
We study the problem of constructing hypergraph cut sparsifiers in the streaming model where a hypergraph on $n$ vertices is revealed either via an arbitrary sequence of hyperedge insertions alone ({\em insertion-only} streaming model) or via an arbitrary sequence of hyperedge insertions and deletions ({\em dynamic} streaming model). For any $ε\in (0,1)$, a $(1 \pm ε)$ hypergraph cut-sparsifier of a hypergraph $H$ is a reweighted subgraph $H'$ whose cut values approximate those of $H$ to within a $(1 \pm ε)$ factor. Prior work shows that in the static setting, one can construct a $(1 \pm ε)$ hypergraph cut-sparsifier using $\tilde{O}(nr/ε^2)$ bits of space [Chen-Khanna-Nagda FOCS 2020], and in the setting of dynamic streams using $\tilde{O}(nr\log m/ε^2)$ bits of space [Khanna-Putterman-Sudan FOCS 2024]; here the $\tilde{O}$ notation hides terms that are polylogarithmic in $n$, and we use $m$ to denote the total number of hyperedges in the hypergraph. Up until now, the best known space complexity for insertion-only streams has been the same as that for the dynamic streams. This naturally poses the question of understanding the complexity of hypergraph sparsification in insertion-only streams. Perhaps surprisingly, in this work we show that in \emph{insertion-only} streams, a $(1 \pm ε)$ cut-sparsifier can be computed in $\tilde{O}(nr/ε^2)$ bits of space, \emph{matching the complexity} of the static setting. As a consequence, this also establishes an $Ω(\log m)$ factor separation between the space complexity of hypergraph cut sparsification in insertion-only streams and dynamic streams, as the latter is provably known to require $Ω(nr \log m)$ bits of space. - Open Access
A Theory of Spectral CSP Sparsification
We initiate the study of spectral sparsification for instances of Constraint Satisfaction Problems (CSPs). In particular, we introduce a notion of the \emph{spectral energy} of a fractional assignment for a Boolean CSP instance, and define a \emph{spectral sparsifier} as a weighted subset of constraints that approximately preserves this energy for all fractional assignments. Our definition not only strengthens the combinatorial notion of a CSP sparsifier but also extends well-studied concepts such as spectral sparsifiers for graphs and hypergraphs. Recent work by Khanna, Putterman, and Sudan [SODA 2024] demonstrated near-linear sized \emph{combinatorial sparsifiers} for a broad class of CSPs, which they term \emph{field-affine CSPs}. Our main result is a polynomial-time algorithm that constructs a spectral CSP sparsifier of near-quadratic size for all field-affine CSPs. This class of CSPs includes graph (and hypergraph) cuts, XORs, and more generally, any predicate which can be written as $P(x_1, \dots x_r) = \mathbf{1}[\sum a_i x_i \neq b \mod p]$. Based on our notion of the spectral energy of a fractional assignment, we also define an analog of the second eigenvalue of a CSP instance. We then show an extension of Cheeger's inequality for all even-arity XOR CSPs, showing that this second eigenvalue loosely captures the ``expansion'' of the underlying CSP. This extension specializes to the case of Cheeger's inequality when all constraints are even XORs and thus gives a new generalization of this powerful inequality which converts the combinatorial notion of expansion to an analytic property.Open AccessA Theory of Spectral CSP Sparsification
We initiate the study of spectral sparsification for instances of Constraint Satisfaction Problems (CSPs). In particular, we introduce a notion of the \emph{spectral energy} of a fractional assignment for a Boolean CSP instance, and define a \emph{spectral sparsifier} as a weighted subset of constraints that approximately preserves this energy for all fractional assignments. Our definition not only strengthens the combinatorial notion of a CSP sparsifier but also extends well-studied concepts such as spectral sparsifiers for graphs and hypergraphs. Recent work by Khanna, Putterman, and Sudan [SODA 2024] demonstrated near-linear sized \emph{combinatorial sparsifiers} for a broad class of CSPs, which they term \emph{field-affine CSPs}. Our main result is a polynomial-time algorithm that constructs a spectral CSP sparsifier of near-quadratic size for all field-affine CSPs. This class of CSPs includes graph (and hypergraph) cuts, XORs, and more generally, any predicate which can be written as $P(x_1, \dots x_r) = \mathbf{1}[\sum a_i x_i \neq b \mod p]$. Based on our notion of the spectral energy of a fractional assignment, we also define an analog of the second eigenvalue of a CSP instance. We then show an extension of Cheeger's inequality for all even-arity XOR CSPs, showing that this second eigenvalue loosely captures the ``expansion'' of the underlying CSP. This extension specializes to the case of Cheeger's inequality when all constraints are even XORs and thus gives a new generalization of this powerful inequality which converts the combinatorial notion of expansion to an analytic property. - 13 February 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 2591-2603
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
The goal of the trace reconstruction problem is to recover a string$\mathbf {x}\in \{0,1\}^{n}$ given many independent traces of x, where a trace is a subsequence obtained from deleting bits of x independently with some given probability$p\in [0,1$ ). A recent result of Chase (STOC 2021) shows how x can be determined (in exponential time) from$\exp ({O}(n^{1/5})\log ^{5} n)$ traces. This is the state-of-the-art result on the sample complexity of trace reconstruction. In this paper we consider two kinds of algorithms for the trace reconstruction problem. We first observe that the bound of Chase, which is based on statistics of arbitrary length-k subsequences, can also be obtained by considering the “k-mer statistics”, i.e., statistics regarding occurrences of contiguous k-bit strings (a.k.a, k-mers) in the initial string x, for$k = 2n^{1/5}$ . Mazooji and Shomorony (arXiv.2210.10917) show that such statistics (called k-mer density map) can be estimated within$\varepsilon $ accuracy from$ {\mathrm {poly}} (n, 2^{k}, 1/ {\varepsilon })$ traces. We call an algorithm to be k-mer-based if it reconstructs x given estimates of the k-mer density map. Such algorithms essentially capture all the analyses in the worst-case and smoothed-complexity models of the trace reconstruction problem we know of so far. Our first, and technically more involved, result shows that any k-mer-based algorithm for trace reconstruction must use$\exp (\Omega (n^{1/5} \sqrt {\log n}))$ traces, thus establishing the optimality of this number of traces. The analysis of this result also shows that the analysis technique used by Chase (STOC 2021) is essentially tight, and hence new techniques are needed in order to improve the worst-case upper bound. This result is shown by considering an appropriate class of real polynomials, that have been previously studied in the context of trace estimation (De, O’Donnell, Servedio. Annals of Probability 2019; Nazarov, Peres. STOC 2017), and proving that two of these polynomials are very close to each other on an arc in the complex plane. Our proof of the proximity of such polynomials uses new technical ingredients that allow us to focus on just a few coefficients of these polynomials. Our second, simple, result considers the performance of the Maximum Likelihood Estimator (MLE), which specifically picks the source string that has the maximum likelihood to generate the samples (traces). We show that the MLE algorithm uses a nearly optimal number of traces, i.e., up to a factor of n in the number of samples needed for an optimal algorithm, and show that this factor of n loss may be necessary under general “model estimation” settings.- 13 February 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 2591-2603
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
The goal of the trace reconstruction problem is to recover a string$\mathbf {x}\in \{0,1\}^{n}$ given many independent traces of x, where a trace is a subsequence obtained from deleting bits of x independently with some given probability$p\in [0,1$ ). A recent result of Chase (STOC 2021) shows how x can be determined (in exponential time) from$\exp ({O}(n^{1/5})\log ^{5} n)$ traces. This is the state-of-the-art result on the sample complexity of trace reconstruction. In this paper we consider two kinds of algorithms for the trace reconstruction problem. We first observe that the bound of Chase, which is based on statistics of arbitrary length-k subsequences, can also be obtained by considering the “k-mer statistics”, i.e., statistics regarding occurrences of contiguous k-bit strings (a.k.a, k-mers) in the initial string x, for$k = 2n^{1/5}$ . Mazooji and Shomorony (arXiv.2210.10917) show that such statistics (called k-mer density map) can be estimated within$\varepsilon $ accuracy from$ {\mathrm {poly}} (n, 2^{k}, 1/ {\varepsilon })$ traces. We call an algorithm to be k-mer-based if it reconstructs x given estimates of the k-mer density map. Such algorithms essentially capture all the analyses in the worst-case and smoothed-complexity models of the trace reconstruction problem we know of so far. Our first, and technically more involved, result shows that any k-mer-based algorithm for trace reconstruction must use$\exp (\Omega (n^{1/5} \sqrt {\log n}))$ traces, thus establishing the optimality of this number of traces. The analysis of this result also shows that the analysis technique used by Chase (STOC 2021) is essentially tight, and hence new techniques are needed in order to improve the worst-case upper bound. This result is shown by considering an appropriate class of real polynomials, that have been previously studied in the context of trace estimation (De, O’Donnell, Servedio. Annals of Probability 2019; Nazarov, Peres. STOC 2017), and proving that two of these polynomials are very close to each other on an arc in the complex plane. Our proof of the proximity of such polynomials uses new technical ingredients that allow us to focus on just a few coefficients of these polynomials. Our second, simple, result considers the performance of the Maximum Likelihood Estimator (MLE), which specifically picks the source string that has the maximum likelihood to generate the samples (traces). We show that the MLE algorithm uses a nearly optimal number of traces, i.e., up to a factor of n in the number of samples needed for an optimal algorithm, and show that this factor of n loss may be necessary under general “model estimation” settings.- Open Access
- 30 January 2025
- Published by National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 122 (5)
Errors are robustly tamed in cumulative knowledge processes
As knowledge accumulates in science and society in a distributed fashion, erroneous derivations can be introduced into the corpus of knowledge. Such derivations can compromise the validity of any units of knowledge that rely on them in the future. Can societal knowledge maintain some level of integrity given simple distributed error-checking mechanisms? In this paper, we investigate the following formulation of the question: assuming that a constant fraction of the new derivations is wrong, is it possible for simple error-checking mechanisms that apply when a new unit of knowledge is derived to maintain the integrity of the corpus of knowledge? This question was introduced by Ben-Eliezer et al. [“Is this correct? Let’s check!” in 14th Innovations in Theoretical Computer Science Conference (ITCS, 2023)], who gave a robust affirmative answer in a specific probabilistic model for knowledge accumulation. Namely, this model required that new units depend on just one existing unit and join the process according to a preferential attachment rule. In this work, we consider much more general families of processes of knowledge accumulation, where new units may depend on multiple existing units and join according to varied attachment mechanisms. We also consider models with a (random) fraction of insertions of adversarial nodes. We give a robust affirmative answer to the above question by showing that for all of these models, as long as many of the units follow simple local heuristics for checking a bounded number of units they depend on, all errors will be eventually eliminated.
- 30 January 2025
- Published by National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 122 (5)
Open AccessErrors are robustly tamed in cumulative knowledge processes
As knowledge accumulates in science and society in a distributed fashion, erroneous derivations can be introduced into the corpus of knowledge. Such derivations can compromise the validity of any units of knowledge that rely on them in the future. Can societal knowledge maintain some level of integrity given simple distributed error-checking mechanisms? In this paper, we investigate the following formulation of the question: assuming that a constant fraction of the new derivations is wrong, is it possible for simple error-checking mechanisms that apply when a new unit of knowledge is derived to maintain the integrity of the corpus of knowledge? This question was introduced by Ben-Eliezer et al. [“Is this correct? Let’s check!” in 14th Innovations in Theoretical Computer Science Conference (ITCS, 2023)], who gave a robust affirmative answer in a specific probabilistic model for knowledge accumulation. Namely, this model required that new units depend on just one existing unit and join the process according to a preferential attachment rule. In this work, we consider much more general families of processes of knowledge accumulation, where new units may depend on multiple existing units and join according to varied attachment mechanisms. We also consider models with a (random) fraction of insertions of adversarial nodes. We give a robust affirmative answer to the above question by showing that for all of these models, as long as many of the units follow simple local heuristics for checking a bounded number of units they depend on, all errors will be eventually eliminated.