Exact learning from an honest teacher that answers membership queries

DOI10.1016/j.tcs.2018.04.034zbMath1393.68146arXiv1706.03935OpenAlexW2963765477WikidataQ109042220 ScholiaQ109042220MaRDI QIDQ2636406

Nader H. Bshouty

Publication date: 5 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.03935

zbMATH Keywords

exact learningmembership queries

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (2)

Efficient multiple constraint acquisition ⋮ Learning of monotone functions with single error correction

Cites Work

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

This page was built for publication: Exact learning from an honest teacher that answers membership queries