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.

*Some Nonstandard Ramsey Like Applications*by Nesetril Theoretical Computer Science, Vol 34, 1984. NONSTANDARDAPP.PDF*Applications of Ramsey Theory*by Roberts, Discrete Applied Mathematics, Vol 9, 1984. Robertsapp.PDF*Boolean Complexity and Ramsey Theorems*by Pudlak, Mathematics of Ramsey Theory, Springer-Verlag, 1990, ed by Nesetril, Rodl, 1990.*Ramsey Theory Applications*by Vera Rosta. Got to: http://www.combinatorics.org/nd look for Dyanmic Surveys.

*On a problem in Formal Logic*by Ramsey. Proceedings of the London Math Society (series 2). Volume 30, pages 264-286, 1930. RAMSEYORIG.PDF My writeup of this: RAMSEYORIGMYWRITEUP.PDF*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.*Bounds for Hodes-Specker Theorem*by Pudlak. In*Logic and Machines, LNCS Vol 171*, 1984. HODESSPECKER.PDF,*A Proof of Beigel's Cardinality Conjecture*by Kummer. Journal of Symbolic Logic, Vol 57, 1992. card.PDF, card.PS*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.*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.*An Existential Fragment of Second Order Logic*by Rosen. Archives for Mathematical Logic, 1998. FRAG2.PDF, FRAG2.PS.*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.*The Complexity of Temporal Constraint Satisfaction Problems*by Manuel Bodirsky Temp-Const-SAT gq.INFO.PS*Ramsey Theory Is Needed for Solving Definability Probs of Gen Quantifiers*by Luosto. European Sum. School in Logic, Language, and Info, ESSLLI Wkshp, LNCS Vol 9, 1997. ramseyneeded.pdf*Proving Program Termination*by Cook, Podelski, Rybachenko. CACM May 2011. provingtermination.pdf- The dynamic description complexity of k-clique by Thomas Zeume. This is an application to descriptive complexity theory. zeume.pdf

*Should Tables be Sorted*by Yao, Journal of the ACM, Vol 28, 1981. tables.PDF, tables.PS*Two Lower Bounds for Branching Programs*by Ajtai, Babai, Hajnal, Komlos, Pudlak, Proceedings of the 18th ACM STOC, 1986. TWOLOWERBOUNDS.PDF*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*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*Decision trees and downward closure*by Imagliazzo and Naor. Proceedings of the 3rd Annual Conference on Structure in Complexity Theory. Pages 29-38. 1988. DECTREESDOWNCLOSURE.PDF,*Meanders and their applications in Lower Bound arguments*by Alon, Maass. Journal of Computer and System Sciences, Vol 37, 1988. MEANDERDS.PDF*Lower Bounds to the Complexity of Symmetric Boolean Functions*By Babai, Pudlak, Rodl, Szemeredi. Theoretical Computer Science Vol 74, No. 3, 313-323. 1990. SYMMBOOLFUNS.PDF*Subquadratic Simulations of Balanced Formulae by Branching Programs*by Cai and Lipton. SICOMP Vol 23 (3), 1994. CaiLipton.PDF*Repeated Communication and Ramsey Graphs*by Alon and Orlitsky IEEE Transactions on Information Theory, Vol 41, 1995. rep.PDF, rep.PS*Superlinear lower bounds for bounded-width branching programs*by Barrington and Straubing. JCSS Vol 50, 1995. superlinearbp.PDF,*Lower Bounds for Approx. by Low Degree Polynomials over Zm*by Alon and Beigel. 16th CCC, 2001. approx-PS, approx-PDF*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*An Application of the Hales-Jewett Theorem to Multiparty Communication Complexity*by Tesson. Manuscript, though its from his PhD thesis. HJPART.PS*A limit to the power of multiple nucleation in self-assembly*by Aaron Sterling. Self-Assembly.pdf 22nd International Symposium on Distributed Computing, 2008.*Satisfiability Allows No Nontrivial Sparsification Unless the Polynomial-Time Hierarchy Collapses*by Holger Dell and Dieter van Melkebeek. ECCC Report 38, 2010. STOC 2010. satsparse.pdf

*The Node-Deletion Problem for Hereditary Properties is NP-Complete*by J.Lewis and M.Yannakakis. JCSS Vol 20, 1980 hered.PS hered.PDF*Some Ramsey Theory in Boolean Algebra for Complexity Classes*by McColm Mathematical Logic Quarterly, Vol 38, 1992. cc.PS cc.PDF*On Proving that a Graph Has No Large Clique: A Connection with Ramsey Theory*by Lipton, IPL, Vol 58, 1996. lipton.PS, lipton.PDF*Sperner's Lemma nad Robust Machines*by Crecenzi and Silvestri. Computational Complexity Vol 7, 1998. Earlier version in STRUCTURES93. robust.PS, robust.PDF*Time Bounded Frequency Computations*by Hinrichs and Wechsung. Information and Computation Vol. 139, 1997. TIMEFREQ.PDF*Param. Complexity of Finding Subgraphs with Hereditary Properties*by Khot and Raman. 6th COCOON, 2000. LNCS Vol 1858, param.PS, param.PDF*Eff. testing of large graphs*by Alon, Fischer, Krivelevich, Szegedy. Combinatorica 20 (2000), 451-476. (Earlier FOCS99) eff-PS, eff-PDF*Testing of Matrix Properties*by Fischer, Newman. Proceedings of The 33rd STOC (2001), 286-295. testmatrix-PS, testmartix-PDF*On the Strength of Comparisons in Property Testing*by Fischer. ECCC TR01-008, 2001. property-PS, property-PDF*Languages Defined with Modular Counting Quantifiers*by Straubing. Information and Computation, Vol 166, 2001. modquant-PS, modquant-PDF*Simple Analysis of Graph Tests for Linearity and PCP*by Hastad and Wigderson Complexity conference, 2001 (also in ECCC). simple-PS,*Satisfiability Allows No Nontrivial Sparsification Unless the Polynomial-Time Hierarchy Collapses*by Dell and van Melkebeek. DELL-PDF,

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

*Algorithms Associated with Ramsey's Theorem*by Whitehead, Randall Rustin, Combinatorial Algorithms, Algorithmics Press, 1973, 1973.*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*Ramsey Numbers and an Approx. Algorithm for the Vertex Cover Problem*by Monien and Speckenmeyer. Acta Informatica, Vol 22, 1985.*Approx. Maximum Indepedent Sets by Excluding Subgraphs*by Boppana and Halldorsson. BIT Vol 32, 1992. indset.PS, indset.PDF*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*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*Finding, Minimizing, and Counting Weighted Subgraphs*by Virginia Vassilevska and Ryan Williams. findmin.pdf STOC 2009.

*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. DISJMONO.PS,*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. VISREP.PDF,*Universal 3-Dimensional Visibility Representation for Graphs*by Alt, Godau, Whitesides. Computational Geometry, Vol 21, 2000. univ3-PS, univ3-PDF.MiscSCHURCOMP.PDF, Computing Schur Numbers.