×

zbMATH — the first resource for mathematics

Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems. (English) Zbl 1364.03081
Proceedings of the 4th conference on innovations in theoretical computer science, ITCS’13, Berkeley, CA, USA, January 9–12, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1859-4). 455-472 (2013).

MSC:
03F20 Complexity of proofs
03B35 Mechanization of proofs and logical operations
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
91A80 Applications of game theory
Software:
PolyBoRi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] D. Angluin and M. Krik¸is. Learning from di.erent teachers. Mach. Learn., 51(2):137 163, 2003. · Zbl 1027.68106
[2] M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying Boolean functinos by labelled examples. Discrete Applied Mathematics, 61(1):1 25, 1995. · Zbl 0826.06008
[3] F. J. Balbach. Measuring teachability using variants of the teaching dimension. Theoret. Comput. Sci., 397(1 3):94 113, 2008. · Zbl 1145.68020
[4] F. J. Balbach and T. Zeugmann. Teaching learners with restricted mind changes. In Proc. 16th ALT, volume 3734, pages 474 489. Springer, 2005. · Zbl 1168.68390
[5] F. J. Balbach and T. Zeugmann. Teaching randomized learners. In Proc. 19th COLT, volume 4005, pages 229 243. Springer, 2008. · Zbl 1143.68409
[6] F. J. Balbach and T. Zeugmann. Recent developments in algorithmic teaching. In Proc. 3rd Int l Conf. on Language and Automata Theory and Applications, pages 1 18, 2009. · Zbl 1234.68165
[7] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam s razor. Inf. Process. Lett., 24:377 380, 1987. · Zbl 0653.68084
[8] S. Floyd. On space-bounded learning and the Vapnik-Chervonenkis dimension.PhD thesis, University of California, Berkeley, Berkeley, CA, 1989. · Zbl 0747.68041
[9] S. Floyd and M. Warmuth. Sample compression, learnability, and the Vapnik-Chervonenkis dimension. Mach. Learn., 21:269 304, 1995.
[10] R. Freivalds, E. B. Kinber, and R. Wiehagen. On the power of inductive inference from good examples. Theoret. Comput. Sci., 110(1):131 144, 1993. · Zbl 0821.68110
[11] H. Freudenthal. LINCOS: Design of a language for cosmic intercourse. North-Holland, Amsterdam, 1960. · Zbl 0095.00506
[12] S. A. Goldman and M. J. Kearns. On the complexity of teaching. J. Comput. Syst. Sci., 50(1):20 31, 1995. · Zbl 0939.68770
[13] S. A. Goldman and H. D. Mathias. Teaching a smarter learner. J. Comput. Syst. Sci., 52(2):255 267, 1996. · Zbl 1152.68451
[14] O. Goldreich, B. Juba, and M. Sudan. A theory of goal-oriented communication. J. ACM, 59(2):8:1 8:65, 2012. · Zbl 1281.94004
[15] R. Impagliazzo, V. Kabanets, and A. Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672 694, 2002. · Zbl 1059.68047
[16] R. Impagliazzo and A. Wigderson. P=BPP unless E has subexponential circuits: Derandomizing the XOR lemma. In Proc. 29th STOC, pages 220 229, 1997. · Zbl 0962.68058
[17] J. Jackson and A. Tomkins. A computational model of teaching. In Proc. 5th COLT, pages 319 326, 1992.
[18] V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1 46, 2004. · Zbl 1089.68042
[19] N. Littlestone. From on-line to batch learning. In Proc. COLT 89, pages 269 284, 1989. · Zbl 0752.68066
[20] N. Littlestone and M. K. Warmuth. Relating data compression and learnability. Unpublished manuscript, 1986.
[21] H. D. Mathias. A model of interactive teaching. J. Comput. Syst. Sci., 54(3):487 501, 1997. · Zbl 0882.68123
[22] N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449 461, 1992. · Zbl 0759.68024
[23] R. L. Rivest. Learning decision lists. Mach. Learn., 2(3):229 246, 1987.
[24] D. Schuurmans and R. Greiner. Sequential PAC learning. In Proc. 8th COLT, pages 377 384, 1995.
[25] R. A. Servedio. On the limits of e.cient teachability. Inf. Process. Lett., 79(6):267 272, 2001. · Zbl 1032.68662
[26] A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Comput., 8(4):337 347, 1991. · Zbl 0712.68084
[27] L. G. Valiant. A theory of the learnable. Communications of the ACM, 18(11):1134 1142, 1984. · Zbl 0587.68077
[28] S. Zilles, S. Lange, R. Holte, and M. Zinkevich. Models of cooperative teaching and learning. JMLR, 12:349 384, 2012. APPENDIX A. TAIL BOUND DERIVATION Here we prove: Reminder of Theorem 3.2 Let X1,...,Xt be independent Bernoulli random variables such that E · Zbl 1280.68224
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.