ß-Publications
   This list also contains the earlier publications of the Theory Group, which is now part of the ß-Lab.)
   2005

  • Mirela Andronescu, Zhi Chuan Zhang and Anne Condon, "Secondary Structure Prediction of Interacting RNA Molecules", Journal of Molecular Biology, 345 (5): 987-1001, Feb 2005 (pdf)
  • Stephane Durocher and David Kirkpatrick, "The Projection Median of a Set Points in R^2", Proceeding of the Seventeenth Canadian Conference on Computational Geometry, 2005 (to appear) (pdf, ps, bibtex)
  • Frank Hutter, Holger H. Hoos and Thomas Stützle, "Efficient Stochastic Local Search for MPE Solving", Proceeding of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05): 169-174, 2005(pdf, slides, bibtex)
  • Mohammad Ali Safari, "D-Width, A more Natural Measure For Directed Tree Width", 30th  International Symposium on Mathematical Foundation of Computer Science (MFCS), Poland, LNCS 3618: 745-756, 2005 (to appear)
  • Will Evans and Mohammad A. Safari, "Directed One Trees", The European Conference in Combinatorics, Graph Theory and Optimization (EuroComb05), Berlin, 2005 (to appear)
  • Alena Shmygelska, "Search for folding nuclei in native protein structures", Bioinformatics, 21: i394 - i402, 2005 (pdf). Best Student Paper Award at ISMB 2005.
  • Alena Shmygelska and Holger H. Hoos, "An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem", BMC Bioinformatics, 6:30, Feb 2005 (pdf). ACO-HPPFP Projet Page.
  • Dan Tulpan, Mirela Andronescu, Seo Bong Chang, Michael R. Shortreed, Anne Condon, Holger H. Hoos and Lloyd M. Smith, "Thermodynamically based DNA strand design", Nucleic Acids Research, 33 (15): 4951-4964, 2005 (to appear)
  • Michael R. Shortreed, Seo Bong Chang, DongGee Hong, Maggie Phillips, Bridget Campion, Dan C. Tulpan, Mirela Andronescu, Anne Condon, Holger H. Hoos and Lloyd M. Smith, "A thermodynamic approach to designing structure-free combinatorial DNA word sets", Nucleic Acids Research, 33 (15): 4965-4977, 2005 (to appear)
  • A.X. Jiang, K. Leyton-Brown, "Building Bidding Agents for Online Auctions with Hidden Bids" , Machine Learning Journal, 2005 (submitted). Short version was presented with the title "Computing Bidders' Valuation Distributions in Online Auctions" at the Game Theory and Decision Theory Workshop at the International Conference on Artificial Intelligence (IJCAI-05)
  • A. Lipson, K. Leyton-Brown and N. de Freitas, " Empirically Evaluating Multiagent Reinforcement Learning Algorithms", Machine Learning Journal, 2005 (submitted to) (pdf, ps, bib)
  • K. Leyton-Brown, E. Nudelman and Y. Shoham, " Empirical Hardness Models: Methodology and a Case Study on Combinatorial Auctions", Working Paper (pdf, ps, bib)
  • K. Leyton-Brown, M. Tennenholtz, Y. Shoham and N. Bhat, " Bidding Rings Revisited", Working Paper (pdf, ps)
   2004

  • Holger H. Hoos and Thomas Stützle: Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, San Francisco (CA), USA, 2004.
    (more information, including a table of contents and sample pages, can be found at www.sls-book.net)
  • Anne Condon, Beth Davy, Baharak Rastegari, Finbar Tarrant, and Shelly Zhao. "Classifying RNA Pseudoknotted Structures" , Theoretical Computer Science, 320(1):35-50, May 2004 (pdf)
  • Mirela Andronescu,  Anthony P. Fejes, Frank Hutter, Holger H. Hoos and Anne Condon, "A New Algorithm for RNA Secondary Structure Design", Journal of Molecular Biology, 336 (3): 607-624, Feb 2004 (pdf)
  • Stephane Durocher and David Kirkpatrick, "The Gaussian Centre and the Projection Centre of a Set Points in R^3", Proceeding of the Sixteenth Canadian Conference on Computational Geometry, 16:140-144, 2004 (pdf, ps, bibtex)
  • J. Mark Keil and P. Belleville, "Dominating the Complements of Bounded Tolerance Graphs and the Complements of Trapezoid Graphs",  Discrete Applied Mathematics, 140:73--89, May 2004 (pdf)
  • E. Nudelman, K. Leyton-Brown, A. Devkar, Y. Shoham and H. Hoos, "Understanding Random SAT: Beyond the Clauses-to-Variables Ratio", Presented at the Tenth International Conference on Principles and Practice of Constraint Programming (CP-04), 2004 (pdf, ps, bib)
  • N. Bhat and K. Leyton-Brown, "Computing Nash Equilibria of Action-Graph Games", Presented at the 20th Conference on Uncertainty in Artificial Intelligence (UAI), 2004 (pdf, ps, bib), Short versions appeared the at Second World Congress on Game Theory (Games2004) and the Stony Brook Game Theory Conference, 2004
  • E. Nudelman, J. Wortman, Y. Shoham and K. Leyton-Brown, "Run the GAMUT: A Comprehensive Approach to Evaluating Game-Theoretic Algorithms", Presented at the Third International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-04), 2004 (pdf, ps, bib), Short versions appeared at the Second  World Congress on Game Theory (Games2004) and the Stony Brook Game Theory Conference, 2004
  • E. Nudelman, K. Leyton-Brown, A. Devkar, Y. Shoham and H. Hoos, "SATzilla: An Algorithm Portfolio for SAT",
    Presented at the Eight International Symposium on Artificial Intelligence and Mathematics (AI+Math2004), 2004 (pdf, ps, bib)
   2003

  • S. P. Shah, G. P. McVicker, A. K. Machworth, S. Rogic and B. F. F. Ouellette, "GeneComber: Combining Outputs of Gene Prediction Programs for Improved Results", Bioinformatics, 19(10): 1296-1297, July 2003 (pdf)
  • Stephane Durocher, Alex Brodsky and Ellen Gethner, "Toward the Rectilinear Crossing Number of K_n", Discrete Mathematics, 262: 59-77,  2003 (pdf, ps, bibtex)
  • Stephane Durocher and David Kirkpatrick, "The Gaussian Centre of a Set of Mobile Points", Proceeding of the Fifteenth Canadian Conference on Computational Geometry, 15:123-127, 2003 (pdf, ps, bibtex, java demo)
  • Mirela Andronescu,  Rosalia Aguirre-Hernandez,  Anne Condon and Holger H. Hoos, "RNAsoft: a Suite of RNA Secondary Structure Prediction and Desgin Software Tools", Nucleic Acids Research, 31: 3416-3422, July 2003 (pdf)
  • Mirela Andronescu, Danielle Dees, Laura Slaybaugh, Yinglei Zhao, Anne Condon, Barry Cohen and Steven Skiena, "Algorithms for testing that sets of DNA words concatenate without secondary structure", Natural Computing, 2(4): 391-415, Jan 2003 (pdf)
  • Mirela Andronescu, Danielle Dees, Laura Slaybaugh, Yinglei Zhao, Anne Condon, Barry Cohen and Steven Skiena, "Algorithms for testing that DNA word designs avoid unwanted secondary structures'', Eighth International Meeting on DNA Based Computers (DNA 8), Sapporo, Japa, May 2002; Lecture Notes in Computer Science, 2568: 182-195, Jun 2002 (pdf)
  • Alena Shmygelska and Holger H. Hoos, "An Improved Ant Colony Optimisation Algorithm for the 2D HP Protein
    Folding Problem    ", Proceeding of the Sixteenth Canadian Conference on Artificial Intelligence (AI'2003), 2003 (pdf)
   2002

  • S. Rogic, B. F. F. Ouellette and A. K. Machworth, "Improving Gene Recognition Accuracy by Combining Prediction from Two Gene-Finding Programs", Bioinformatics, 16(8): 1034-1045, Aug 2002 (pdf)
  • Stephane Durocher and David Kirkpatrick, "On the Hardness of Turn-Angle-Restricted Rectilinear Cycle Cover Problems", Proceeding of the Fourteenth Canadian Conference on Computational Geometry, 14:13-16, 2002 (pdf, ps, bibtex)
  • Frank Hutter, Dave A.D. Tompkins and Holger H. Hoos, "Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT", Proceeding of the Eight International Conference on Principals and Practice of Constraint Programming (CP'02), LNCS 2470: 233-248, 2002 (pdf)
  • Alena Shmygelska, Rosalia Aguirre-Hernndez and Holger H. Hoos, "An Ant Colony Optimization Algorithm for the 2D HP Protein Folding Problem", Proceeding of Third International Workshop, ANTS 2002, Springer's Lecture Notes in Computer Science (LNCS) series, 2463: 40-52, 2002 (pdf, ps, bibtex). Best Paper Award at ANTS 2002.
   2001

  • S. Rogic, A. K. Machworth and B. F. F. Ouellette, "Evaluation of gene finding programs", Genome Research, 11: 817-832, May 2001 (Abstract , pdf)
  • Stephane Durocher, Alex Brodsky and Ellen Gethner, "The Rectilinear Crossing Number of K_10 is 62", Electronic Journal of Combinations, 8(1):R23, 2001 (pdf, ps, bibtex)
   2000

  • Holger H. Hoos and Kevin O'Neill, "Stochastic Local Search Methods for Dynamic SAT - an Initial Investigation", UBC CS Technical Report TR-2000-01, 2000.
   1999

  • Holger H. Hoos, "Heavy-Tailed Behaviour in Randomised Systematic Search Algorithms for SAT?", UBC CS Technical Report TR-99-16, 1999.
  • Hamish Carr, Jack Snoeyink and Ulrike Axen, "Computing Contour Trees in All Dimensions", UBC CS Technical Report TR-99-09, 1999.
  • Holger H. Hoos, "Systematic vs. Local Search for SAT", UBC CS Technical Report TR-99-06, 1999.
  • Alex Brodsky and Nicholas Pippenger, "Characterizations of 1-Way Quantum Finite Automata", UBC CS Technical Report TR-99-03 Revised, 1999.
   1998

  • Nicholas Pippenger, "Galois Theory for Minors of Finite Functions", UBC CS Technical Report TR-98-08, 1998.
  • Joel Hass, Jeffrey C. Lagarias and Nicholas Pippenger, "The Computational Complexity of Knot and Link Problems", UBC CS Technical Report TR-98-07, 1998.
  • Nicholas Pippenger, "Entropy and Enumeration", UBC CS Technical Report TR-98-02, 1998.
   1997

  • Nicholas Pippenger, "Average-Case Bounds on the Complexity of Path-Search", UBC CS Technical Report TR-97-13, 1997.
   1995

  • William Evans and Nicholas Pippenger, "On the Maximum Tolerable Noise for Reliable Computation by Formulas", UBC CS Technical Report TR-95-20, 1995.
  • Dwight J. Makaroff and Raymond T. Ng, "Buffer Sharing Schemes for Continuous-Media Systems", UBC CS Technical Report TR-95-01, 1995.
   1994

  • Raymond T. Ng and Xiaomei Tian, "Incremental Algorithms for Optimizing Model Computation Based on Partial Instantiation", UBC CS Technical Report TR-94-21, 1994.
  • Raymond T. Ng and Jinhai Yang, "An Analysis of Buffer Sharing and Prefetching Techniques for Multimedia Systems", UBC CS Technical Report TR-94-20, 1994.
  • David Kirkpatrick and Jack Snoeyink, "Computing Common Tangents Without a Separating Line", UBC CS Technical Report TR-94-15, 1994.
  • Nicholas Pippenger, "Topological Aspects of Regular Languages", UBC CS Technical Report TR-94-14, 1994.
  • Raymond T. Ng and Jiawei Han, "Efficient and Effective Clustering Methods for Spatial Data Mining", UBC CS Technical Report TR-94-13, 1994.
  • Raymond T. Ng, "Semantics, Consistency and Query Processing of Empirical Deductive Databases", UBC CS Technical Report TR-94-11, 1994.
   1993

  • Nicholas Pippenger, "Juggling Networks", UBC CS Technical Report TR-93-42, 1993.
  • Nicholas Pippenger, "Self-Routing Superconcentrators", UBC CS Technical Report TR-93-34, 1993.
  • Nicholas Pippenger, "Analysis of a Recurrence Arising from a construction for Non-Blocking Networks", UBC CS Technical Report TR-93-33, 1993.
  • Heinz Breu and David Kirkpatrick, "Unit Disk Graph Recognition is NP-Hard*", UBC CS Technical Report TR-93-27, 1993.
   1992

  • Nicholas Pippenger, "Rearrangeable Circuit-Switching Networks", UBC CS Technical Report TR-92-14, 1992.
  • Nicholas Pippenger, "An Elementary Approach to Some Analytic Asymptotics", UBC CS Technical Report TR-92-09, 1992.
  • Nicholas Pippenger, "Symmetry in Self-Correcting Cellular Automata", UBC CS Technical Report TR-92-08, 1992.
   1990

  • Nicholas Pippenger, "The Blocking Probability of Spider-Web Networks", UBC CS Technical Report TR-90-18, 1990.
  • Nicholas Pippenger, George D. Stamoulis and John N. Tsitsiklis, "On a Lower Bound for the Redundancy of Reliable Networks with Noisy Gates", UBC CS Technical Report TR-90-13, 1990.
  • Nicholas Pippenger, "Selection Networks", UBC CS Technical Report TR-90-12, 1990.
  • Lin and Nicholas Pippenger, "Parallel Algorithms for Routing in Non-Blocking Networks", UBC CS Technical Report TR-90-10, 1990.
   1989

  • Nicholas Pippenger, "The Expected Capacity of Concentrators", UBC CS Technical Report TR-89-18, 1989.
  • Nicholas Pippenger, "Exactly Solvable Telephone Switching Problems", UBC CS Technical Report TR-89-17, 1989.
  • Nicholas Pippenger, "Enumeration of Equicolourable Trees", UBC CS Technical Report TR-2000-04, 2000.
  • Nicholas Pippenger, "The Asymptotic Optimality of Spider-Web Networks", UBC CS Technical Report TR-89-15, 1989.

For comments or updates please send a message to beta-web [at] cs [dot] ubc [dot] ca