Abstract:
We present a general computation model inspired in the notion of information hiding in software engineering. This model has the form of a game which we call quiz game. It allows in a uniform way to prove exponential lower bounds for several complexity problems. © 2016 Elsevier Inc. All rights reserved.
Registro:
Documento: |
Artículo
|
Título: | Quiz games as a model for information hiding |
Autor: | Bank, B.; Heintz, J.; Matera, G.; Montaña, J.L.; Pardo, L.M.; Rojas Paredes, A. |
Filiación: | Humboldt-Universität zu Berlin, Institut für Mathematik, Berlin, 10099, Germany Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Univ., Pab. I, Buenos Aires, 1428, Argentina National Council of Science and Technology (CONICET), Argentina Instituto Del Desarrollo Humano, Universidad Nacional General Sarmiento, J. M. Gutiérrez 1150 (B1613GSX) Los Polvorines, Provincia de Buenos Aires, Argentina Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, Santander, 39071, Spain
|
Palabras clave: | Elimination problem; Geometrically robust constructible map; Interpolation problem; Lower complexity bound; Neural network; Quiz game; Neural networks; Software engineering; Computation model; Elimination problem; Information hiding; Interpolation problems; Lower bounds; Lower complexity; Quiz game; Complex networks |
Año: | 2016
|
Volumen: | 34
|
Página de inicio: | 1
|
Página de fin: | 29
|
DOI: |
http://dx.doi.org/10.1016/j.jco.2015.11.005 |
Título revista: | Journal of Complexity
|
Título revista abreviado: | J. Complexity
|
ISSN: | 0885064X
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v34_n_p1_Bank |
Referencias:
- Alder, A., (1984) Grenzrang und Grenzkomplexität Aus Algebraischer und Topologischer Sicht, , (Ph.D. thesis) Universität Zürich
- Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic Complexity Theory, 315. , Grundlehren Math. Wiss. Springer Berlin
- Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial equation solving (2003) Found. Comput. Math., 3 (4), pp. 347-420
- Eisenbud, D., (1995) Commutative Algebra with A View Toward Algebraic Geometry, 150. , Grad. Texts in Math. Springer New York
- Fried, M., Jarden, M., (2005) Field Arithmetic, , second ed. Springer Berlin
- Giménez, N., Heintz, J., Matera, G., Solernó, P., Lower complexity bounds for interpolation algorithms (2011) J. Complexity, 27 (2), pp. 151-187
- Giusti, M., Heintz, J., Kronecker's smart, little black-boxes (2001) Proceedings of Foundations of Computational Mathematics, 284, pp. 69-104. , A. Iserles, R. Devore, E. Süli, FoCM'99, Oxford 1999 (Cambridge) London Math. Soc. Lecture Note Ser. Cambridge Univ. Press
- Griesser, B., Lower bounds for the approximative complexity (1986) Theoret. Comput. Sci., 46, pp. 329-338
- Hagan, M., Demuth, H., Beale, M., (1996) Neural Network Design, , PWS Publishing Company Boston, MA
- Haykin, S., Krogh, A., Palmer, R., (1999) Neural Networks, A Comprehensive Foundation, , second ed. Prentice Hall Upper Saddle River, NJ
- Heintz, J., Kuijpers, B., Rojas Paredes, A., On the intrinsic complexity of elimination problems in effective algebraic geometry (2013) Recent Advances in Real Complexity and Computation (Providence, RI), 604, pp. 129-150. , J.L. Montaña, L.M. Pardo, Contemp. Math. Amer. Math. Soc
- Heintz, J., Kuijpers, B., Rojas Paredes, A., Software engineering and complexity in effective algebraic geometry (2013) J. Complexity, 29 (1), pp. 92-138
- Hertz, J., Krogh, A., Palmer, R., (1991) Introduction to the Theory of Neural Computation, , Addison-Wesley Reading, Massachusetts
- Iversen, B., (1973) Generic Local Structure of the Morphisms in Commutative Algebra, 310. , Lecture Notes in Math. Springer New York
- Kunz, E., (1985) Introduction to Commutative Algebra and Algebraic Geometry, , Birkhäuser Boston
- Lickteig, T.M., (1990) On Semialgebraic Decision Complexity, Technical Report TR-90-052, , Int. Comput. Sci. Inst Berkeley
- Meyer, B., (1997) Object-oriented Software Construction, , second ed. Prentice-Hall, Inc. Upper Saddle River, NJ
- Mumford, D., (1988) The Red Book of Varieties and Schemes, 1358. , first ed. Lecture Notes in Math. Springer New York
- Shafarevich, I.R., (1994) Basic Algebraic Geometry: Varieties in Projective Space, , Springer Berlin Heidelberg New York
Citas:
---------- APA ----------
Bank, B., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M. & Rojas Paredes, A.
(2016)
. Quiz games as a model for information hiding. Journal of Complexity, 34, 1-29.
http://dx.doi.org/10.1016/j.jco.2015.11.005---------- CHICAGO ----------
Bank, B., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M., Rojas Paredes, A.
"Quiz games as a model for information hiding"
. Journal of Complexity 34
(2016) : 1-29.
http://dx.doi.org/10.1016/j.jco.2015.11.005---------- MLA ----------
Bank, B., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M., Rojas Paredes, A.
"Quiz games as a model for information hiding"
. Journal of Complexity, vol. 34, 2016, pp. 1-29.
http://dx.doi.org/10.1016/j.jco.2015.11.005---------- VANCOUVER ----------
Bank, B., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M., Rojas Paredes, A. Quiz games as a model for information hiding. J. Complexity. 2016;34:1-29.
http://dx.doi.org/10.1016/j.jco.2015.11.005