Exact learning from an honest teacher that answers membership queries (Q2636406): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Created claim: Wikidata QID (P12): Q109042220, #quickstatements; #temporary_batch_1721925744443
 
(3 intermediate revisions by 3 users not shown)
Property / OpenAlex ID
 
Property / OpenAlex ID: W2963765477 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1706.03935 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3994535 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Queries and concept learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning regular sets from queries and counterexamples / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4473537 / rank
 
Normal rank
Property / cites work
 
Property / cites work: New Construction of Error-Tolerant Pooling Designs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning a Hidden Subgraph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning Boolean Halfspaces with Small Weights from Membership Queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of properly learning simple concept classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning a Hidden Matching / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Exact Learning Monotone DNF from Membership Queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Non-adaptive Learning of a Hidden Hypergraph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3174038 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning a hidden graph using \(O(\log n)\)queries per edge / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning conjunctions of Horn clauses / rank
 
Normal rank
Property / cites work
 
Property / cites work: Point probe decision trees for geometric concept classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity theoretic hardness results for query learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning read-once formulas with queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4230377 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Malicious omissions and errors in answers to membership queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algorithmic construction of sets for <i>k</i> -restrictions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3503433 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quasi-polynomial hitting-set for set-depth-Δ formulas / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pseudorandom generators for low degree polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact learning Boolean functions via the monotone theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: Simple learning algorithms using divide and conquer / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4542579 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact learning of formulas in parallel / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Coin Weighing Problem with the Presence of Noise / rank
 
Normal rank
Property / cites work
 
Property / cites work: Testers and their applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact Learning from Membership Queries: Some Techniques, Results and New Directions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear Time Constructions of Some $$d$$-Restriction Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: On interpolating arithmetic read-once formulas with exponentiation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning functions represented as multiplicity automata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning with errors in answers to membership queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5687002 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Oracles and queries that are sufficient for exact learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Interpolating Arithmetic Read-Once Formulas in Parallel / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact learning of juntas from membership queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Almost optimal set covers in finite VC-dimension / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asking questions to minimize errors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph-Theoretic Concepts in Computer Science / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Two-Stage Algorithms for Group Testing Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Attribute-efficient learning in query and mistake-bound models / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning Boolean read-once formulas over generalized bases / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning Arithmetic Read-Once Formulas / rank
 
Normal rank
Property / cites work
 
Property / cites work: An algorithm to learn read-once threshold formulas, and transformations between learning models / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning in the presence of finitely or infinitely many irrelevant attributes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Deterministically testing sparse polynomial identities of unbounded degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotically Optimal Hitting Sets Against Polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: More efficient PAC-learning of DNF with membership queries under the uniform distribution / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Polynomial Time Constructions of Minimum Height Decision Tree / rank
 
Normal rank
Property / cites work
 
Property / cites work: Simple Learning Algorithms for Decision Trees and Multivariate Polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Query Complexity for Reconstructing Hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5365125 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reconstructing weighted graphs with minimal query complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Toward a deterministic polynomial time algorithm with optimal additive query complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast identification of geometric objects with membership queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast learning of \(k\)-term DNF formulas with queries. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Improved algorithms for group testing with inhibitors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Determining a Set from the Cardinalities of its Intersections with Other Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tree algorithms for packet broadcast channels / rank
 
Normal rank
Property / cites work
 
Property / cites work: Improved constructions for non-adaptive threshold group testing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Noise-resilient group testing: limitations and constructions / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient randomized group testing procedure to determine the number of defectives / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fault-tolerant search algorithms. Reliable computation with unreliable information / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reconstruction of hidden graphs and threshold group testing / rank
 
Normal rank
Property / cites work
 
Property / cites work: On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Zig-Zag Approach for Competitive Group Testing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning a hidden graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning read-constant polynomials of constant degree modulo composites / rank
 
Normal rank
Property / cites work
 
Property / cites work: A survey on nonadaptive group testing algorithms through the angle of decoding / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient Algorithms for Noisy Group Testing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5302100 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal query complexity bounds for finding graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Partial Derivatives in Arithmetic Complexity and Beyond / rank
 
Normal rank
Property / cites work
 
Property / cites work: Non-adaptive complex group testing with multiple positive sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Determination of a Subset from Certain Combinatorial Properties / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4938780 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Perfect two-fault tolerant search with minimum adaptiveness / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2722011 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Adaptive versus nonadaptive attribute-efficient learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: On parallel attribute-efficient learning. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4506360 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5395177 / rank
 
Normal rank
Property / cites work
 
Property / cites work: COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives / rank
 
Normal rank
Property / cites work
 
Property / cites work: Randomized Group Testing Both Query-Optimal and Minimal Adaptive / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4745752 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Analytical approach to parallel repetition / rank
 
Normal rank
Property / cites work
 
Property / cites work: Families of finite sets in which no intersection of \(\ell\) sets is covered by the union of \(s\) others / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds on the rate of disjunctive codes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Erratum to: ``Bounds on the rate of disjunctive codes'' / rank
 
Normal rank
Property / cites work
 
Property / cites work: Modifications of Competitive Group Testing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Improved Combinatorial Group Testing Algorithms for Real‐World Problem Sizes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hitting sets when the VC-dimension is small / rank
 
Normal rank
Property / cites work
 
Property / cites work: A threshold of ln <i>n</i> for approximating set cover / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3174124 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On \(r\)-cover-free families / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning from a consistently ignorant teacher / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Binary Identification Procedures / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4218421 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ulam's searching game with two lies / rank
 
Normal rank
Property / cites work
 
Property / cites work: Construction of \(d(H)\)\,-\,disjunct matrix for group testing in hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4237365 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of teaching / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal reconstruction of graphs under the additive model / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning via queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Algebraic Perspective on Boolean Function Learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial results on the complexity of teaching and learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Method for Detecting All Defective Members in a Population by Group Testing / rank
 
Normal rank
Property / cites work
 
Property / cites work: RANDOM <i>k</i>-SET POOL DESIGNS WITH DISTINCT COLUMNS / rank
 
Normal rank
Property / cites work
 
Property / cites work: The identification of positive clones in a general inhibitor model / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4013534 / rank
 
Normal rank
Property / cites work
 
Property / cites work: THE EXPECTED NUMBERS OF UNRESOLVED POSITIVE CLONES FOR VARIOUS RANDOM POOL DESIGNS / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constructing optimal binary decision trees is NP-complete / rank
 
Normal rank
Property / cites work
 
Property / cites work: \(\epsilon\)-nets and simplex range queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4829004 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning random monotone DNF / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3002770 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning with queries corrupted by classification noise / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reducibility among Combinatorial Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5183260 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient noise-tolerant learning from statistical queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4766905 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A simple algorithm for learning O(log n)-term DNF / rank
 
Normal rank
Property / cites work
 
Property / cites work: Derandomizing polynomial identity tests means proving circuit lower bounds / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning in the Presence of Malicious Errors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning Decision Trees Using the Fourier Spectrum / rank
 
Normal rank
Property / cites work
 
Property / cites work: Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in / rank
 
Normal rank
Property / cites work
 
Property / cites work: PAC learning intersections of halfspaces with membership queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Nonrandom binary superimposed codes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Families of \(k\)-independent sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: On some approximation problems concerning sparse polynomials over finite fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Randomness efficient identity testing of multivariate polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: Blackbox Polynomial Identity Testing for Depth 3 Circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Sequential Method for Screening Experimental Variables / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5535504 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a Combinatorial Problem in Number Theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4109144 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constant depth circuits, Fourier transform, and learnability / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the hardness of the minimum height decision tree problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: ERROR-TOLERANT TRIVIAL TWO-STAGE GROUP TESTING FOR COMPLEXES USING ALMOST SEPARABLE AND ALMOST DISJUNCT MATRICES / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multi-user communication systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5417652 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4081256 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4742561 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Transactions on Rough Sets I / rank
 
Normal rank
Property / cites work
 
Property / cites work: A group testing method for finding patterns in data / rank
 
Normal rank
Property / cites work
 
Property / cites work: Trivial two-stage group testing for complexes using almost disjunct matrices. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lower bound methods and separation results for on-line learning models / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a bound of cover-free families / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5457049 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4231923 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3798601 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On learning monotone Boolean functions with irrelevant variables / rank
 
Normal rank
Property / cites work
 
Property / cites work: Solution of Ulam's problem on searching with a lie / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3783955 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Searching games with errors -- fifty years of coping with liars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds on the performance of protocols for a multiple-access broadcast channel / rank
 
Normal rank
Property / cites work
 
Property / cites work: Explicit Nonadaptive Combinatorial Group Testing Schemes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5331663 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the theory of random search / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the upper bound of the size of the \(r\)-cover-free families / rank
 
Normal rank
Property / cites work
 
Property / cites work: Coping with errors in binary search procedures / rank
 
Normal rank
Property / cites work
 
Property / cites work: Deterministic polynomial identity testing in non-commutative models / rank
 
Normal rank
Property / cites work
 
Property / cites work: Testing geometric objects / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4527015 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning and Verifying Graphs Using Queries with a Focus on Edge Counting / rank
 
Normal rank
Property / cites work
 
Property / cites work: How an Erdos-Renyi-type search approach gives an explicit code construction of rate 1 for random access with multiplicity feedback / rank
 
Normal rank
Property / cites work
 
Property / cites work: On learning from queries and counterexamples in the presence of noise / rank
 
Normal rank
Property / cites work
 
Property / cites work: Progress on Polynomial Identity Testing - II / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the limits of efficient teachability / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the definition of a family of automata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ulam's searching game with a fixed number of lies / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Detection of Defective Members of Large Populations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Vector sets for exhaustive testing of logic circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4013738 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Teachability in computational learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Combinatory Detection Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning sparse multivariate polynomials over a field with queries and counterexamples. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Blackbox identity testing for bounded top fanin depth-3 circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3081624 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Improved Results for Competitive Group Testing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Arithmetic Circuits: A survey of recent results and open questions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Improved Polynomial Identity Testing for Read-Once Formulas / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5302074 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Black-box identity testing of depth-4 multilinear circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Three Thresholds for a Liar / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some new bounds for cover-free families / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4247002 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sets pooling designs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A group testing problem for hypergraphs of bounded rank / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4121861 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A theory of the learnable / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of sparse polynomial interpolation over finite fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Guessing Games / rank
 
Normal rank
Property / cites work
 
Property / cites work: Born again group testing: Multiaccess communications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3851616 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4888930 / rank
 
Normal rank
Property / Wikidata QID
 
Property / Wikidata QID: Q109042220 / rank
 
Normal rank

Latest revision as of 17:49, 25 July 2024

scientific article
Language Label Description Also known as
English
Exact learning from an honest teacher that answers membership queries
scientific article

    Statements

    Exact learning from an honest teacher that answers membership queries (English)
    0 references
    0 references
    5 June 2018
    0 references
    exact learning
    0 references
    membership queries
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers