On the public citation graph

Optimal Hardness Results for Maximizing Agreements with Monomials

0 signed · 45 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/jcss.1995.1011openalex-snapshot
Robust Trainability of Single Neurons
inferredcites →https://doi.org/10.1007/3-540-36169-3_9openalex-snapshot
Maximizing Agreements and CoAgnostic Learning
inferredcites →https://doi.org/10.1007/3-540-45435-7_19openalex-snapshot
Bounds for the Minimum Disagreement Problem with Applications to Learning Theory
inferredcites →https://doi.org/10.1007/bf00116829openalex-snapshot
Learning From Noisy Examples
inferredcites →https://doi.org/10.1007/bf00993468openalex-snapshot
Toward efficient agnostic learning
inferredcites →https://doi.org/10.1007/bf01200426openalex-snapshot
Majority gates vs. general weighted threshold gates
inferredcites →https://doi.org/10.1016/0304-3975(94)00254-gopenalex-snapshot
The complexity and approximability of finding maximum feasible subsystems of linear relations
inferredcites →https://doi.org/10.1016/0890-5401(92)90010-dopenalex-snapshot
Decision theoretic generalizations of the PAC model for neural net and other learning applications
inferredcites →https://doi.org/10.1016/j.tcs.2005.10.014openalex-snapshot
Maximizing agreements and coagnostic learning
inferredcites →https://doi.org/10.1016/s0022-0000(03)00038-2openalex-snapshot
On the difficulty of approximately maximizing agreements
inferredcites →https://doi.org/10.1109/focs.2004.36openalex-snapshot
Learnability and Automatizability
inferredcites →https://doi.org/10.1109/sfcs.2005.13openalex-snapshot
Agnostically Learning Halfspaces
inferredcites →https://doi.org/10.1137/0222052openalex-snapshot
Learning in the Presence of Malicious Errors
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
inferredcites →https://doi.org/10.1145/130385.130424openalex-snapshot
Toward efficient agnostic learning
inferredcites →https://doi.org/10.1145/185675.306789openalex-snapshot
On the hardness of approximating minimization problems
inferredcites →https://doi.org/10.1145/1968.1972openalex-snapshot
A theory of the learnable
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/258533.258641openalex-snapshot
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
inferredcites →https://doi.org/10.1145/278298.278306openalex-snapshot
Proof verification and the hardness of approximation problems
inferredcites →https://doi.org/10.1145/28395.28426openalex-snapshot
On the learnability of Boolean formulae
inferredcites →https://doi.org/10.1145/285055.285059openalex-snapshot
A threshold of ln n for approximating set cover
inferredcites →https://doi.org/10.1145/3749740.3749746openalex-snapshot
A Theory of the Learnable
inferredcites →https://doi.org/10.1145/48014.63140openalex-snapshot
Computational limitations on learning from examples

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-0-387-30162-4_177openalex-snapshot
Hardness of Proper Learning
inferred← citeshttps://doi.org/10.1007/springerreference_57696openalex-snapshot
Hardness of Proper Learning, 1988; Pitt, Valiant
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.02.023openalex-snapshot
Self-improved gaps almost everywhere for the agnostic approximation of monomials
inferred← citeshttps://doi.org/10.1109/focs.2006.33openalex-snapshot
Hardness of Learning Halfspaces with Noise
inferred← citeshttps://doi.org/10.1109/focs.2006.51openalex-snapshot
New Results for Learning Noisy Parities and Halfspaces
inferred← citeshttps://doi.org/10.1109/focs.2007.31openalex-snapshot
Simulating Quantum Correlations with Finite Communication
inferred← citeshttps://doi.org/10.1109/focs.2007.37openalex-snapshot
Hardness of Reconstructing Multivariate Polynomials over Finite Fields
inferred← citeshttps://doi.org/10.1109/focs.2008.35openalex-snapshot
On Basing Lower-Bounds for Learning on Worst-Case Assumptions
inferred← citeshttps://doi.org/10.1109/focs.2008.37openalex-snapshot
Hardness of Minimizing and Learning DNF Expressions
inferred← citeshttps://doi.org/10.1109/focs.2009.26openalex-snapshot
Agnostic Learning of Monomials by Halfspaces Is Hard
inferred← citeshttps://doi.org/10.1137/070684914openalex-snapshot
On Agnostic Learning of Parities, Monomials, and Halfspaces
inferred← citeshttps://doi.org/10.1137/070685798openalex-snapshot
Hardness of Learning Halfspaces with Noise
inferred← citeshttps://doi.org/10.1137/070705258openalex-snapshot
Hardness of Reconstructing Multivariate Polynomials over Finite Fields
inferred← citeshttps://doi.org/10.1137/1.9781611972771.21openalex-snapshot
Boosting Optimal Logical Patterns Using Noisy Data
inferred← citeshttps://doi.org/10.1145/3406325.3451067openalex-snapshot
Hardness of learning DNFs using halfspaces
inferred← citeshttps://doi.org/10.1184/r1/6606365openalex-snapshot
Improved Guarantees for Agnostic Learning of Disjunctions
inferred← citeshttps://doi.org/10.1184/r1/6714833openalex-snapshot
Approximation Algorithms and New Models for Clustering and Learning
inferred← citeshttps://doi.org/10.1287/ijoc.1110.0459openalex-snapshot
An Improved Branch-and-Bound Method for Maximum Monomial Agreement
inferred← citeshttps://doi.org/10.1609/aaai.v31i1.10700openalex-snapshot
An Improved Algorithm for Learning to Perform Exception-Tolerant Abduction
inferred← citeshttps://doi.org/10.7282/t3dr2vn1openalex-snapshot
Optimization for sparse and accurate classifiers
inferred← citeshttps://doi.org/10.7936/k7jh3jm6openalex-snapshot
An Improved Algorithm for Learning to Perform Exception-Tolerant Abduction
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.