Low-weight halfspaces for sparse boolean vectors
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
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)
