Exact learning from an honest teacher that answers membership queries (Q2636406)

From MaRDI portal

Revision as of 12:38, 19 December 2024 by Import241208061232 (talk | contribs) (Normalize DOI.)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to:navigation, search

scientific article

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

Statements

scholarly article

0 references

Exact learning from an honest teacher that answers membership queries (English)

0 references

Nader H. Bshouty

0 references

Theoretical Computer Science

0 references

publication date

5 June 2018

0 references

full work available at URL

https://arxiv.org/abs/1706.03935

0 references

zbMATH Keywords

exact learning

0 references

membership queries

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

Queries and concept learning

0 references

Learning regular sets from queries and counterexamples

0 references

0 references

New Construction of Error-Tolerant Pooling Designs

0 references

Learning a Hidden Subgraph

0 references

Learning Boolean Halfspaces with Small Weights from Membership Queries

0 references

The complexity of properly learning simple concept classes

0 references

Learning a Hidden Matching

0 references

On Exact Learning Monotone DNF from Membership Queries

0 references

Non-adaptive Learning of a Hidden Hypergraph

0 references

0 references

Learning a hidden graph using \(O(\log n)\)queries per edge

0 references

Learning conjunctions of Horn clauses

0 references

Point probe decision trees for geometric concept classes

0 references

Complexity theoretic hardness results for query learning

0 references

Learning read-once formulas with queries

0 references

0 references

Malicious omissions and errors in answers to membership queries

0 references

Algorithmic construction of sets for <i>k</i> -restrictions

0 references

Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle

0 references

0 references

Quasi-polynomial hitting-set for set-depth-Δ formulas

0 references

Pseudorandom generators for low degree polynomials

0 references

Exact learning Boolean functions via the monotone theory

0 references

Simple learning algorithms using divide and conquer

0 references

0 references

Exact learning of formulas in parallel

0 references

On the Coin Weighing Problem with the Presence of Noise

0 references

Testers and their applications

0 references

Exact Learning from Membership Queries: Some Techniques, Results and New Directions

0 references

Linear Time Constructions of Some $$d$$-Restriction Problems

0 references

On interpolating arithmetic read-once formulas with exponentiation

0 references

Learning functions represented as multiplicity automata

0 references

Learning with errors in answers to membership queries

0 references

0 references

Oracles and queries that are sufficient for exact learning

0 references

Interpolating Arithmetic Read-Once Formulas in Parallel

0 references

Exact learning of juntas from membership queries

0 references

Almost optimal set covers in finite VC-dimension

0 references

Asking questions to minimize errors

0 references

Graph-Theoretic Concepts in Computer Science

0 references

Optimal Two-Stage Algorithms for Group Testing Problems

0 references

Attribute-efficient learning in query and mistake-bound models

0 references

Learning Boolean read-once formulas over generalized bases

0 references

Learning Arithmetic Read-Once Formulas

0 references

An algorithm to learn read-once threshold formulas, and transformations between learning models

0 references

Learning in the presence of finitely or infinitely many irrelevant attributes

0 references

Deterministically testing sparse polynomial identities of unbounded degree

0 references

Asymptotically Optimal Hitting Sets Against Polynomials

0 references

More efficient PAC-learning of DNF with membership queries under the uniform distribution

0 references

On Polynomial Time Constructions of Minimum Height Decision Tree

0 references

Simple Learning Algorithms for Decision Trees and Multivariate Polynomials

0 references

Optimal Query Complexity for Reconstructing Hypergraphs

0 references

0 references

Reconstructing weighted graphs with minimal query complexity

0 references

Toward a deterministic polynomial time algorithm with optimal additive query complexity

0 references

Fast identification of geometric objects with membership queries

0 references

Fast learning of \(k\)-term DNF formulas with queries.

0 references

Improved algorithms for group testing with inhibitors

0 references

Determining a Set from the Cardinalities of its Intersections with Other Sets

0 references

Tree algorithms for packet broadcast channels

0 references

Improved constructions for non-adaptive threshold group testing

0 references

Noise-resilient group testing: limitations and constructions

0 references

An efficient randomized group testing procedure to determine the number of defectives

0 references

A Greedy Heuristic for the Set-Covering Problem

0 references

Fault-tolerant search algorithms. Reliable computation with unreliable information

0 references

Reconstruction of hidden graphs and threshold group testing

0 references

On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields

0 references

A Zig-Zag Approach for Competitive Group Testing

0 references

Learning a hidden graph

0 references

Learning read-constant polynomials of constant degree modulo composites

0 references

A survey on nonadaptive group testing algorithms through the angle of decoding

0 references

Efficient Algorithms for Noisy Group Testing

0 references

0 references

Optimal query complexity bounds for finding graphs

0 references

Partial Derivatives in Arithmetic Complexity and Beyond

0 references

Non-adaptive complex group testing with multiple positive sets

0 references

Determination of a Subset from Certain Combinatorial Properties

0 references

0 references

Perfect two-fault tolerant search with minimum adaptiveness

0 references

0 references

Adaptive versus nonadaptive attribute-efficient learning

0 references

On parallel attribute-efficient learning.

0 references

0 references

0 references

COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY

0 references

Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives

0 references

Randomized Group Testing Both Query-Optimal and Minimal Adaptive

0 references

Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries

0 references

0 references

Analytical approach to parallel repetition

0 references

Families of finite sets in which no intersection of \(\ell\) sets is covered by the union of \(s\) others

0 references

Bounds on the rate of disjunctive codes

0 references

Erratum to: ``Bounds on the rate of disjunctive codes''

0 references

Modifications of Competitive Group Testing

0 references

Improved Combinatorial Group Testing Algorithms for Real‐World Problem Sizes

0 references

Hitting sets when the VC-dimension is small

0 references

A threshold of ln <i>n</i> for approximating set cover

0 references

0 references

On \(r\)-cover-free families

0 references

Learning from a consistently ignorant teacher

0 references

Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms

0 references

Optimal Binary Identification Procedures

0 references

0 references

Ulam's searching game with two lies

0 references

Construction of \(d(H)\)\,-\,disjunct matrix for group testing in hypergraphs

0 references

0 references

On the complexity of teaching

0 references

Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping

0 references

Optimal reconstruction of graphs under the additive model

0 references

Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions

0 references

Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields

0 references

Learning via queries

0 references

An Algebraic Perspective on Boolean Function Learning

0 references

Combinatorial results on the complexity of teaching and learning

0 references

A Method for Detecting All Defective Members in a Population by Group Testing

0 references

RANDOM <i>k</i>-SET POOL DESIGNS WITH DISTINCT COLUMNS

0 references

The identification of positive clones in a general inhibitor model

0 references

0 references

THE EXPECTED NUMBERS OF UNRESOLVED POSITIVE CLONES FOR VARIOUS RANDOM POOL DESIGNS

0 references

Constructing optimal binary decision trees is NP-complete

0 references

\(\epsilon\)-nets and simplex range queries

0 references

0 references

An efficient membership-query algorithm for learning DNF with respect to the uniform distribution

0 references

Learning random monotone DNF

0 references

0 references

Learning with queries corrupted by classification noise

0 references

Reducibility among Combinatorial Problems

0 references

0 references

Efficient noise-tolerant learning from statistical queries

0 references

0 references

A simple algorithm for learning O(log n)-term DNF

0 references

Derandomizing polynomial identity tests means proving circuit lower bounds

0 references

Learning in the Presence of Malicious Errors

0 references

Learning Decision Trees Using the Fourier Spectrum

0 references

Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in

0 references

PAC learning intersections of halfspaces with membership queries

0 references

Nonrandom binary superimposed codes

0 references

Families of \(k\)-independent sets

0 references

On some approximation problems concerning sparse polynomials over finite fields

0 references

Randomness efficient identity testing of multivariate polynomials

0 references

Blackbox Polynomial Identity Testing for Depth 3 Circuits

0 references

A Sequential Method for Screening Experimental Variables

0 references

0 references

On a Combinatorial Problem in Number Theory

0 references

0 references

Constant depth circuits, Fourier transform, and learnability

0 references

On the hardness of the minimum height decision tree problem

0 references

ERROR-TOLERANT TRIVIAL TWO-STAGE GROUP TESTING FOR COMPLEXES USING ALMOST SEPARABLE AND ALMOST DISJUNCT MATRICES

0 references

Multi-user communication systems

0 references

0 references

0 references

0 references

Transactions on Rough Sets I

0 references

A group testing method for finding patterns in data

0 references

Trivial two-stage group testing for complexes using almost disjunct matrices.

0 references

Lower bound methods and separation results for on-line learning models

0 references

On a bound of cover-free families

0 references

0 references

0 references

0 references

On learning monotone Boolean functions with irrelevant variables

0 references

Solution of Ulam's problem on searching with a lie

0 references

0 references

Searching games with errors -- fifty years of coping with liars

0 references

Bounds on the performance of protocols for a multiple-access broadcast channel

0 references

Explicit Nonadaptive Combinatorial Group Testing Schemes

0 references

0 references

On the theory of random search

0 references

On the upper bound of the size of the \(r\)-cover-free families

0 references

Coping with errors in binary search procedures

0 references

Deterministic polynomial identity testing in non-commutative models

0 references

Testing geometric objects

0 references

0 references

Learning and Verifying Graphs Using Queries with a Focus on Edge Counting

0 references

How an Erdos-Renyi-type search approach gives an explicit code construction of rate 1 for random access with multiplicity feedback

0 references

On learning from queries and counterexamples in the presence of noise

0 references

Progress on Polynomial Identity Testing - II

0 references

Fast Probabilistic Algorithms for Verification of Polynomial Identities

0 references

On the limits of efficient teachability

0 references

On the definition of a family of automata

0 references

Ulam's searching game with a fixed number of lies

0 references

On the Detection of Defective Members of Large Populations

0 references

Vector sets for exhaustive testing of logic circuits

0 references

0 references

Teachability in computational learning

0 references

A Combinatory Detection Problem

0 references

Learning sparse multivariate polynomials over a field with queries and counterexamples.

0 references

Blackbox identity testing for bounded top fanin depth-3 circuits

0 references

0 references

Improved Results for Competitive Group Testing

0 references

Arithmetic Circuits: A survey of recent results and open questions

0 references

Improved Polynomial Identity Testing for Read-Once Formulas

0 references

0 references

Black-box identity testing of depth-4 multilinear circuits

0 references

Three Thresholds for a Liar

0 references

Some new bounds for cover-free families

0 references

0 references

Sets pooling designs

0 references

A group testing problem for hypergraphs of bounded rank

0 references

0 references

A theory of the learnable

0 references

The complexity of sparse polynomial interpolation over finite fields

0 references

0 references

Born again group testing: Multiaccess communications

0 references

0 references

0 references

Identifiers

zbMATH Open document ID

0 references

Mathematics Subject Classification ID

0 references

zbMATH DE Number

0 references

0 references

0 references

0 references

10.1016/J.TCS.2018.04.034

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2636406

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2636406&oldid=39171749"