Carla P. Gomes

Home Research Agenda Presentations Papers Demos

If you would like a copy of a paper that is not available here, please email me.

Surveys

Satisfiability Solvers. Carla Gomes, Heny Kautz, Ashish Sabharwal, and Bart Selman. Handbook of Knowledge Representation. 2007. PDF (draft)

Randomness and Structure. Carla Gomes and Toby Walsh. Handbook of Constraint Programming, F. Rossi, P. van Beek, T. Walsh (eds.), Elsevier, 2006. Abstract PDF

Approximation Algorithms. Carla Gomes and Ryan Williams. Introduction to Optimization, Decision Support and Search Methodologies,Burke and Kendall (Eds.),Kluwer, 2005. PDF

Complete Randomized Backtrack Search. Carla Gomes. In Constraint and Integer Programming: Toward a Unified Methodology, Milano, M., (ed.), Kluwer, 2003, 233-283. PDF

Hill Climbing Search. Bart Selman and Carla Gomes. In Nature Encyclopedia of Cognition, Nature Publ., 2002. PDF

Recent Papers

The Impact of Network Topology on Pure Nash Equilibria in Graphical Games. Bistra Dilkina, Carla Gomes, and Ashish Sabharwal. AAAI-07. 22nd Conference on Artificial Intelligence, Vancouver, B.C., Canada, July 2007. (Nominated for Best Paper Award). PDF

Counting CSP Solutions Using Generalized XOR Constraints. Carla Gomes, Willem van Hoeve, Ashish Sabharwal, and Bart Selman. AAAI-07. Proceedings of the 22nd National Conference on Artificial Intelligence, Vancouver, Canada, Jul 2007. PDF

From Sampling to Model Counting. Carla Gomes, Ashish Sabharwal, and Bart Selman. IJCAI07. Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, Jan 2007. (Nominated for Best Paper Award). PDF

Optimal Multi-Agent Scheduling with Constraint Programming. Willem van Hoeve, Carla Gomes, Michele Lombardi, and Bart Selman. In Proceedings of the Nineteenth Conference on Innovative Applications of Artificial Intelligence (IAAI 2007), 2007. PDF

Tradeoffs in the Complexity of Backdoor Detection. Bistra Dilkina, Carla Gomes, and Ashish Sabharwal. Proc. 13th International Conference on Principles and Practice of Constraint Programming, Providence, RI, Sep 2007. PDF

Connection in Networks: Hardness of Feasibility versus Optimality. Jon Conrad, Carla Gomes, Willem van Hoeve, Ashish Sabharwal, and Jordan Suter. CPAIOR07. Proc. of the 4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Brussels, Belgium, May 2007. PDF

Spatially-Balanced Complete Block Designs for Field Experiments Harold van Es, Carla Gomes, Meinolf Sellmann, and Cindy van Es. Geoderma Journal, Vol. 140 (2007) 346--352. PDF

Model Counting: A New Strategy for Obtaining Good Bounds. Carla Gomes, Ashish Sabharwal, and Bart Selman. AAAI-06. Proceedings of the 21st National Conference on Artificial Intelligence, pp 54-61, Boston, MA, Jul 2006. (Best Paper Award). PDF Slides

Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints. Carla Gomes, Ashish Sabharwal, and Bart Selman. NIPS-06. Proceedings of the 20th Annual Conference on Neural Information Processing Systems. Vancouver, B. C., Dec 2006. PDF

QBF Modeling: Exploiting Player Symmetry for Simplicity and Efficiency Ashish Sabharwal, Carlos Ansotegui, Carla Gomes, Justin Hart, and Bart Selman. SAT-06. Proceedings of the 9th International Conference on Theory and Applications of Satisfiability Testing, LNCS, volume 4121, pp 382-395, Seattle, WA, Aug 2006. PDF

Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in Sat-Based Planning Joerg Hoffmann, Carla Gomes, and Bart Selman. ICAPS-06. Proceedings of International Conference on Automated Planning and Scheduling, Cumbria, UK, June 2006. PDF

The Impact of Balancing on Problem Hardness in a Highly Structured Domain Carlos Ansotegui, Ramon Bejar, Cesar Fernandez, Carla Gomes, and Carles Mateu SAT-06. Proceedings of the 9th International Conference on Theory and Applications of Satisfiability Testing, LNCS, volume 4121, Seattle, WA, Aug 2006. (This paper studies the hardness of Generalized Sudoku). PDF

The Power of Semidefinite Programming Relaxations for MAXSAT. Carla Gomes, Willem van Hoeve, and Lucian Leahu. Proc. of Conference on Integration of AI/OR Techniques (CPAIOR 2006), 2006. PDF

Statistical Regimes Across Constrainedness Regions. Carla Gomes, Cesar Fernandez, Bart Selman, and Christian Bessiere. Constraints (extended version of conference version). 2005. Postscript PDF.

Achilles' Heel of QBF. Carlos Ansotegui, Carla Gomes, and Bart Selman. Proc. AAAI, 2005. PDF.

Can Get Satisfaction. Carla Gomes and Bart Selman. Nature Vol. 435, June 9, 2005, 751--752. (News & Views article). PDF

Sensor networks and distributed CSP: Communication, Computation and Complexity. Ramon Bejar, Carmel Dohmslak, C. Fernandez, C. Gomes, B. Krishnamachari, B. Selman, and M. Valls. Artificial Intelligence Journal, Vol. 161(1/2), 2005, 117-147. PDF

Approximations and Randomization to Boost CSP Technique. Carla Gomes and David Shmoys. Annals of Operations Research. Vol 130 (1), Aug. 2004, 117--141 PDF

Statistical Regimes Across Constrainedness Regions Carla Gomes, Cesar Fernandez, Bart Selman, and Christian Bessiere. In Proc. of 10th Conf. on Principles and Practice of Constraint Programming (CP-04) 2004. Postscript PDF Distinguished Paper Award.

Streamlined Constrained Reasoning. Carla Gomes and Meinolf Sellmann. In Proc. of 10th Conf. on Principles and Practice of Constraint Programming (CP-04) 2004. Postscript PDF

Quality of LP-based Approximations for Highly Combinatorial Problems. Lucian Leahu and Carla Gomes. In Proc. of 10th Conf. on Principles and Practice of Constraint Programming (CP-04) 2004. Postscript PDF

Cardinality Matrix Constraint. Jean-Charles Regin and Carla Gomes. In Proc. of 10th Conf. on Principles and Practice of Constraint Programming (CP-04) 2004. Postscript PDF

The Challenge of Generating Spatially Balanced Scientific Experiment Designs Carla Gomes, Meinolf Sellmann, Cindy van Es, and Harold van Es. In Proc. of Conf. on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR '04), 2004. Postscript PDF

An Improved Approximation for the Partial Latin Square Extension Problem. Carla Gomes, Rommel Regis, and David Shmoys. In Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA-2003), Baltimore, MD, 2003. Postscript PDF

Backdoors to Typical Case Complexity. Ryan Williams, Carla Gomes, and Bart Selman. In Proc. IJCAI 2003. Further results presented at AAAS-04. PDF

On the Connections between Heavy-tails, Backdoors, and Restarts in Combinatorial search. Ryan Williams, Carla Gomes, and Bart Selman. In Proc. SAT 2003. PDF

Satisfied with Physics. Carla Gomes and Bart Selman. Science, Vol. 287, 784-785, Aug 02, 2002. PDF

Science News article by Ivars Peterson. "Completing Latin Squares"

The Promise of LP to Boost CSP Techniques for Combinatorial Problems. Carla Gomes and David Shmoys. In Proceedings of the 4th International Symposium on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR '02), 291-305, Le Croisic, France, 291-305, March 2002. Postscript PDF

Dynamic Restart Policies. Henry Kautz, Eric Horvitz, Yongshao Ruan, Carla Gomes, and Bart Selman. Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02), Edmonton, Alberta, Canada, 2002, 674-682. Postscript PDF

Completing Quasigroups or Latin Squares: A Structured Graph Coloring Problem. Carla Gomes and David Shmoys. In Proceedings of the Computational Symposium on Graph Coloring and Extensions, 2002. PDF Postscript

Communication and Computation in DisCSP Algorithms. Cesar Fernandez, Ramon Bejar, Bhaskar Krishnamachari, and Carla Gomes. In Proceedings of the Eighth Conference on Principles and Practices of Constraint Programming (CP-02) 2002. Postscript PDF

Formal Models of Heavy-tailed Behavior in Combinatorial Search. Hubie Chen, Carla Gomes, and Bart Selman. In Proceedings of the Seventh International Conference on Principles and Practices of Constraint Programming (CP-01) 2001. Postscript PDF

On the Intersection of Artificial Intelligence and Operations Research. Carla Gomes. Journal of Knowledge Engineering Review, Cambridge Press, Vol.16 1, 2001, 1-6.

Algorithm Portfolios. Carla Gomes and Bart Selman. Artificial Intelligence Journal, Vol. 126, 2001, 43-62. Postscript PDF

Capturing the Structure of Satisfiability. Ramon Bejar, Alba Cabiscol, Cesar Fernandez, Felip Manya, and Carla Gomes. Proceedings of Seventh Intl. Conference on the Principles and Practice of Constraint Programming (CP-2001), 2001, 137-153.

Extending the Reach of Proof Planning by Randomization and Restart Strategies. Andreas Meier, Carla Gomes, and Erica Melis. IJCAR, 2001.

Balance and Filtering in Structured Satisfiable Problems. Henry Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla Gomes, Bart Selman, and Mark Stickel. Proceedings of the 17th International Conference on Artificial Intelligence (IJCAI-2001), Seattle, 2001.PDF

A Bayesian Approach to Tackling Hard Computational Problems. Eric Horvitz, Yongshao Ruan, Carla Gomes, Henry Kautz, Bart Selman, and Mark Chickering. Proceedings 17th Conf. on Uncertainty and Artificial Intelligence (UAI-2001), Seattle, 2001.

An Application of Randomization and Restarts in Proof Planning. Andreas Meier, Carla Gomes, and Erica Melis. Proceedings of the 6th European Conference on Planning (ECP-01), Toledo, Spain, 2001.

Generating Hard Feasible Schedules. Carlos Argelich, Ramon Bejar, Alba Cabiscol, Cesar Fernandez, Felip Manya, and Carla Gomes. Proceedings of the 6th European Conference on Planning (ECP-01), Toledo, Spain, 2001.

Structure, Duality, and Randomization --- Common Themes in AI and OR. Carla Gomes. Invited Talk, Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-00), Austin, TX, 2000. (Written version of invited plenary talk.). Postscript PDF

Generating Satisfiable Instances. Dimitris Achlioptas, Carla Gomes, Henry Kautz, and Bart Selman. In Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-00), Austin, TX, 2000. Postscript PDF

Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems. Carla Gomes, Bart Selman, Nuno Crato, and Henry Kautz. Journal of Automated Reasoning, Vol. 24(1/2), pages 67-100, 2000. PDF

Hybrid Strategies for Heterogeneous Search Spaces. Carla Gomes and Bart Selman. International Journal on Artificial Intelligence Tools, Vol. 9(1), 2000

Artificial Intelligence and Operations Research: Challenges and Opportunities in Planning and Scheduling. Carla Gomes. Journal of Knowledge Engineering Review, Vol. 15, 1, 2000.

A Connection Between Phase Transitions in Complexity and Good Decodings. Carla Gomes, Stephen Wicker, and Xi Xie. Proc. of the International Symposium on Information Theory and its Applications, 2000.

Heavy-tails, Phase Transitions, and the Nature of Cutoff and Capacity. Carla Gomes, Xi Xie, Stephen Wicker, and Bart Selman. In Forney Festschrift, Kluwer, 2000. PDF

On the Fine Structure of Large Search Spaces. Carla Gomes and Bart Selman. In Proceedings the Eleventh International Conference on Tools with Artificial Intelligence ICTAI'99, Chicago, IL, November 1999. PDF Postscript

Search Strategies for Hybrid Search Spaces. Carla Gomes and Bart Selman. In Proceedings the Eleventh International Conference on Tools with Artificial Intelligence ICTAI'99, Chicago, IL, November 1999.

Heavy-tailed Distributions in Computational Methods. Carla Gomes and Bart Selman. In Proc. Application of Heavy Tailed Distribution in Economics, Engineering and Statistics (TAILS-99), 1999.

Boosting Combinatorial Search Through Randomization. Carla Gomes, Bart Selman, and Henry Kautz. Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98). PDF Postscript Compressed Postscript

Randomization in Backtrack Search: Exploiting Heavy-Tailed Profiles for Solving Hard Scheduling Problems. Carla Gomes, Ken McAloon, Bart Selman, and Carol Tretkoff. Proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems (AIPS-98), Pittsburgh, PA, 1998. Compressed Postscript

Heavy-tailed Distributions in Combinatorial Search. Carla Gomes, Bart Selman, and Nuno Crato. In Principles and Practices of Constraint Programming, (CP-97) Lecture Notes in Computer Science 1330, pp 121-135, Linz, Austria., 1997. Springer-Verlag. Postscript PDF Compressed Postscript

Problem Structure in the Presence of Perturbations. Carla Gomes and Bart Selman. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), New Providence, RI, 1997.

Algorithm Portfolio Design: Theory vs. Practice. Carla Gomes and Bart Selman. In Proceedings of the Thirteenth Conference On Uncertainty in Artificial Intelligence (UAI-97), New Providence, RI, 1997. Morgan Kaufmann. Compressed Postscript

A Transformational Approach Applied to Outage Management of Nuclear Power Plants. C. Gomes, D. Smith, and S. Westfold. Proceedings of the 13th HICC, IEEE Computer Society, 1997.

Technology for Planning and Scheduling under Complex Constraints. Carla Gomes and Karen Alguire. In Proceedings of Society for Optical Engineering, 1997, Boston.

Synthesis of Schedulers for Planned Shutdowns of Power Plants. Carla Gomes, Douglas Smith, and Stephen Westfold. In Proceedings of the Eleventh Knowledge-Based Software Engineering Conference, IEEE Computer Society Press, 1996.

ROMAN: An Application of Advanced Technology to Outage Management. Karen Alguire and Carla Gomes. Proceedings of the Sixth Annual Dual-Use Technologies and Applications Conference, IEEE Computer Society Press, 1996.