Eric I. Hsu

Department of Computer Science
University of Toronto

 my picture Sandford Fleming Building
10 King's College Road
Room 3305
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.

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...
  • "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)

    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)


  • "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)