Learning Disjunction of Conjunctions

By Leslie G. Valiant. 1985

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Robust multivariate mean estimation: The optimality of trimmed mean (2019, background): “Its origins may be traced back to the malicious noise model of Valiant [29] and Kearns and Li [16].”
Learning to reason (1994, background): “Oracles that seem to be relevant in this context are partial assignments oracles [Valiant 1985] more selective oracles such as Amsterdam s [1988] experiment oracle and Valiant s [1995] actions in the rationality model, and perhaps the use of declarative information.”
Agnostically learning halfspaces (2005, methodology): “We now consider the problem of PAC learning an unknown origin-centered halfspace, under the uniform distribution on Sn 1, in the demanding malicious noise model introduced by Valiant [ 35 ] and subsequently studied by Kearns and Li [18] and many others.”
Queries and concept learning (1988, methodology): “Work by Valiant (1985) , Kearns and Li (1987), Angluin and Laird (1987), and Laird (1987) on malicious and random errors has begun to clarify the effect of errors on identification and learning.”
Blockwise p-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners (2017, background): “For all of our attacks, all adversary needs is to ‘continue’ the computation done by the learner, and knowing the current state (as in Valiant’s model) allows us to do so, even if the previous blocks are unknown.”
Classification in the Presence of Label Noise: A Survey (2014, background): “In this survey, label noise is considered to be a stochastic process, i.e., the case where the labeling errors may be intentionally (like e.g. in the food industry [13]–[16]) and maliciously induced by an adversary agent [17]–[26] is not considered.”
Dataset Security for Machine Learning: Data Poisoning, Backdoor Attacks, and Defenses (2020, background): “of data corruption where each bit is perturbed with probability p [63], [64].”
Exact Rule Learning via Boolean Compressed Sensing (2013, background): “…widely used by analytics practitioners today precisely due to their interpretability, rely on greedy, heuristic training procedures because rule learning is inherently combinatorial and notoriously difficult from the perspective of the theory of computation (Valiant, 1985; Kearns & Vazirani, 1994).”
Mixture models, robustness, and sum of squares proofs (2017, background): “There has been a long line of work on making algorithms tolerant to error in supervised settings [41, 66], especially for learning halfspaces [4, 28, 42, 60], and for problems such as PCA [15, 16, 47, 70].”
Can machine learning be secure? (2006, unknown): “They worked in the context of Valiant’s Probably Approximately Correct (PAC) learning framework [35, 36 ], extending it to prove bounds for maliciously chosen errors in the training data.”
Learning Halfspaces with Malicious Noise (2009, methodology): “In this model, introduced by Valiant [ 27 ] (see also [12]), there is an unknown target function f and distribution D over examples.”