Ashish Sabharwal

Research Associate
Cornell-CS Cornell-CS

   Institute for Computational Sustainability (ICS)
   Intelligent Information Systems Institute (IISI)

office: 5160 Upson Hall, Cornell University
tel: 607.255.8563   |   fax: 607.255.4428
first-six-letters-of-lastname at c s dot cor nell dot edu

NOTE: As of May 2014, I am a senior research scientist at Allen Institute for Artificial Intelligence (AI2).
Please visit my new homepage at AI2 for updated information.

During Oct 2010 - Apr 2014, I was a research scientist at IBM Watson Research Center.






Curriculum Vitae : pdf (as of Jan 2010)               (please click here for a shorter CV and further information)
 
Education : 2005 - 2008   Postdoctoral Associate in Computer Science, Cornell University
1998 - 2005   Ph.D. and M.S. at the University of Washington (UW), Seattle     [thesis]
1994 - 1998   Bachelor of Technology at the Indian Institute of Technology (IIT), Kanpur
 
Short Bio : txt
 
Other Listings : DBLP    CiteSeerX    AI Genealogy Project    Math Genealogy Project


Research

Research Interests: Artificial Intelligence; Combinatorial Reasoning; Constraints; Probabilistic Inference; Multi-Agent and Adversarial Reasoning; Optimization. Application areas: Planning, Scheduling, Verification, Diagnosis.

Recent Focus: Computational Sustainability


SOFTWARE & BENCHMARKS

  • 3S or Satisfiability Solver Selector is a portfolio solver for SAT develped with my colleagues at IBM Watson and Brown University. Unlike currently dominating portfolio solvers like SATzilla, 3S does not rely on learning a model for the runtime behavior of each SAT solver on various classes of instances (so-called empirical hardness models). Instead, it brings together ideas such as simple k-nearest neighbor recommendation and a fixed-split solver schedule, generated using the column generation technique from Integer Programming, in order to create a powerful portfolio solver. For details, see papers titled Non-Model-Based Algorithm Portfolios for SAT at SAT-2011 and Algorithm Selection and Scheduling at CP-2011.

    3S won 7 medals at SAT Competition 2011 (link). It is a sequential solver, by design. To the best of my knowledge, 3S is the only single solver to ever win two main sequential categories of the Competition (namely, Crafted and Random instances) and be ranked in the top-10 in the third category (Application/Industrial instances).

  • BPCount is a SAT model counter based on ideas very similar to SampleCount (see below), with the major difference being in the way marginal values of variables are estimated: it uses Belief Propagation (and its generalizations) rather than local search based sampling of solutions. For details, see the paper titled Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting at CPAIOR-08 and its journal version in Annals of Operations Research (ANOR-2011).

    MiniCount is another model counter proposed in the same paper as BPCount. It is one of the first model counters that can provide a good upper bound with an accuracy guarantee, namely, a statistical correctness guarantee if the underlying search tree satisfies a commonly observed log-normal search depth behavior.

  • SampleCount is a SAT model counter, i.e., a tool that computes the number of solutions of a given Boolean formula. It uses solution sampling to cut down the search space in a controlled manner, and is the first tool to provide guaranteed lower bounds on the model count without assuming what-so-ever about the quality of the solution samples. For details, see the paper titled From Sampling to Model Counting at IJCAI-07.

    Download source code: tgz, tar.bz2, zip, README.

    • Includes an enhanced version of Approxcount.
    • Includes SampleSat as a command-line option.

  • Approxcount [Wei and Selman, 2005]. Download stand-alone source code: tgz, tar.bz2, zip, README.

  • SampleSat [Wei et al. 2004]. Now available as an integrated command-line option in Approxcount/SampleCount. See usage in SampleCount README.

  • MBound is also a SAT model counter like SampleSat. However, the approach used by it is different. It employs randomly generated parity or XOR constraints for domain-independent streamlining of the input formula, while maintaining a good handle on the solution count of the original formula. It provides probabilistic guarantees on the obtained model count. For details, see the paper titled Model Counting: A New Strategy for Obtaining Good Bounds at AAAI-06.

    Download simple scripts for adding random XORs to formulas: tgz, tar.bz2, zip, README.

  • XorSample is a technique for near-uniformly sampling the solutions of a combinatorial problems, specifically, SAT formulas. Like MBound, it uses randomly generated parity or XOR constraints for domain-independent streamlining of the input formula to fewer and fewer solutions. For details, see the paper titled Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints at NIPS-06.

    Download simple scripts for adding random XORs to formulas: tgz, tar.bz2, zip, README.

  • Duaffle is a quantified Boolean formula solver (QBF solver) that uses a split dual CNF-DNF format both internally and for input representation. This facilitates significantly better constraint propagation and avoids other issues that traditional CNF-based QBF solvers run into. Duaffle is implemented as an extension of the QBF solver Quaffle from Princeton. For details, see the paper titled QBF Modeling: Exploiting Player Symmetry for Simplicity and Efficiency at SAT-06.

    Download source code: tgz, tar.bz2, zip, README.

  • SymChaff is a propositional satisfiability solver (SAT solver) that implements a new technique to exploit structural symmetry present in a problem instance. For details, see papers titled SymChaff: A Structure-Aware Satisfiability Solver at AAAI-05 and SymChaff: Exploiting Symmetry in a Structure-Aware Satisfiability Solver in the Constraints Journal, 2009.

    Download source code from the SymChaff webpage.

  • Benchmarks


BOOK CHAPTERS AND SURVEYS

  • Book Review: S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, Third Edition [published]
    Ashish Sabharwal, Bart Selman
    AIJ-2011. Artificial Intelligence, Special Review Issue, Elsevier, volume 175, number 5-6, pp 935-937, Apr 2011.

  • Incomplete Algorithms (for Satisfiability) [published, draft pdf]
    Henry Kautz, Ashish Sabharwal, Bart Selman
    Handbook of Satisfiability, IOS Press. Editors: Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh. Chapter 6, pp 185-203, 2009.

  • Model Counting [published, draft pdf]
    Carla P. Gomes, Ashish Sabharwal, Bart Selman
    Handbook of Satisfiability, IOS Press. Editors: Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh. Chapter 20, pp 633-654, 2009.

  • Exploiting Runtime Variation in Complete Solvers (for Satisfiability) [published]
    Carla P. Gomes, Ashish Sabharwal
    Handbook of Satisfiability, IOS Press. Editors: Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh. Chapter 9, pp 271-288, 2009.

  • Satisfiability Solvers
    Carla P. Gomes, Henry Kautz, Ashish Sabharwal, Bart Selman [pdf, bib]
    Handbook of Knowledge Representation, in the series Foundations of Artificial Intelligence, vol. 3. Editors: Frank van Harmelen, Vladimir Lifschitz, and Bruce Porter. Elsevier, pp 89-134, 2008.


CONFERENCE PUBLICATIONS (refereed and archived)

   [2011]

  • Accelerated Adaptive Markov Chain for Partition Function Computation [draft]
    Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman
    NIPS-2011. 25th Annual Conference on Neural Information Processing Systems, Granada, Spain, Dec 2011.

  • [3S paper #2] Algorithm Selection and Scheduling [pdf, slides]
    Serdar Kadioglu, Yuri Malitsky, Ashish Sabharwal, Horst Samulowitz, and Meinolf Sellmann
    CP-2011. 17th International Conference on Principles and Practice of Constraint Programming, LNCS volume 6876, pp 454-469, Perugia, Italy, Sep 2011.

  • Constraint Reasoning and Kernel Clustering for Pattern Decomposition With Scaling [pdf]
    Ronan LeBras, Theodoros Damoulas, John M. Gregoire, Ashish Sabharwal, Carla P. Gomes, R. Bruce van Dover
    CP-2011. 17th International Conference on Principles and Practice of Constraint Programming, LNCS volume 6876, pp 508-522, Perugia, Italy, Sep 2011.

  • A General Nogood-Learning Framework for Pseudo-Boolean Multi-Valued SAT [PDF]
    Siddhartha Jain, Ashish Sabharwal, Meinolf Sellmann
    AAAI-11. 25th AAAI Conference on Artificial Intelligence, San Francisco, CA, August 2011.

  • [3S paper #1] Non-Model-Based Algorithm Portfolios for SAT [pdf, poster]
    Yuri Malitsky, Ashish Sabharwal, Horst Samulowitz, Meinolf Sellmann
    SAT-2011. 14th International Conference on Theory and Applications of Satisfiability Testing, LNCS volume 6695, pp 369-370, Ann Arbor, MI, June 2011.

   [2010]

  • An Empirical Study of Optimization for Maximizing Diffusion in Networks [pdf]
    Kiyan Ahmadizadeh, Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal
    CP-2010. 16th International Conference on Principles and Practice of Constraint Programming, LNCS volume 6308, pp 514-521, St Andrews, Scotland, Sep 2010.

  • An Empirical Study of Optimal Noise and Runtime Distributions in Local Search [pdf, slides]
    Lukas Kroc, Ashish Sabharwal, Bart Selman
    SAT-2010. 13th International Conference on Theory and Applications of Satisfiability Testing, LNCS volume 6175, pp 346-351, Edinburgh, UK, July 2010.

  • Understanding Sampling Style Adversarial Search Methods [PDF]
    Raghuram Ramanujan, Ashish Sabharwal, Bart Selman
    UAI-2010. 26th Conference on Uncertainty in Artificial Intelligence, Avalon / Catalina Island, CA, pp 474-483, July 2010.

  • Maximizing Spread of Cascades Using Network Design [PDF]
    Daniel Sheldon, Bistra Dilkina, Adam Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad,Carla Gomes, David Shmoys, Will Allen, Ole Amundsen, William Vaughan
    UAI-2010. 26th Conference on Uncertainty in Artificial Intelligence, Avalon / Catalina Island, CA, pp 517-526, July 2010.

  • On Adversarial Search Spaces and Sampling-Based Planning [PDF]
    Raghuram Ramanujan, Ashish Sabharwal, Bart Selman
    ICAPS-2010. 29th International Conference on Automated Planning and Scheduling, pp 242-245, Toronto, Canada, June 2010.

   [2009]

  • Integrating Systematic and Local Search Paradigms: A New Strategy for MaxSAT [pdf, slides]
    Lukas Kroc, Ashish Sabharwal, Carla P. Gomes, Bart Selman
    IJCAI-09. 21st International Joint Conference on Artificial Intelligence, pp 544-551, Pasadena, CA, July 2009.
    Also at the SoCS-09 symposium.

  • Relaxed DPLL Search for MaxSAT [pdf, slides]
    Lukas Kroc, Ashish Sabharwal, Bart Selman
    SAT-09. 12th International Conference on Theory and Applications of Satisfiability Testing, LNCS volume 5584, pp 447-452, Swansea, Wales, U.K., June 2009. (short paper).

  • Backdoors in the Context of Learning [pdf, slides, with extended version as a Tech Report]
    Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal
    SAT-09. 12th International Conference on Theory and Applications of Satisfiability Testing, LNCS volume 5584, pp 73-79, Swansea, Wales, U.K., June 2009. (short paper).

  • Backdoors to Combinatorial Optimization: Feasibility and Optimality [PDF, draft pdf]
    Bistra Dilkina, Carla P. Gomes, Yuri Malitski, Ashish Sabharwal, Meinolf Sellmann
    CPAIOR-09. 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, LNCS volume 5547, pp 56-70, Pittsburgh, PA, May 2009.

  • Message-Passing and Local Heuristics as Decimation Strategies for Satisfiability [pdf, bib, slides]
    Lukas Kroc, Ashish Sabharwal, Bart Selman
    SAC-09. 24th Annual ACM Symposium on Applied Computing, pp 1408-1414, Honolulu, HI, Mar 2009.

   [2008]

  • Counting Solution Clusters in Graph Coloring Problems Using Belief Propagation [pdf, bib, spotlight-slide]
    Lukas Kroc, Ashish Sabharwal, Bart Selman
    NIPS-08. 22nd Annual Conference on Neural Information Processing Systems, pp 873-880, Vancouver, BC, Canada, Dec 2008.

  • [BPCount and MiniCount paper #1] Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting [pdf, bib, slides, journal version]
    Lukas Kroc, Ashish Sabharwal, Bart Selman
    CPAIOR-08. 5th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, LNCS volume 5015, pp 127-141, Paris, France, May 2008.
    Also at the ISAIM-08 symposium.

  • Connections in Networks: A Hybrid Approach [pdf, bib, slides]
    Carla P. Gomes, Willem-Jan van Hoeve, Ashish Sabharwal
    CPAIOR-08. 5th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, LNCS volume 5015, pp 303-307, Paris, France, May 2008.

  • Filtering Atmost1 on Pairs of Set Variables [PDF, bib, journal version]
    Willem-Jan van Hoeve, Ashish Sabharwal
    CPAIOR-08. 5th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, LNCS volume 5015, pp 382-386, Paris, France, May 2008.
    Also at the ModRef-07 workshop.

   [2007]

  • Tradeoffs in the Complexity of Backdoor Detection [pdf, published, bib, with extended results at ISAIM-08, journal version]
    Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal
    CP-07. 13th International Conference on Principles and Practice of Constraint Programming, LNCS volume 4741, pp 256-270, Providence, RI, Sep 2007.

  • Survey Propagation Revisited [pdf (revised, see footnote 3), bib]
    Lukas Kroc, Ashish Sabharwal, Bart Selman
    UAI-07. 23rd Conference on Uncertainty in Artificial Intelligence, pp 217-226, Vancouver, BC, Canada, July 2007.
    Nominated for the UAI-07 Best Student Paper Award.

  • The Impact of Network Topology on Pure Nash Equilibria in Graphical Games [pdf, published, bib]
    Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal
    AAAI-07. 22nd Conference on Artificial Intelligence, pp 42-49, Vancouver, BC, Canada, July 2007.
    Also in NESCAI-07 (preliminary version)
    Nominated for the AAAI-07 Best Paper Award.

  • Counting CSP Solutions Using Generalized XOR Constraints [pdf, published, bib, slides]
    Carla P. Gomes, Willem-Jan van Hoeve, Ashish Sabharwal, Bart Selman
    AAAI-07. 22nd Conference on Artificial Intelligence, 204-209, Vancouver, BC, Canada, July 2007.

  • Short XORs for Model Counting: From Theory to Practice [pdf in color, pdf in black-and-white, published, slides, bib]
    Carla P. Gomes, Joerg Hoffmann, Ashish Sabharwal, Bart Selman
    SAT-07. 10th International Conference on Theory and Applications of Satisfiability Testing, LNCS volume 4501, pp 100-106, Lisbon, Portugal, May 2007. (short paper).

  • Connections in Networks: Hardness of Feasibility versus Optimality [pdf, published, slides, bib]
    Jon Conrad, Carla P. Gomes, Willem-Jan van Hoeve, Ashish Sabharwal, Jordan Suter
    CPAIOR-07. 4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, LNCS volume 4510, pp 16-28, Brussels, Belgium, May 2007.

  • [SampleCount paper] From Sampling to Model Counting [pdf, published, bib]
    Carla P. Gomes, Joerg Hoffmann, Ashish Sabharwal, Bart Selman
    IJCAI-07. 20th International Joint Conference on Artificial Intelligence, pp 2293-2299, Hyderabad, India, Jan 2007.
    Nominated for the IJCAI-07 Best Paper Award.

   [2006]

  • [XorSample paper] Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints [pdf with appendix, published, bib]
    Carla P. Gomes, Ashish Sabharwal, Bart Selman
    NIPS-06. 20th Annual Conference on Neural Information Processing Systems, pp 481-488, Vancouver, BC, Canada, Dec 2006.

  • Revisiting the Sequence Constraint [pdf, published, bib, journal version]
    Willem-Jan van Hoeve, Gilles Pesant, Louis-Martin Rousseau, Ashish Sabharwal
    CP-06. 12th International Conference on Principles and Practice of Constraint Programming, LNCS volume 4204, pp 620-634, Nantes, France, Sep 2006.
    Best Paper Award.

  • [Duaffle paper] QBF Modeling: Exploiting Player Symmetry for Simplicity and Efficiency [pdf, published, slides with the video used, bib]
    Ashish Sabharwal, Carlos Ansotegui, Carla P. Gomes, Justin W. Hart, Bart Selman
    SAT-06. 9th International Conference on Theory and Applications of Satisfiability Testing, LNCS volume 4121, pp 382-395, Seattle, WA, Aug 2006.

  • [MBound paper] Model Counting: A New Strategy for Obtaining Good Bounds [pdf, published, slides, bib]
    Carla P. Gomes, Ashish Sabharwal, Bart Selman
    AAAI-06. 21st National Conference on Artificial Intelligence, pp 54-61, Boston, MA, Jul 2006.
    Outstanding Paper Award (two awards out of nearly 800 submissions).

  • Friends or Foes? An AI Planning Perspective on Abstraction and Search [pdf, published, bib, journal version]
    Joerg Hoffmann, Ashish Sabharwal, Carmel Domshlak
    ICAPS-06. 16th International Conference on Automated Planning and Scheduling, pp 294-303, The English Lake District, UK, June 2006.
    Nominated for the ICAPS-06 Best Paper Award.

   [2005 and earlier]

  • [SymChaff paper #1] SymChaff: A Structure-Aware Satisfiability Solver [pdf, published, slides, bib, journal version]
    Ashish Sabharwal
    AAAI-05. 20th National Conference on Artificial Intelligence, pp 467-474, Pittsburgh, PA, July 2005.

  • Using Problem Structure for Efficient Clause Learning [pdf, published volume, slides, bib, journal version]
    Ashish Sabharwal, Paul Beame, Henry Kautz
    SAT-03. 6th International Conference on Theory and Applications of Satisfiability Testing, LNCS volume 2919, pp 242-256, Portofino, Italy, May 2003.

  • Understanding the Power of Clause Learning [pdf, published, slides, bib, journal version]
    Paul Beame, Henry Kautz, Ashish Sabharwal
    IJCAI-03. 18th International Joint Conference on Artificial Intelligence, pp 1194-1201, Acapulco, Mexico, August 2003.

  • Bounded-depth Frege Lower Bounds for Weaker Pigeonhole Principles [pdf, published, bib, journal version]
    Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal
    FOCS-02. 43rd Annual Symposium on Foundations of Computer Science, pp 583-592, Vancouver, BC, Nov 2002.

  • Resolution Complexity of Independent Sets in Random Graphs [pdf, published, bib, journal version]
    Paul Beame, Russell Impagliazzo, Ashish Sabharwal
    CCC-01. 16th Annual Conference on Computational Complexity, pp 52-68, Chicago, IL, June 2001.


JOURNAL ARTICLES

  • Bounds Consistency Filtering for Pair-Atmost1
    Willem-Jan van Hoeve, Ashish Sabharwal
    (in preparation)

  • Tradeoffs in the Complexity of Backdoors to Satisfiability: Dynamic Sub-Solvers and Learning During Search
    Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal
    (under review)

  • Wildlife Corridors as a Connected Subgraph Problem
    Jon Conrad, Carla P. Gomes, Willem-Jan van Hoeve, Ashish Sabharwal, Jordan F. Suter
    JEEM-2011. Journal of Environmental Economics and Management. To appear.
    Also as TechReport-2010. Incorporating Economic and Ecological Information into the Optimal Design of Wildlife Corridors. Cornell University Technical Report, Computing and Information Science series, http://hdl.handle.net/1813/17053, August 2010.

  • [BPCount and MiniCount paper #2] Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting [published, draft pdf]
    Lukas Kroc, Ashish Sabharwal, Bart Selman
    ANOR-2011. Annals of Operations Research, volume 184, number 1, pp 209-231, 2011.

  • Predicting direct protein interactions from affinity purification mass spectrometry data [published]
    Ethan Kim, Ashish Sabharwal, Adrian R. Vetta, Mathieu Blanchette
    ALMOB-2010. Algorithms for Molecular Biology, volume 5, number 34, October 2010.

  • Friends or Foes? On Planning as Satisfiability and Abstract CNF Encodings [pdf, published, bib]
    Carmel Domshlak, Joerg Hoffmann, Ashish Sabharwal
    JAIR-09. Journal of Artificial Intelligence Research, volume 36, pp 415-469, Dec 2009.

  • Towards Understanding and Harnessing the Potential of Clause Learning [pdf, published, bib]
    (see also chapter 4 of my Ph.D. thesis, in particular Corollary 4.2)
    Paul Beame, Henry Kautz, Ashish Sabharwal
    JAIR-04. Journal of Artificial Intelligence Research, volume 22, pp 319-351, Dec 2004.
    Runner-up for the IJCAI-JAIR 2003-2008 Best Paper Prize.

  • New Filtering Algorithms for Combinations of Among Constraints [published, draft pdf, bib]
    Willem-Jan van Hoeve, Gilles Pesant, Louis-Martin Rousseau, Ashish Sabharwal
    Constraints journal, volume 14, number 2, pp 273-292, June 2009.

  • [SymChaff paper #2] SymChaff: Exploiting Symmetry in a Structure-Aware Satisfiability Solver [draft pdf, published, bib]
    Ashish Sabharwal
    Constraints journal, special issue on Symmetry, volume 14, number 4, pp 478-505, Dec 2009.

  • The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs [pdf, published, bib]
    Paul Beame, Russell Impagliazzo, Ashish Sabharwal
    Computational Complexity journal, volume 16, number 3, pp 245-297, 2007.

  • Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles [pdf, published, bib]
    Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal
    SICOMP-04. SIAM Journal on Computing, volume 34, number 2, pp 261-276, Dec 2004.

  • Floodlight Illumination of Infinite Wedges [publisher, draft pdf, bib]
    Matthew Cary, Atri Rudra, Ashish Sabharwal, Erik Vee
    COMGEO-10. Special issue of the journal Computation Geometry: Theory and Applications, volume 43, number 1, pp 23-34, Jan 2010.
    Abstract in the 14th Annual Fall Workshop on Computational Geometry, Boston, MA, Nov 2004.
    Preliminary version: Technical Report UW-CSE-2004-10-04, University of Washington, Seattle, Oct 2004.


WORKSHOPS,  INVITED TALKS,  OTHER WORK

  • General Nogood-Learning Framework for Pseudo-Boolean Multi-Valued SAT (extended abstract) [pdf, slides]
    Siddhartha Jain, Ashish Sabharwal, Meinolf Sellmann
    CSPSAT-2011 at SAT-2011. 1st International Workshop on the Cross-Fertilization Between CSP and SAT, Ann Arbor, MI, June 2011.

  • Guiding Combinatorial Optimization with UCT [pdf]
    Ashish Sabharwal, Horst Samulowitz
    MCTS-2011. ICAPS 2011 Workshop on Monte-Carlo Tree Search: Theory and Applications, Freiburg, Germany, June 2011.

  • On the Behavior of UCT in Synthetic Search Spaces
    Raghuram Ramanujan, Ashish Sabharwal, Bart Selman
    MCTS-2011. ICAPS 2011 Workshop on Monte-Carlo Tree Search: Theory and Applications, Freiburg, Germany, June 2011.

  • A flat histogram method for inference with probabilistic and deterministic constraints
    Stefano Ermon, Carla Gomes, Ashish Sabharwal, Bart Selman
    DISCML-2010. NIPS 2010 Workshop on Discrete Optimization in Machine Learning: Structures, Algorithms and Applications, Whistler, BC, Canada, Dec 2010.

  • Bridging Constraint Reasoning and Machine Learning for Unsupervised Labeling and Decomposition
    Ronan LeBras, Theodoros Damoulas, John M. Gregoire, Ashish Sabharwal (presenting author), Carla P. Gomes, R. Bruce van Dover
    INFORMS-2010. INFORMS Annual Meeting, Austin, TX, Nov 2010.

  • Backdoors in the Context of Combinatorial Optimization and Learning
    Bistra Dilkina, Carla P. Gomes, Yuri Malitsky, Ashish Sabharwal (presenting author), Meinolf Sellmann
    INFORMS-2010. INFORMS Annual Meeting, Austin, TX, Nov 2010.

  • Game Playing Techniques for Optimization Under Uncertainty
    Kiyan Ahmadizadeh, Carla P. Gomes, Ashish Sabharwal
    CROCS at CP-10. Third International Workshop on Constraint Reasoning and Optimization for Computational Sustainability, St Andrews, Scotland, Sep 2010.

  • Computational Thinking for Material Discovery: Bridging Constraint Reasoning and Learning
    Ronan LeBras, Theodoros Damoulas, John M. Gregoire, Ashish Sabharwal, Carla P. Gomes, R. Bruce van Dover
    CROCS at CPAIOR-10. Second International Workshop on Constraint Reasoning and Optimization for Computational Sustainability (in conjunction with CPAIOR-10 conference), Bologna, Italy, June 2010.

  • Optimal Network Design for the Spread of Cascades
    Daniel Sheldon, Bistra Dilkina, Adam Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad,Carla Gomes, David Shmoys, Will Allen, Ole Amundsen, William Vaughan
    CROCS at CPAIOR-10. Second International Workshop on Constraint Reasoning and Optimization for Computational Sustainability (in conjunction with CPAIOR-10 conference), Bologna, Italy, June 2010.

  • Approximate Inference for Clusters in Solution Spaces [pdf]
    Lukas Kroc, Ashish Sabharwal, Bart Selman
    WARA-2010. AAAI-10 Workshop on Abstraction, Reformulation, and Approximation, Atlanta, GA, Jul 2010.

  • Connections in Networks: A Hybrid Approach
    Carla P. Gomes, Willem-Jan van Hoeve (presenter), Ashish Sabharwal
    INFORMS-09. INFORMS Annual Meeting, San Diego, CA, Oct 2009.

  • Optimizing Fish Passage Barrier Removal Using Mixed Integer Linear Programming [slides]
    Carla P. Gomes, Ashish Sabharwal
    CROCS-09. First International Workshop on Constraint Reasoning and Optimization for Computational Sustainability (in conjunction with CP-09 Conference), Lisbon, Portugal, Sep 2009.

  • Integrating Systematic and Local Search Paradigms: A New Strategy for MaxSAT
    Lukas Kroc, Ashish Sabharwal, Carla P. Gomes, Bart Selman
    SoCS-09. The 2009 International Symposium on Combinatorial Search, Lake Arrowhead, CA, July 2009.

  • Backdoors in the Context of Learning
    Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal (presenter)
    CORS-INFORMS-09. CORS-INFORMS International Meeting, Toronto, ON, Canada, June 2009.

  • Integrating Systematic and Local Search Paradigms: A New Strategy for MaxSAT
    Lukas Kroc, Ashish Sabharwal (presenter), Carla P. Gomes, Bart Selman
    CORS-INFORMS-09. CORS-INFORMS International Meeting, Toronto, ON, Canada, June 2009.

  • Domain Filtering for the Intersection of Set Variables
    Willem-Jan van Hoeve (presenter), Ashish Sabharwal
    EURO-09. 23rd European Conference on Operational Research, Bonn, Germany, Jul 2009.

  • Solution Counting Methods for Combinatorial Problems [slides]
    Carla P. Gomes, Willem-Jan van Hoeve, Lukas Kroc, Ashish Sabharwal (presenter), Bart Selman
    INFORMS-08. INFORMS Annual Meeting, Washington, DC, Oct 2008.

  • Hidden Structure in Constraint Reasoning Problems [slides]
    Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal (presenter)
    INFORMS-08. INFORMS Annual Meeting, Washington, DC, Oct 2008.

  • Counting CSP Solutions Using Generalized XOR Constraints
    Carla P. Gomes, Willem-Jan van Hoeve (presenter), Ashish Sabharwal, Bart Selman
    INFORMS-08. INFORMS Annual Meeting, Washington, DC, Oct 2008.

  • Optimal Corridor Design for Grizzly Bear in the U.S. Northern Rockies
    Jordan F. Suter (presenter), Jon Conrad, Carla P. Gomes, Willem-Jan van Hoeve, Ashish Sabharwal
    AAEA-08. American Agricultural Economics Association Annual Meeting, Orlando, FL, Jul 2008.

  • Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting [pdf, bib]
    Lukas Kroc (presenter), Ashish Sabharwal, and Bart Selman
    ISAIM-08. 10th International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, FL, Jan 2008.

  • Tradeoffs in Backdoors: Inconsistency Detection, Dynamic Simplification, and Preprocessing [pdf, bib, slides]
    Bistra Dilkina, Carla Gomes, Ashish Sabharwal (presenter)
    ISAIM-08. 10th International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, FL, Jan 2008.

  • Hidden Structure in Combinatorial Problems [Please refer to slides for the ISAIM-08 paper on Backdoors]
    Carla P. Gomes, Ashish Sabharwal (presenter)
    INFORMS-07. INFORMS Annual Meeting, Seattle, WA, Nov 2007.

  • Filtering Algorithms for the Sequence Constraint
    Willem-Jan van Hoeve (presenter), Gilles Pesant, Louis-Martin Rousseau, Ashish Sabharwal
    INFORMS-07. INFORMS Annual Meeting, Seattle, WA, Nov 2007.

  • Two Set Constraints for Modeling and Efficiency [pdf, bib, slides]
    Willem-Jan van Hoeve, Ashish Sabharwal (presenter)
    ModRef-07 at CP-07. 6th International Workshop on Constraint Modelling and Reformulation, Providence, RI, Sep 2007. In conjunction with the CP-07 conference.

  • Sampling and Soundness: Can We Have Both?
    Carla P. Gomes, Joerg Hoffmann, Ashish Sabharwal, Bart Selman
    ISWC-07. 6th International Semantic Web Conference, Busan, Korea, Nov 2007.

  • Empirical Validation of the Relationship Between Survey Propagation and Covers in Random 3-SAT [slides]
    Lukas Kroc (presenter), Ashish Sabharwal, Bart Selman
    AISP-07. Workshop on Algorithms, Inference, & Statistical Physics, Santa Fe, NM, May 2007.

  • Sparse Message Passing Algorithms for Weighted Maximum Satisfiability [pdf]
    Aron Culotta, Andrew McCallum, Bart Selman, Ashish Sabharwal
    NESCAI-07. 2nd North East Student Colloquium on Artificial Intelligence, Ithaca, NY, Apr 2007.

  • Streamlining Reasoning for Solution Finding and Counting
    Carla P. Gomes (presenter), Ashish Sabharwal, Meinolf Sellmann, Bart Selman
    INFORMS-06. INFORMS Annual Meeting, Pittsburgh, PA, Nov 2006.


  • Algorithmic Applications of Propositional Proof Complexity [bib]
    PH.D. THESIS, University of Washington, Seattle, 2005
    Advisors: Profs. Paul Beame and Henry Kautz

            [ abstract, full pdf (single spaced, 1.3MB) ]
            [ chapters, single-spaced: titlepage, abstract, contents, ch1, ch2, ch3, ch4, ch5, ch6, ch7 ]

  • Model Checking: Two Decades of Novel Techniques and Trends [pdf]
    General Examination Report, University of Washington, Seattle, May 2002.

Disclaimer: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.


Teaching

TUTORIALS

  • Satisfied by Message Passing: Probabilistic Techniques for Combinatorial Problems [webpage, bib]
    Lukas Kroc, Ashish Sabharwal, Bart Selman
    AAAI-08. 23rd Conference on Artificial Intelligence, Tutorial Forum, Chicago, IL, July 2008.
    Shorter version also at: LION 3, 2009. 3rd Conference on Learning and Intelligent Optimization, Tutorial Forum, Trento, Italy, Jan 2009.

  • Combinatorial Problems (series of three lectures)
    1. Finding Solutions [slides]
    2. Counting and Sampling Solutions [slides]
    3. The Next Level of Complexity [slides with the video used]

    Ashish Sabharwal, Bart Selman
    KITPC-08. 2nd Asian-Pacific School on Statistical Physics and Interdisciplinary Applications, Collective Dynamics and Information Systems Program, Kavli Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing, China, March 2008

  • Beyond Traditional SAT Reasoning: QBF, Model Counting, and Solution Sampling [webpage, bib]
    Ashish Sabharwal, Bart Selman
    AAAI-07. 22nd Conference on Artificial Intelligence, Tutorial Forum, Vancouver, BC, Canada, July 2007

  • Quantified Boolean Formula (QBF) Reasoning [slides with videos used]
    Bart Selman, Carla Gomes, Ashish Sabharwal
    Tutorial prepared for DARPA, Feb 2007


COURSE MATERIAL

  • For the course webpage for CSE 326, Data Structures, that I taught as a pre-doctoral instructor in Fall 2003 at the University of Washington, please click here.

  • Notes on Proof Complexity [pdf]
    Lectures by Paul Beame, scribed by Ashish Sabharwal.
    IAS/PCMI Summer School, Princeton, NJ, Aug 2000.


My Other Interests

Piano
Although piano playing has been on hold for the past many years now, six quarters of piano lessons at the University of Washington greatly increased the appreciation I have for (Western) classical music, performers, and composers. Being mathematically oriented, I found it relatively easy to theoretically digest the concepts of scales, transposition, quarter notes, etc., but bringing it all tegether and training one's mind and body to play even a single note perfectly is an art that will take several years. Luckily for me, my piano teacher knew the secrets!

Martial Arts
I started practicing Shotokan karate with SKA in January 2000. I became a shodan (first degree black belt) in June 2004. The picture on the right is from my first tournament as a white belt. After moving to Cornell University, I haven't had much opportunity to practice karate with an SKA-affiliated dojo. Instead, I have explored aikido with the Cornell Aikido Club. 		       
Hiking, Mountaineering, and Rock Climbing
The Pacific Northwest is undoubtedly one of the best places to hike. Some of my mountain climbs and scrambles include Mount Hood (Oregon), Mount Daniel (Cascades), The Brothers (Olympics), Colchuck Peak (Alpine Lakes area), Mount Rainier [unsuccessful], and Mount Adams. I have also begun to explore areas in the central New York region. Indoor rock climbing is another related challenge I enjoy.
Skiing
My favorite ski place near Seattle is Crystal Mountain, but of all the mountains I have skied down, the best is Whistler-Blackcomb in British Columbia, Canada. The wind can be trecherous, but nothing compares to the powdery snow, the beauty, and the challenges of Whistler. The picture here is of me looking at the Roundhouse lodge half way up Whistler mountain. Recently, I have also begun to explore (not-so-exciting) skiing opportunities in the New York region, with my Head Monster iM77 skis with a built-in 'intelligent chip'.
Motorcycle Riding
I enjoyed riding a beautiful motorcycle that I bought in 2001 and sold off after four years --- a 1997 Kawasaki Ninja 600R (600 cc). Hours working on it and tuning it for a smooth ride were certainly well spent. In the summer of 2004, I was on the road for a memorable trip with my girlfriend to the Columbia River Gorge, on Highways 7/25/30S, 30/I-84E, 97N, 410W... splendid views, scenary changing from thick forests to open dry lands, and close encounters of the four big mountains in the area: St. Helens, Hood, Adams, and Rainier!