APPLICATIONS OF RAMSEY THEORY TO COMPUTER SCIENCE

This is a collection of papers that APPLY Ramsey Theory TO Theoretical Computer Science. I define `Ramsey Theory' to be any theorem that (roughly) says that if some structure is big enough, order emerges.

I divide the papers into the categories Surveys, Logic (Decidability, finite model theory), Concrete Complexity Theory (circuits, decision trees, comm. complexity, branching programs, hashing), Complexity Classes (the usual, but also property testing) Parallelism, and Computational Geometry.

Survey's

1. Some Nonstandard Ramsey Like Applications by Nesetril Theoretical Computer Science, Vol 34, 1984.
2. Applications of Ramsey Theory by Roberts, Discrete Applied Mathematics, Vol 9, 1984.
3. Boolean Complexity and Ramsey Theorems by Pudlak, Mathematics of Ramsey Theory, Springer-Verlag, 1990, ed by Nesetril, Rodl, 1990.
4. Ramsey Theory Applications by Vera Rosta. Manuscript. 2002. rosta.PS

Applications to Logic

1. On a problem in Formal Language by Ramsey. Proceedings of the London Math Society (series 2). Volume 30, pages 264-286, 1930.
2. On a decision method in restricted second order arithmetics by Buchi. In Proc. Int. Cong. of Logic, Methodogy, and Phil. of Sci, 1960. Ed by E. Nagel.
3. Bounds for Hodes-Specker Theorem by Pudlak. In Logic and Machines, LNCS Vol 171, 1984.
4. A Proof of Beigel's Cardinality Conjecture by Kummer. Journal of Symbolic Logic, Vol 57, 1992. card.PDF, card.PS
5. Generalized Quantifiers and Pebble Games on Finite Structures by Kolaitis and Vaananen, Annals of Pure and Applied Logic, Vol. 74, 1995. pebbles.PDF, pebbles.PS.
6. XML with data values: typechecking revisited by Alon, Milo, Neven, Suciu, Vianu, Proc. of the 20th Symposisum on Principles of Databases Systems (PODS 2001). XML1.PDF, XML1.PS.
7. An Existential Fragment of Second Order Logic by Rosen. Archives for Mathematical Logic, 1998. FRAG2.PDF, FRAG2.PS.
8. Typechecking XML Views of Relational Databases ACM Transactions on Computational Logic Vol 4, No 3, 315-354, 2003. by Alon, Milo, Neven, Suciu, Vianu, Earlier version in LICS01 XML2.PDF, XML2.PS.
9. The Complexity of Temporal Constraint Satisfaction Problems by Manuel Bodirsky Temp-Const-SAT

Applications to Concrete Complexity

1. Should Tables be Sorted by Yao, Journal of the ACM, Vol 28, 1981. tables.PDF, tables.PS
2. Two Lower Bounds for Branching Programs by Ajtai, Babai, Hajnal, Komlos, Pudlak, Proceedings of the 18th ACM STOC, 1986.
3. Multi-Party Protocols by Chandra, Furst, Lipton, Proceedings of the 15th ACM Symposium on Theory of Computing. 1983. (STOC 1983) Multi-Party Protocols multi-party-protocols.PDF
4. Applications of Ramsey's Theorem to Decision Tree Complexity by Moran, Snir, and Manber. Journal of the ACM, Vol 32, 1985. dt.PDF, dt.PS
5. Decision trees and downward closure by Imagliazzo and Naor. Proceedings of the 3rd Annual Conference on Structure in Complexity Theory. Pages 29-38. 1988.
6. Meanders and their applications in Lower Bound arguments by Alon, Maass. Journal of Computer and System Sciences, Vol 37, 1988. lb.INFO.PS
7. Lower Bounds to the Complexity of Symmetric Boolean Functions By Babai, Pudlak, Rodl, Szemeredi. Theoretical Computer Science Vol 74, No. 3, 313-323. 1990.
8. Subquadratic Simulations of Balanced Formulae by Branching Programs by Cai and Lipton. SICOMP Vol 23 (3), 1994. sub.PDF, sub.PS Excerpt in sublower.PDF, sublower.PS
9. Repeated Communication and Ramsey Graphs by Alon and Orlitsky IEEE Transactions on Information Theory, Vol 41, 1995. rep.PDF, rep.PS
10. Lower Bounds for Approx. by Low Degree Polynomials over Zm by Alon and Beigel. 16th CCC, 2001. approx-PS, approx-PDF
11. An Application of Hindman's Theorem to a Problem in Communication Complexity by Pudlak. Combinatorics, Probability, and Computing. 2003 Vol 12, pages 661-670. hind.PS My writeup of part of it PUDLAK
12. An Application of the Hales-Jewett Theorem to Multiparty Communication Complexity by Tesson. Manuscript, though its from his PhD thesis. HJPART.PS
13. A limit to the power of multiple nucleation in self-assembly by Aaron Sterling. Self-Assembly.pdf 22nd International Symposium on Distributed Computing, 2008.

Applications to Complexity Classes

1. Some Ramsey Theory in Boolean Algebra for Complexity Classes by McColm Mathematical Logic Quarterly, Vol 38, 1992. cc.PS cc.PDF
2. On Proving that a Graph Has No Large Clique: A Connection with Ramsey Theory by Lipton, IPL, Vol 58, 1996. lipton.PS, lipton.PDF
3. Sperner's Lemma nad Robust Machines by Crecenzi and Silvestri. Computational Complexity Vol 7, 1998. Earlier version in STRUCTURES93. robust.PS, robust.PDF
4. Time Bounded Frequency Computations by Hinrichs and Wechsung. Information and Computation Vol. 139, 1997.
5. Param. Complexity of Finding Subgraphs with Hereditary Properties by Khot and Raman. 6th COCOON, 2000. LNCS Vol 1858, param.PS, param.PDF
6. Eff. testing of large graphs by Alon, Fischer, Krivelevich, Szegedy. Combinatorica 20 (2000), 451-476. (Earlier FOCS99) eff-PS, eff-PDF
7. Testing of Matrix Properties by Fischer, Newman. Proceedings of The 33rd STOC (2001), 286-295. testmatrix-PS, testmartix-PDF
8. On the Strength of Comparisons in Property Testing by Fischer. ECCC TR01-008, 2001. property-PS, property-PDF
9. Languages Defined with Modular Counting Quantifiers by Straubing. Information and Computation, Vol 166, 2001. modquant-PS, modquant-PDF
10. Simple Analysis of Graph Tests for Linearity and PCP by Hastad and Wigderson Complexity conference, 2001 (also in ECCC). simple-PS,

Applications to Parallelism

1. On Parallel Searching by Snir. SIAM Journal on Computing, Vol 14, 1985.
2. One, Two, Three, ... infinity: Lower Bounds for Parallel Computation by Fich, Der Heide, Wigderson. STOC 1985, 123.PS, 123.PDF
3. Lower Bounds for Parallel Random-Access Machines by Fich, Der Heide, Radge, Wigderson. Advances in Computing Research, Vol. 4, 1986.
4. The Complexity of Parallel Sorting by Der Heide ad Wigderson. SICOMP Vol 16 (1), 1987.
5. The Parallel Complexity of Element Distinction by Ragde, Steiger, Szemeredi, and Wigderson. SIAM J of Disc. Math Vol 1, 1988.
6. Optimal Separations Between Concurrent-Write Parallel Machines by Boppana. 21st STOC, 1989. seppara.PS, seppara.PDF
7. What can be Computed Locally? by Naor and Stockmeyer. SICOMP Vol. 24, 1995. locally.PS, locally.PDF
8. Transforming Comparison Model Lower Bounds to the PRAM by Breslauer, Czumaj, Dubhashi, Meyer auf de Heide. IPL Vol. 62, 1997. tran.PS, tran.PDF

Applications to Algorithms and Misc.

1. Algorithms Associated with Ramsey's Theorem by Whitehead, Randall Rustin, Combinatorial Algorithms, Algorithmics Press, 1973, 1973.
2. Matrix Multiplication via Arithmetic Progressions by Coppersmith and Winograd, Journal of Symbolic Computation Vol 9, 1990. Earlier version in STOC 1987. I only have the STOC version electronically. Matrixmult.PDF
3. Ramsey Numbers and an Approx. Algorithm for the Vertex Cover Problem by Monien and Speckenmeyer. Acta Informatica, Vol 22, 1985.
4. Approx. Maximum Indepedent Sets by Excluding Subgraphs by Boppana and Halldorsson. BIT Vol 32, 1992. indset.PS, indset.PDF
5. A Ramsey-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems by Bartal, Bollobas, Mendel. Journal of Computing and Systems Science, Vol 72, No 5, Pages 890-922. (Also in FOCS01) metric.PDF
6. On the Diagonal Queens Domination Problem by Cockayne and Hedetniemi. Journal of Combinatorial Theory (Series A), Vol 42, 1986, 137-139. queens-on-a-diag.pdf

Applications to Computational Geometry

1. An Algorithm for Finding Many Disjoint Monochromatic Edges in a Complete 2-Colored Geometric Graph by Karolyi, Pach, Tardos, Toth. Intuitive Geometry, Bolyai Society Mathematical Studies, 1996.
2. Ramsey-type Results for Geometric Graphs I by Karolyi, Pach, Toth. Discrete and Computational Geometry, Vol. 18, 1997.
3. Ramsey-type Results for Geometric Graphs II by Karolyi, Pach, Toth. Discrete and Computational Geometry, Vol. 20, 1998.
4. A Visibility Representation for Graphs in Three Dimensions by Bose, Everett, Fekete, Houle, Lubiw,Meijer, Romanik, Rote, Shermer, Whitesides. Journal of Graph Algorithms and Applications Vol 2, 1998. visibility-PS, visibility-PDF
5. Universal 3-Dimensional Visibility Representation for Graphs by Alt, Godau, Whitesides. Computational Geometry, Vol 21, 2000. univ3-PS, univ3-PDF.
6. Separating Geometric Thickness from Book Thickness by David Eppstein. link-to-arXiv
7. Separating Thickness from Geometric Thickness by David Eppstein. link-to-arXiv