On Learning Random DNF Formulas Under the Uniform Distribution
by Jeffrey C. Jackson and Rocco A. Servedio
Theory of Computing, Volume 2(8), pp. 147-172, 2006
Bibliography with links to cited articles
| [1] |
H. Aizenstein and L. Pitt: On the learnability of disjunctive normal form
formulas.
Machine Learning, 19:183-208, 1995.
[ML:n226835168336578]. |
| [2] |
Noga Alon and Joel H. Spencer: The Probabilistic Method.
John Wiley and Sons, 2000. |
| [3] |
D. Angluin: Queries and concept learning.
Machine Learning, 2(4):319-342, 1988.
[ML:u228266621966h58]. |
| [4] |
Dana Angluin and Michael Kharitonov: When won't membership queries help?
Journal of Computer and System Sciences, 50(2):336-355, 1995.
[JCSS:10.1006/jcss.1995.1026]. |
| [5] |
A. Blum: Learning a function of r relevant variables (open problem).
In Proc. 16th Ann. Conf. on Computational Learning Theory
(COLT'03), volume 2777 of Lecture Notes in Computer Science, pp.
731-733. Springer, 2003.
[COLT:fxdg79cvndr6n05r]. |
| [6] |
A. Blum: Machine learning: a tour through some favorite results,
directions, and open problems.
FOCS 2003 tutorial slides, available at
http://www-2.cs.cmu.edu/ avrim/Talks/FOCS03/tutorial.ppt, 2003. |
| [7] |
A. Blum, C. Burch, and J. Langford: On learning monotone boolean
functions.
In Proc. 39th FOCS, pp. 408-415. IEEE Computer Society Press,
1998.
[FOCS:10.1109/SFCS.1998.743491]. |
| [8] |
A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and S. Rudich:
Weakly learning DNF and characterizing statistical query learning using
Fourier analysis.
In Proc. 26th STOC, pp. 253-262. ACM Press, 1994.
[STOC:195058.195147]. |
| [9] |
B. Bollobás: Combinatorics: Set Systems, Hypergraphs, Families
of Vectors and Combinatorial Probability.
Cambridge University Press, 1986. |
| [10] |
M. Golea, M. Marchand, and T. Hancock: On learning μ-perceptron
networks on the uniform distribution.
Neural Networks, 9(1):67-82, 1994.
[NeuralNet:10.1016/0893-6080(95)00009-7]. |
| [11] |
T. Hancock: Learning kμ decision trees on the uniform distribution.
In Proc. 6th Ann. Conf. on Computational Learning Theory
(COLT'93), pp. 352-360. ACM Press, 1993.
[ACM:168304.168374]. |
| [12] |
J. Jackson: An efficient membership-query algorithm for learning DNF
with respect to the uniform distribution.
Journal of Computer and System Sciences, 55(3):414-440, 1997.
[JCSS:10.1006/jcss.1997.1533]. |
| [13] |
J. Jackson, A. Klivans, and R. Servedio: Learnability beyond AC0.
In Proc. 34th STOC, pp. 776-784. ACM Press, 2002.
[STOC:509907.510018]. |
| [14] |
J. Jackson and R. Servedio: Learning random log-depth decision trees
under the uniform distribution.
In Proc. 16th Ann. Conf. on Computational Learning Theory
(COLT'03) and 7th Kernel Workshop, volume 2777 of Lecture Notes in
Computer Science, pp. 610-624. Springer, 2003.
[ doi:10.1007/b12006,
COLT:31wxjv7lb9l5 ]. |
| [15] |
J. Jackson and R. Servedio: On learning random DNF formulas under the
uniform distribution.
In Proc. 9th Internat. Workshop on Randomization and Computation
(RANDOM'05), volume 3624 of Lecture Notes in Computer Science, pp.
342-353. Springer, 2005.
[RANDOM:2y5933y326xhbgar]. |
| [16] |
J. Jackson and C. Tamon: Fourier Analysis in Machine Learning.
ICML/COLT 1997 tutorial slides, available at
http://learningtheory.org/resources.html, 1997. |
| [17] |
M. Kearns: Efficient noise-tolerant learning from statistical queries.
Journal of the ACM, 45(6):983-1006, 1998.
[JACM:293347.293351]. |
| [18] |
M. Kearns, M. Li, L. Pitt, and L. Valiant: On the learnability of
Boolean formulae.
In Proc. 19th STOC, pp. 285-295. ACM Press, 1987.
[STOC:28395.28426]. |
| [19] |
M. Kearns, M. Li, L. Pitt, and L. Valiant: Recent results on Boolean
concept learning.
In Proc. 4th Internat. Workshop on Machine Learning, pp.
337-352. Morgan Kaufmann, 1987. [ .ps | .pdf ] |
| [20] |
M. Kearns and U. Vazirani: An introduction to computational learning
theory.
MIT Press, Cambridge, MA, 1994. |
| [21] |
A. Klivans, R. O'Donnell, and R. Servedio: Learning intersections and
thresholds of halfspaces.
In Proc. 43rd FOCS, pp. 177-186. IEEE Computer Society Press,
2002.
[FOCS:10.1109/SFCS.2002.1181894]. |
| [22] |
L. Kucera, A. Marchetti-Spaccamela, and M. Protassi: On learning
monotone DNF formulae under uniform distributions.
Information and Computation, 110:84-95, 1994.
[IandC:10.1006/inco.1994.1024]. |
| [23] |
Y. Mansour: Learning Boolean functions via the Fourier
transform, pp. 391-424.
Kluwer Academic Publishers, 1994. [ .ps.gz ] |
| [24] |
C. McDiarmid: On the method of bounded differences.
In Surveys in Combinatorics 1989, pp. 148-188. London
Mathematical Society Lecture Notes, 1989. |
| [25] |
R. Servedio: On learning monotone DNF under product distributions.
In Proc. 14th Ann. Conf. on Computational Learning Theory
(COLT'01), volume 2111 of Lecture Notes in Computer Science, pp.
558-573. Springer, 2001.
[COLT:3j42gw4570jb08yt]. |
| [26] |
L. Valiant: A theory of the learnable.
Communications of the ACM, 27(11):1134-1142, 1984.
[CACM:1968.1972]. |
| [27] |
K. Verbeurgt: Learning DNF under the uniform distribution in
quasi-polynomial time.
In Proc. 3rd Ann. Workshop on Computational Learning Theory
(COLT '90), pp. 314-326. Morgan Kaufmann, 1990.
[ACM:92571.92657]. |
This file has been generated by bibtex2html 1.81.