Publication:2986855

DOI10.1145/2422436.2422440zbMATH Open1362.68123OpenAlexW1967138953MaRDI QIDQ2986855FDOQ2986855

Philip M. Long, Rocco A. Servedio

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2422436.2422440

zbMATH Keywords

hyperplanehalfspacelinear threshold functionHamming balllinear separator

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A theory of the learnable
• On the power of inductive inference from good examples
• Occam's razor
• Teaching a smarter learner.
• Derandomizing polynomial identity tests means proving circuit lower bounds
• On specifying Boolean functions by labelled examples
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Pseudorandom generators for space-bounded computation
• On the complexity of teaching
• Teachability in computational learning
• A model of interactive teaching
• Learning from different teachers
• Algorithmic Learning Theory
• On the limits of efficient teachability
• Measuring teachability using variants of the teaching dimension
• A theory of goal-oriented communication
• Recent Developments in Algorithmic Teaching
• Teaching Randomized Learners

Recommendations

• Learning Boolean halfspaces with small weights from membership queries 👍 👎
• Optimal indexes for sparse bit vectors 👍 👎
• Approximating sparse binary matrices in the cut-norm 👍 👎
• A sparse matrix algorithm on the Boolean vector machine 👍 👎
• Sparse learning via Boolean relaxations 👍 👎
• Sparse representation of vectors in lattices and semigroups 👍 👎
• Sparse Boolean equations and circuit lattices 👍 👎
• Learning Boolean Halfspaces with Small Weights from Membership Queries 👍 👎
• Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity 👍 👎
• Small Linear Dependencies for Binary Vectors of Low Weight 👍 👎

This page was built for publication: Low-weight halfspaces for sparse boolean vectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986855)