%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% v002/a008.bib  Jackson - Servedio  9/18/2006
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@article{AizensteinPitt:95,
 author={H. Aizenstein and L. Pitt},
 title={On the Learnability of Disjunctive Normal Form Formulas},
 journal={Machine Learning},
 year={1995},
 volume={19},
 pages={183--208},
eprint={ml:n226835168336578}
}

@Book{AlonSpencer,
  author={Noga Alon and Joel H. Spencer},
  title={The Probabilistic Method},
  publisher={John Wiley and Sons},
  year = {2000}
}

@article{Angluin:88,
 author={D. Angluin},
 title={Queries and concept learning},
 journal={Machine Learning},
 year={1988},
 volume={2},
 number=4,
 pages={319--342},
eprint="ml:u228266621966h58"
}

@ARTICLE{angkha95,
 author = {Dana Angluin and Michael Kharitonov},
 title = {When Won't Membership Queries Help?},
 journal = {Journal of Computer and System Sciences},
 year = {1995},
 volume = {50},
 pages = {336--355},
 number = {2},
 printoutnum = {132},
 eprint={jcss:10.1006/jcss.1995.1026}
}

@inproceedings{Blum:03problem,
 author={A. Blum},
 title={Learning a function of $r$ relevant variables (open problem)},
 booktitle={Proc. 16th Ann. Conf. on Computational Learning Theory (COLT'03)},
 series={Lecture Notes in Computer Science},
 volume={2777},
 publisher={Springer},
 year={2003},
 pages={731--733},
 eprint="colt:fxdg79cvndr6n05r"
}

@unpublished{Blum:03tutorial,
author={A. Blum},
 title={Machine learning:  a tour through some favorite results,
 directions, and open problems},
 note={FOCS 2003 tutorial slides, available at
http://www-2.cs.cmu.edu/~avrim/Talks/FOCS03/tutorial.ppt},
 year={2003}
}

@InProceedings{BBL:98,
author  =   {A. Blum and C. Burch and J. Langford},
title   =   {On Learning Monotone Boolean Functions},
 booktitle={Proc. 39th FOCS},
publisher = {IEEE Computer Society Press},
pages   =   {408--415},
year    = {1998},
eprint="focs:10.1109/SFCS.1998.743491"
}

@inproceedings{BFJ+:94,
 author={A. Blum and M. Furst and J. Jackson and M. Kearns and Y.
Mansour and S. Rudich},
 title={Weakly learning {DNF} and characterizing statistical query
learning using {F}ourier analysis},
 booktitle={Proc. 26th STOC},
 location={Montreal, Quebec, Canada},
 publisher={ACM Press},
 pages={253--262},
 year={1994},
 eprint="stoc:195058.195147"
}

@book{Bollobas:86,
 author={B. Bollob{\'a}s},
 title={Combinatorics:  Set Systems, Hypergraphs, Families of Vectors
and Combinatorial Probability},
 publisher={Cambridge University Press},
 year={1986}
}

@article{GHM:94,
 author={M. Golea and M. Marchand and T. Hancock},
 title={On Learning $\mu$-perceptron networks on the uniform distribution},
 journal={Neural Networks},
 year={1994},
 volume={9},
 number=1,
 pages={67--82},
 eprint="NeuralNet:10.1016/0893-6080(95)00009-7"
}

@inproceedings{Hancock:93,
 author={T. Hancock},
 title={{Learning $k\mu$ decision trees on the uniform distribution}},
 booktitle={Proc. 6th Ann. Conf. on Computational Learning Theory (COLT'93)},
 location={Santa Cruz, California},
 publisher={ACM Press},
 pages={352--360},
 year={1993},
 eprint="ACM:168304.168374"
}

@article{Jackson:97,
 author={J. Jackson},
 title={An efficient membership-query algorithm for learning {DNF}
with respect to the uniform distribution},
 journal={Journal of Computer and System Sciences},
 year={1997},
 volume={55},
 number=3,
 pages={414--440},
 eprint="jcss:10.1006/jcss.1997.1533"
}

@inproceedings{JKS:02,
 author={J. Jackson and A. Klivans and R. Servedio},
 title={Learnability beyond ${AC}^0$},
 booktitle={Proc. 34th STOC},
 location={Montreal, Quebec, Canada},
 publisher={ACM Press},
 pages={776--784},
 year={2002},
 eprint="stoc:509907.510018"
}

@inproceedings{JacksonServedio:03,
 author={J. Jackson and R. Servedio},
 title={Learning Random Log-Depth Decision Trees under the Uniform
Distribution},
 booktitle={Proc. 16th Ann. Conf. on Computational Learning Theory
(COLT'03) and 7th Kernel Workshop},
 location={Washington, DC},
 series={Lecture Notes in Computer Science},
 volume={2777},
 publisher={Springer},
 pages={610--624},
 year={2003},
 doi = {10.1007/b12006},
 eprint="colt:31wxjv7lb9l5"
}

@inproceedings{JacksonServedio:05random,
author={J. Jackson and R. Servedio},
title={On Learning Random {DNF} Formulas under the Uniform Distribution},
booktitle={Proc. 9th Internat. Workshop on Randomization and
Computation (RANDOM'05)},
series={Lecture Notes in Computer Science},
volume={3624},
publisher={Springer},
pages={342--353},
year={2005},
eprint="random:2y5933y326xhbgar"
}

@unpublished{JacksonTamon:97,
author={J. Jackson and C. Tamon},
 title={Fourier {A}nalysis in {M}achine {L}earning},
 note={ICML/COLT 1997 tutorial slides, available at
http://learningtheory.org/resources.html},
 year={1997}
}

@article{Kearns:98,
 author={M. Kearns},
 title={Efficient noise-tolerant learning from statistical queries},
 journal={Journal of the ACM},
 year={1998},
 volume={45},
 number={6},
 pages={983--1006},
 eprint="jacm:293347.293351"
}

@inproceedings{KLP+:87a,
 author={M. Kearns and M. Li and L. Pitt and L. Valiant},
 title={Recent results on {B}oolean concept learning},
 booktitle={Proc. 4th Internat. Workshop on Machine Learning},
 publisher={Morgan Kaufmann},
 pages={337--352},
 year={1987},
ps="http://www.cis.upenn.edu/~mkearns/papers/klpv-ml.ps",
pdf="http://www.cis.upenn.edu/~mkearns/papers/klpv-ml.pdf"
}

@inproceedings{KLP+:87b,
 author={M. Kearns and M. Li and L. Pitt and L. Valiant},
 title={On the learnability of {B}oolean formulae},
 booktitle={Proc. 19th STOC},
 publisher={ACM Press},
 pages={285--295},
 year={1987},
 eprint="stoc:28395.28426"
}

@book{KearnsVazirani:94,
 author={M. Kearns and U. Vazirani},
 title={An introduction to computational learning theory},
 publisher={MIT Press},
 year={1994},
 address={Cambridge, MA}
}

@inproceedings{KOS:02,
 author={A. Klivans and R. O'Donnell and R. Servedio},
 title={Learning intersections and thresholds of halfspaces},
 booktitle={Proc. 43rd FOCS},
 location={Vancouver, B. C.},
 publisher={IEEE Computer Society Press},
 pages={177--186},
 year={2002},
 eprint="focs:10.1109/SFCS.2002.1181894"
}

@article{KMP:94,
 author={L. Ku{\v c}era and A. Marchetti-Spaccamela and M. Protassi},
 title={On learning monotone {DNF} formulae under uniform distributions},
 journal={Information and Computation},
 year={1994},
 volume={110},
 pages={84--95},
 eprint="IandC:10.1006/inco.1994.1024"
}

@inbook{Mansour:94,
 author={Y. Mansour},
 title={Learning {B}oolean functions via the {F}ourier transform},
 booktitle={Theoretical Advances in Neural Computation and Learning},
 publisher={Kluwer Academic Publishers},
 pages={391--424},
 year={1994},
ps="http://www.math.tau.ac.il/~mansour/papers/fourier-survey.ps.gz"
}

@inproceedings{McDiarmid:89,
author={C. McDiarmid},
title={On the method of bounded differences},
booktitle={Surveys in Combinatorics 1989},
pages={148--188},
publisher={London Mathematical Society Lecture Notes},
year={1989}
}

@inproceedings{Servedio:01mdnf,
  author={R. Servedio},
  title="On learning monotone {DNF} under product distributions",
  booktitle={Proc. 14th Ann. Conf. on Computational Learning Theory (COLT'01)},
  location={Amsterdam},
  series="Lecture Notes in Computer Science",
  volume={2111},
  publisher={Springer},
  pages={558--573},
  year={2001},
  eprint="colt:3j42gw4570jb08yt"
 }

@article{Valiant:84,
 author={L. Valiant},
 title={A theory of the learnable},
 journal={Communications of the ACM},
 year={1984},
 volume={27},
 number={11},
 pages={1134--1142},
 eprint="cacm:1968.1972"
}

@inproceedings{Verbeurgt:90,
 author={K. Verbeurgt},
 title={Learning {DNF} under the uniform distribution in quasi-polynomial time},
 booktitle={Proc. 3rd Ann. Workshop on Computational Learning Theory
(COLT '90)},
 publisher={Morgan Kaufmann},
 pages={314--326},
 year={1990},
 eprint="ACM:92571.92657"
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%