next up previous
Next: About this document ...

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. NONSTANDARDAPP.PDF
  2. Applications of Ramsey Theory by Roberts, Discrete Applied Mathematics, Vol 9, 1984. Robertsapp.PDF
  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. Got to: http://www.combinatorics.org/nd look for Dyanmic Surveys.

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. RAMSEYORIG.PDF
  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. HODESSPECKER.PDF,
  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 gq.INFO.PS
  10. 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
  11. Proving Program Termination by Cook, Podelski, Rybachenko. CACM May 2011. provingtermination.pdf

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. TWOLOWERBOUNDS.PDF
  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. DECTREESDOWNCLOSURE.PDF,
  6. Meanders and their applications in Lower Bound arguments by Alon, Maass. Journal of Computer and System Sciences, Vol 37, 1988. MEANDERDS.PDF
  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. SYMMBOOLFUNS.PDF
  8. Subquadratic Simulations of Balanced Formulae by Branching Programs by Cai and Lipton. SICOMP Vol 23 (3), 1994. CaiLipton.PDF
  9. Repeated Communication and Ramsey Graphs by Alon and Orlitsky IEEE Transactions on Information Theory, Vol 41, 1995. rep.PDF, rep.PS
  10. Superlinear lower bounds for bounded-width branching programs by Barrington and Straubing. JCSS Vol 50, 1995. superlinearbp.PDF,
  11. Lower Bounds for Approx. by Low Degree Polynomials over Zm by Alon and Beigel. 16th CCC, 2001. approx-PS, approx-PDF
  12. 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
  13. An Application of the Hales-Jewett Theorem to Multiparty Communication Complexity by Tesson. Manuscript, though its from his PhD thesis. HJPART.PS
  14. A limit to the power of multiple nucleation in self-assembly by Aaron Sterling. Self-Assembly.pdf 22nd International Symposium on Distributed Computing, 2008.
  15. 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

Applications to Complexity Classes

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

Applications to Parallelism

  1. On Parallel Searching by Snir. SIAM Journal on Computing, Vol 14, 1985. PARASEARCH.PDF
  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. PARASORT.PDF
  5. The Parallel Complexity of Element Distinction by Ragde, Steiger, Szemeredi, and Wigderson. SIAM J of Disc. Math Vol 1, 1988. paraed.PDF
  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
  9. schgraphs.pdf Schafer's theorem for graphs by Bodirsky and Pinsker. STOC 2011.

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
  7. Finding, Minimizing, and Counting Weighted Subgraphs by Virginia Vassilevska and Ryan Williams. findmin.pdf STOC 2009.

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


next up previous
Next: About this document ...
William Gasarch 2013-03-04