LIPIcs.STACS.2015.249.pdf
- Filesize: 0.59 MB
- 13 pages
Document
Combinatorial Expressions and Lower Bounds
Authors
-
Part of:
Volume:
32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-02-26
Cite As Get BibTex
Thomas Colcombet and Amaldev Manuel. Combinatorial Expressions and Lower Bounds. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 249-261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.STACS.2015.249
Abstract
A new paradigm, called combinatorial expressions, for computing functions expressing properties over infinite domains is introduced. The main result is a generic technique, for showing indefinability of certain functions by the expressions, which uses a result, namely Hales-Jewett theorem, from Ramsey theory. An application of the technique for proving inexpressibility results for logics on metafinite structures is given. Some extensions and normal forms are also presented.
Subject Classification
Keywords
- expressions
- lower bound
- indefinability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and Real Computation. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1998.
-
Erich Grädel and Yuri Gurevich. Metafinite model theory. Information and Computation, 140(1):26 - 81, 1998.
-
R.L. Graham, B.L. Rothschild, and J.H. Spencer. Ramsey Theory. A Wiley-Interscience publication. Wiley, 1990.
-
T. Jech. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer Monographs in Mathematics. Springer, 2003.
-
Pascal Koiran. A weak version of the blum, shub, and smale model. Journal of Computer and System Sciences, 54(1):177 - 189, 1997.
-
Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser Verlag, Basel, Switzerland, Switzerland, 1994.
-
Pascal Tesson. Computational Complexity Questions Related to Finite Monoids and Semigroups. PhD thesis, School of Computer Science, McGill University, Montreal, 2003.
-
Pascal Tesson. An application of the hales-jewett theorem to multiparty communication complexity. Extract from the PhD Thesis, 2004.
-
L. G. Valiant. Completeness classes in algebra. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 249-261, New York, NY, USA, 1979. ACM.