J. Culberson

Publications Page

• F. Yang , J. Culberson , R. Holte, U. Zahavi and A. Felner (2008) "A General Theory of Additive State Space Abstractions", JAIR Volume 32, pages 631-662
• Y. Gao and J. Culberson, Consistency and Random Constraint Satisfaction Models, JAIR Volume 28, pages 517-557, 2007.
• N. Abbas, J. Culberson, L. Stewart. Recognizing Maximal Unfrozen Graphs with Respect to Independent Sets is  CO-NP complete. Discrete Mathematics & Theoretical Computer Science ,Vol 7, No. 1, pp 141-154, 2005.
• J. Culberson, Y. Gao, and C. Anton. Phase Transitions of Dominating Clique Problem and Their Implications to Satisfiability Search.  The 19th Internatinoal Joint Conference on Artificial Intelligence (IJCAI). 2005 , pp 78-83.
• Y. Gao and J. Culberson. Consistency and Random Constraint Satisfaction Models with a high Constraint Tightness.
   Tenth International Conference on Principles and Practice of Constraint Programming (CP-2004) , pp. 17-31, 2004.
   (Distinguished Paper Award)
• Y. Gao and J. Culberson. Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story.
  Discrete Applied Mathematics, Volume 153, Issues 1-3,   December 2005,  Pages 124-140.
• On the Complexity of Unfrozen Problems.
  Adam Beacham and Joseph Culberson.  Discrete Applied Mathematics, Volume 153, Issues 1-3,   December 2005,  Pages 124-140.
  Extended Abstract presented at WORKSHOP ON COMPUTATIONAL COMPLEXITY AND STATISTICAL PHYSICS, 2001.
  See also Adam Beacham's thesis.
• Y. Gao and J. Culberson. Space Complexity of Estimation of Distribution Algorithms.
  Evolutionary Computation ,  vol. 13, no. 1, 2005.
•  Y. Gao and J. Culberson. Probabilistic Methods in Landscape Analysis: phase transitions, interaction structures, and complexity measures
    Evolutionary Computation Theory Workshop , held at GECCO 04.
• The Resolution Complexity of Random Graph $k$-Colorability.   Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore, Electronic Colloquium on Computational Complexity  Report TR04-012,   2004.    Discrete Applied Mathematics, Volume 153, Issues 1-3,   December 2005,  Pages 124-140.
• On the Treewidth of NK Landscapes. Yong Gao and Joseph Culberson.
  Genetic and Evolutionary Computation Conference (GECCO 2003) , LNCS 2723, pp. 948-954, 2003.
  A local copy here. 
• Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story Yong Gao and Joseph Culberson LICS'03 Workshop on Typical Case Complexity and Phase Transitions    A local copy here.
• Generating Instances of Intermediate Hardness for Satisfiability .
  Calin Anton and Joseph Culberson. Paper here presented at  SAT 2003 Poster Presentation (Calin)
•  An Analysis of Phase Transition in NK Landscapes
  Yong Gao and Joseph Culberson. Journal of Artificial Intelligence Research Volume 17, pages 309-332 , 2002.
• Hidden Solutions, Tell-tales, Heuristics and Anti-heuristics
  Joseph Culberson. Preprint in The IJCAI-01 Workshop on Empirical Methods in Artificial Intelligence pp 9-14
• The Phase Transition in NK Landscapes is Easy.
  Yong Gao and Joseph Culberson. in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 1227-1234, Morgan Kaufmann , 7-11 July 2001.
  Bibliographic Reference
  PrePrint
  Additional proofs and experimental results can be found in Gao's MSc Thesis
• Frozen Development in Graph Coloring
  Joseph Culberson and Ian P. Gent Theoretical Computer Science. Volume 265, Issue 1-2, 28 August 2001, pages 227-264
  A preprint version is available as APES-19-2000 APES Research Report with a mirror Copy at UofA
  The output files from the frozen development process can be retrieved here .
• Empirical Evidence for an Asymptotic Discontinuity in the Backbone of the 3-Coloring Phase Transition
  Joseph Culberson and Ian P. Gent APES-16-1999 APES Research Report A mirror Copy at UofA
• On the Probabilistic Approximate Completeness of WalkSAT for 2-SAT
  Joseph Culberson, Ian P. Gent and Holger Hoos. APES-15a-1999 APES Research Report A mirror Copy at UofA
• Well out of reach: Why hard problems are hard.
  Joseph Culberson and Ian P. Gent APES-13-1999 APES Research Report A mirror Copy at UofA
• Sokoban is PSPACE-complete
  Proceedings in Informatics 4, Fun With Algorithms, E. Lodi, L. Pagli and N. Santoro Eds. pp 65-76, Carleton Scientific, Waterloo. 1999
  Preprint in HTML format. Available as postscript (417K) technical report TR97-02.
• On the Futility of Blind Search: An Algorithmic View of "No Free Lunch".
  Joseph Culberson. Evolutionary Computation Journal 6(2):109--128, 1998.
  Technical Report Version
• The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle Problem
  Vandegriend, B. and Culberson, J. Journal of Artificial Intelligence Research, Volume 9, pages 219-245, 1998.
• Pattern Databases
  Joseph C. Culberson and Jonathan Schaeffer, Computational Intelligence, 14(3):318--334, 1998. 
• Searching with Pattern Databases
  Joseph C. Culberson and Jonathan Schaeffer Advances in Artificial Intelligence, 11th Biennial Conference of the Canadian Society for Computational Studies of Intelligence, AI'96. Lecture Notes in Artificial Intelligence 1081, Springer. pp 402-416, May 1996.
  Conference and 1994 Techreport version available here
• On Searching A-ary Hypercubes and Related Graphs
  Joseph Culberson and Jonathan Lichtner Foundations of Genetic Algorithms 4, Richard K. Belew and Michael D. Vose, editors, 263-290, 1996.
  Workshop held August 3-5, 1996. Univ. San Diego Abstract and Full paper
• Hiding our colors
  Joseph Culberson, Adam Beacham and Denis Papp. CP'95 Workshop, Studying and Solving Really Hard Problems, Cassis, France, pages 31--42, September 1995. Available here
• Exploring the k-colorable Landscape with Iterated Greedy
  Joseph Culberson and Feng Luo. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, David S. Johnson and Michael A. Trick (eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 26 , American Mathematical Society, pages 245-284 (1996). Abstract and Preprint
• Camouflaging Independent Sets in Quasi-Random Graphs.
  Mark Brockington and Joseph C. Culberson Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, David S. Johnson and Michael A. Trick (eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 26 , American Mathematical Society, pages 75-88 (1996). Abstract and Preprint
• Mutation-Crossover Isomorphisms and the Construction of Discriminating Functions
  Joseph Culberson. Evolutionary Computation. 2(3), 279-311, 1995. Abstract and Preprint
• Multicommodity flows in simple multistage networks
  Ehab S. Elmallah and Joseph Culberson. Networks Vol. 25 (1995) 19-30. Preliminary version available as Technical Report TR94-11
• Covering polygons is hard.
  Joseph C. Culberson, and Robert A. Reckhow. Journal of Algorithms vol 17, 2-44, 1994. Abstract and paper
• Crossover versus mutation: fueling the debate: TGA versus GIGA.
  Joseph Culberson In Stephanie Forrest, Editor, Proceedings of the Fifth International Conference on Genetic Algorithms, page 632,1993 Paper
• Searching in the plane.
  Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J. E. Rawlins. Information and Computation, vol 106(2), 234-252, 1993 Abstract
• A world championship caliber checkers program.
  Jonathan Schaeffer, Joseph Culberson, Norman Treloar, Brent Knight, Paul Lu, and Duane Szafron. Artificial Intelligence vol 53, 273-289, 1992 Abstract
• New results from an algorithm for counting posets.
  Joseph Culberson and Gregory J. E. Rawlins. Order vol 7, 361-374, 1991. Abstract
• Reviving the game of checkers.
  Jonathan Schaeffer, Joseph Culberson, Norman Treloar, Brent Knight, Paul Lu, and Duane Szafron. In D.N.L. Levy and D.F. Beal, editors, The Second Annual Computer Olympiad,pages 119-136, Ellis Horwood, London 1991. Abstract
• Analysis of the standard deletion algorithms in exact fit domain binary search trees.
  Joseph Culberson and J. Ian Munro. Algorithmica, vol 6, 295-311, 1990. Abstract
• Explaining the behavior of binary search trees under prolonged updates: A model and simulations.
  Joseph C. Culberson and J. Ian Munro. The Computer Journal, vol 32(1), 68-75, February 1989. Abstract
• A fast algorithm for constructing trees from distance matrices.
  Joseph C. Culberson and Piotr Rudnicki. Information Processing Letters, vol 30(4), 215-220, February 1989. Abstract
• Orthogonally convex coverings of orthogonal polygons without holes.
  Joseph Culberson and Robert A. Reckhow. Journal of Computer and System Sciences, vol 39(2), 166-204, October 1989. Abstract
• Covering polygons is hard: preliminary abstract.
  Joseph C. Culberson and Robert A. Reckhow. In 29th Annual Symposium on Foundations of Computer Science, vol 21, pages 601-611, White Plains, New York, October 1988. Abstract
• Searching with uncertainty (extended abstract).
  Ricardo A. Baeza-Yates, Joseph C. Culberson and Gregory J. E. Rawlins. In R. Karlsson and A. Lingas, editors, SWAT 88 1st Scandinavian Workshop on Algorithm Theory, pages 176-189. Springer-Verlag, 1988. Lecture Notes in Computer Science #318.
• Covering a simple orthogonal polygon with a minimum number of orthogonally convex polygons.
  Robert A. Reckhow and Joseph Culberson. In Proceedings of the Third Annual Symposium on Computational Geometry, pages 268-277, June 1987. Abstract
• The Effect of Updates in Binary Search Trees.
  Joseph Culberson In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 205-212, 1985.
• Turtlegons: Generating Simple Polygons from Sequences of Angles.
  Joseph C. Culberson and Gregory J. E. Rawlins, In Proceedings of the First Annual Symposium on Computational Geometry pages 305-310, 1985. Abstract

Selected Older Technical Reports

These reports mostly contain material that has not otherwise yet been published.

TR97-02: Sokoban is PSPACE-complete

Joseph Culberson

TR96-18: On the Futility of Blind Search

Joseph Culberson

TR94-09: Asymmetry in Binary Search Tree Update Algorithms

Joseph C. Culberson and Patricia A. Evans.

TR94-08: Efficiently Searching the 15-Puzzle

Joseph C. Culberson and Jonathan Schaeffer

TR92-02: Genetic Invariance: A New Paradigm for Genetic Algorithm Design

Joseph Culberson

TR92-06: GIGA Program Description and Operation

Joseph Culberson

TR92-07: Iterated Greedy Graph Coloring and the Difficulty Landscape

Joseph Culberson

TR89-06: A unified approach to orthogonal polygon covering problems via dent diagrams.

Joseph C. Culberson and Robert A. Reckhow. February 1989.

TR88-01: On the Comparison Cost of Partial Orders

Joseph Culberson and Gregory J. E. Rawlins.

Graduate Work

MSc Thesis

Updating Binary Trees University of Waterloo Department of Computer Science, 1984. (Available as Waterloo Research Report CS-84-08.) Abstract

Ph. D. Thesis

The Effect of Asymmetric Deletions on Binary Search Trees. University of Waterloo Department of Computer Science, May 1986. (Available as Waterloo Research Report CS-86-15.) Abstract

Joseph Culberson

May 2008