Article

Free access

On restricted-focus-of-attention learnability of Boolean functions

Authors:

Hans Ulrich SimonAuthors Info & Claims

COLT '96: Proceedings of the ninth annual conference on Computational learning theory

Pages 205 - 216

https://doi.org/10.1145/238061.238098

Published: 01 January 1996 Publication History

PDF eReader

References

[1]

Shai Ben-David and Eli Dichterman. Learning with restricted focus of attention. In Proceedings of the 6th Annual Workshop on Computational Learning Theory, pages 287-296. ACM Press, New York, NY, 1993.

Digital Library

Google Scholar

[2]

Shai Ben-David and Eli Dichterman. Learnability with restricted focus of attention guarantees noise-tolerance. In 5th International Workshop on Algorithmic Learning Theory, ALT'94, pages 248-259, 1994.

Digital Library

Google Scholar

[3]

Jehoshua Bruck. Harmonic analysis of polynomial threshold functions. SIAM Journal of Discrete Mathematics, 3(2): 168-177, May 1990.

Crossref

Google Scholar

[4]

Scott E. Decatur and Rosario Gennaro. On learning from noisy and incomplete examples. In Proceedings of the 8th Annual Workshop on ComputationalLearning Theory, pages 353-360, 1995.

Digital Library

Google Scholar

[5]

Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie G. Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82:247-261, 1989. First appeared in Proceedings of the 1st Annual Workshop on Computational Learning Theory.

Digital Library

Google Scholar

[6]

Yoav Freund. Boosting a weak learning algorithm by majority. In Proceedings of the 3rd Annual Workshop on Computational Learning Theory, pages 202-216. Morgan Kaufmann, San Mateo, CA, 1990.

Digital Library

Google Scholar

[7]

Yoav Freund. Data Filtering and Distribution Modeling Algorithms for Machine Learning. PhD thesis, University of California, Santa Cruz, September 1993.

Digital Library

Google Scholar

[8]

Jeffrey C. Jackson. An efficient membershipquery algorithm for learning DNF with respect to the uniform distribution. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 42-53, 1994.

Digital Library

Google Scholar

[9]

Jeffrey Charles Jackson. The Harmonic Sieve: A Novel Application of FourierAnalysis to Machine Learning Theory and Practice. PhD thesis, Carnegie Mellon University, August 1995. Available as technical report CMU-CS-95-183.

Digital Library

Google Scholar

[10]

Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 392-401, 1993.

Digital Library

Google Scholar

[11]

Michael J. Kearns and Robert E. Schapire. Efficient distribution-free learning of probabilistic concepts. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 382-391, 1990.

Google Scholar

[12]

Ronald L. Rivest. Learning decision lists. Machine Learning, 2:229-246, 1987.

Digital Library

Google Scholar

Cited By

View all

Servedio R(2006)Every Linear Threshold Function has a Low-Weight ApproximatorProceedings of the 21st Annual IEEE Conference on Computational Complexity10.1109/CCC.2006.18(18-32)Online publication date: 16-Jul-2006
https://dl.acm.org/doi/10.1109/CCC.2006.18
Kwek SBen-David SLong P(1999)An apprentice learning model (extended abstract)Proceedings of the twelfth annual conference on Computational learning theory10.1145/307400.307413(63-74)Online publication date: 6-Jul-1999
https://dl.acm.org/doi/10.1145/307400.307413
Birkendorf AKlasner NKuhlmann CSimon HBartlett PMansour Y(1998)Structural results about exact learning with unspecified attribute valuesProceedings of the eleventh annual conference on Computational learning theory10.1145/279943.279974(144-153)Online publication date: 24-Jul-1998
https://dl.acm.org/doi/10.1145/279943.279974
Show More Cited By

Index Terms

On restricted-focus-of-attention learnability of Boolean functions
1. Computing methodologies
  1. Machine learning
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
  2. Models of computation
    1. Computability

Recommendations

Boolean functions with two distinct Walsh coefficients

Are there other Boolean functions having two distinct Walsh coefficients except affine Boolean functions and maximal nonlinear (i.e. bent) Boolean functions__ __ This paper proves that all Boolean functions with exactly two distinct Walsh coefficients ...
On Restricted-Focus-of-Attention Learnability of Boolean Functions
Special issue on the ninth annual conference on computational theory (COLT '96)

In the k -Restricted-Focus-of-Attention ( k -RFA) model, only k of the n attributes of each example are revealed to the learner, although the set of visible attributes in each example is determined by the learner. While the k -RFA model is a natural ...
On the Symmetric Negabent Boolean Functions
INDOCRYPT '09: Proceedings of the 10th International Conference on Cryptology in India: Progress in Cryptology

We study the negabent Boolean functions which are symmetric. The Boolean function which has equal absolute spectral values under the nega-Hadamard transform is called a negabent function. For a bent function, the absolute spectral values are the same ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLT '96: Proceedings of the ninth annual conference on Computational learning theory

January 1996

344 pages

ISBN:0897918118

DOI:10.1145/238061

Chairmen:
Avrim Blum
Carnegie Mellon Univ., Pittsburgh, PA
,
Michael Kearns
AT&T Research

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

9COLT96

Sponsor:

SIGAI
SIGACT
Univ degli Studi de Milano

9COLT96: 9th Annual Conference on Computational Learning Theory

June 28 - July 1, 1996

Desenzano del Garda, Italy

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
224
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)3

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Servedio R(2006)Every Linear Threshold Function has a Low-Weight ApproximatorProceedings of the 21st Annual IEEE Conference on Computational Complexity10.1109/CCC.2006.18(18-32)Online publication date: 16-Jul-2006
https://dl.acm.org/doi/10.1109/CCC.2006.18
Kwek SBen-David SLong P(1999)An apprentice learning model (extended abstract)Proceedings of the twelfth annual conference on Computational learning theory10.1145/307400.307413(63-74)Online publication date: 6-Jul-1999
https://dl.acm.org/doi/10.1145/307400.307413
Birkendorf AKlasner NKuhlmann CSimon HBartlett PMansour Y(1998)Structural results about exact learning with unspecified attribute valuesProceedings of the eleventh annual conference on Computational learning theory10.1145/279943.279974(144-153)Online publication date: 24-Jul-1998
https://dl.acm.org/doi/10.1145/279943.279974
Goldman SKwek SScott SFreund YSchapire R(1997)Learning from examples with unspecified attribute values (extended abstract)Proceedings of the tenth annual conference on Computational learning theory10.1145/267460.267504(231-242)Online publication date: 1-Jul-1997
https://dl.acm.org/doi/10.1145/267460.267504

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Boolean functions with two distinct Walsh coefficients

On Restricted-Focus-of-Attention Learnability of Boolean Functions

On the Symmetric Negabent Boolean Functions