Eric I. Hsu

Department of Computer Science
University of Toronto

my picture Sandford Fleming Building
6 King's College Road
Room 386
Toronto, ON M5S 3G4

Phone: 416 946 8440
Fax: 416 978 1455
(email address as image; it's eihsu.)


I am a Ph.D. student researching Artificial Intelligence under Sheila McIlraith's supervision. My interests involve combining continuous (i.e. statistical) techniques with discrete (i.e. logical) ones. Typically this involves finding the hidden structure in otherwise complex problems.

IJCAI Tutorial on integrating probabilistic reasoning and constraint satisfaction: Sunday Afternoon, July 17.

VARSAT homepage contains derivations and preliminary results for a SAT-solving system that exploits probabilistic inference techniques for heuristic guidance.

Old web page at KSL, includes links to a couple of workshop papers, and to yet another old page, at SRI.

More to come soon...


  • "Computing Equivalent Transformations for Combinatorial Optimization by Branch-and-Bound Search"

    Eric I. Hsu and Sheila A. McIlraith

    SoCS 2010

    Presents "Minimum-Height Equivalent Transformation" process for shifting fractional weights between constraint extensions within a (MaxSAT) constraint optimization problem. Result is an equivalent problem that induces a tighter lower bound during branch-and-bound search, when using a specific height-based bounding technique.

    Paper: (.pdf)
    Poster Describing Project: (.pdf)

    BibTeX: (.bib)

  • "VARSAT: Integrating Probabilistic Inference with DPLL Search"

    Eric I. Hsu and Sheila A. McIlraith

    SAT 2009

    Presents four novel message-passing techniques for approximating marginal probabilities over Boolean satisfiability problems. Introduces a complete backtracking (DPLL) solver that exploits such techniques to guide its search process.

    Paper: (.pdf)
    Presentation: (.pdf)

    BibTeX: (.bib)


  • "Probabilistically Estimating Backbones and Variable Bias"

    Eric I. Hsu, Christian J. Muise, J. Christopher Beck, and Sheila A. McIlraith

    CP 2008 (shorter version)
    STAIR 2008, Technical Report CSRG-577 (longer versions)

    Examines the concept variable bias, or the percentage of solutions where a given variable holds a particular value. First measures the ability of various probabilistic techniques to estimate bias in isolation. Secondly, studies effective ways to embed bias estimators within a full-featured DPLL SAT-solver, thus assessing the importance of bias to heuristic search.

    Shorter Paper: (.pdf)

    Longer Paper: (.pdf)

    Technical Report (Longest): (.pdf)
    Poster Describing Project: (.pdf)

    BibTeX: (.bib)

    Online Appendix presents detailed experimental results and derivations.


  • "Using EM to Find Likely Assignments for Solving Constraint Satisfaction Problems"

    Eric I. Hsu, Matthew Kitching, Fahiem Bacchus, and Sheila A. McIlraith

    AAAI 2007 (shorter, revised version)
    NESCAI 2007 (longer, preliminary version)

    Derives a variable and value ordering heuristic for solving constraint satisfaction problems, using the Expecation Maximization (EM) framework. Focuses on the "Quasigroup with Holes" combinatorial problem, whose heavy-tailed empirical behavior is especially sensitive to such ordering heuristics. Characterizes the operation of EM as probabilistic local search alternating over the primal and dual versions of a problem.

    Shorter Paper: (.pdf)
    Shorter Presentation: (.pdf)

    Longer Paper: (.pdf)
    Longer Presentation: (.pdf)

    BibTeX: (.bib)


  • "Characterizing Propagation Methods for Boolean Satisfiabilty"

    Eric I. Hsu and Sheila A. McIlraith

    SAT 2006

    Presents Survey Propagation (SP) in standard Computer Science terms, exhibiting connections to Belief Propagation (BP), local search, and backbones/backdoors. Re-derives BP/SP within the Expectation Maximization (EM) statistical framework, resulting in a new version that always converges. More generally, suggests the grouping of a variety of artificial intelligence, constraint programming, and logical reasoning techniques within a single class of primal/dual discrete optimization methods.

    Paper: (.pdf)
    Presentation: (.pdf)

    BibTeX: (.bib)