Low-weight halfspaces for sparse boolean vectors

DOI10.1145/2422436.2422440MaRDI QIDQ2986855zbMATH OpenOpenAlexFDO

Authors 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

halfspaceHamming ballhyperplanelinear separatorlinear threshold function

Mathematics Subject Classification ID

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

Recommendations

• A sparse matrix algorithm on the Boolean vector machine
• Learning Boolean halfspaces with small weights from membership queries
• Learning Boolean halfspaces with small weights from membership queries
• Small Linear Dependencies for Binary Vectors of Low Weight
• Sparse Boolean equations and circuit lattices
• Near-optimal upper bound on Fourier dimension of Boolean functions in terms of Fourier sparsity
• Optimal indexes for sparse bit vectors
• Sparse learning via Boolean relaxations
• Approximating sparse binary matrices in the cut-norm
• Sparse representation of vectors in lattices and semigroups

Cites work

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

Cited in

(1)

• Learning Boolean halfspaces with small weights from membership queries

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)