Yliopiston etusivulle Suomeksi På svenska In English
Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Department of Computer Science

Research Seminar on Algorithms: Sums of Products (2 cu)

Organizer: Mikko Koivisto
Time (tentative): Fall 2005
Place (tentative): Exactum

To whom: Students in the specialization areas of (1) Algorithms and (2) Intelligent Systems.

Overview

If you combine two operations, e.g., the artihmetic + and * or the logical AND and OR, you may end up with powerful expressions. Indeed, many theoretically and practically important computational problems are large-dimensional "summations" over a "product" of lower-dimensional functions. For example, various forms of satisfiability, constraint satisfaction, and Bayesian inference problems are, in essence, this type of sum-product problems. Recognizing the unifying problem structure allows adaptation of algorithmic ideas that have been developed for seemingly different problems. The algorithms often exploit the distributive law

a * b + a * c = a * (b + c) ,

but there are also other techniques...

In this seminar, we study related basic concepts as well as recent advances. While providing an overview of the research area, the seminar also aims at identifying potential research topics.

Format and participation

From a given list of articles, each participant selects one or more papers about which she/he gives an oral presentation (45 to 60 minutes.) Alternatively, a participant may suggest a topic of her/his own. Each participant will also act as an opponent for one presentation by another participant. The opponent prepares comments and questions based on the associated article(s) (offline) and the oral presentation (online). After the opponent has made her/his comments, the rest of the seminar audience may join in the discussion that will follow.

  • Weekly seminar sessions (1 to 2 presentations).
  • 2 credit units.
  • Prerequisites: basics in algebra, in design and analysis of algorithms, and in probability calculus.

Tentative schedule

Week 39: An introduction to sums of products (Mikko Koivisto)
Week 40: Deadline for choosing an article, or two, and date for oral presentation (no seminar session)
Week 41: Final schedule will be announced (no seminar session)
Week 42: First presentation(s)
...
Week 50: Last presentation(s)

Tentative list of articles

  1. S. M. Aji and R. McEliece: The Generalized Distributive Law. IEEE Trans. Inform. Theory, vol. 46, no. 2 (March 2000), pp. 325-343.
  2. David Allen and Adnan Darwiche: New advances in inference by recursive conditioning. UAI'03.
  3. David Allen and Adnan Darwiche: Optimal time-space tradeoff in probabilistic inference. IJCAI'03.
  4. Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi: Algorithms and Complexity Results for #SAT and Bayesian Inference. FOCS'03.
  5. Pedro F. Felzenszwalb, Daniel P. Huttenlocher, Jon M. Kleinberg: Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis. NIPS 2003.
  6. E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schöning: A Deterministic (2-2/(k+1))^n Algorithm for k-SAT Based on Local Search. Theoretical Computer Science 289/1, 2002, pp. 69-83.
  7. E. Dantsin, E. A. Hirsch, A. Wolpert: Algorithms for SAT based on search in Hamming balls. STACS 2004, volume 2996 of Lecture Notes in Computer Science, pages 141-151. Springer, March 2004.
  8. A. Darwiche: Recursive Conditioning. Artificial Intelligence. Vol 125, No 1-2, pages 5-41, 2001.
  9. Rina Dechter: Bucket Elimination: A Unifying Framework for Reasoning. Artif. Intell. 113(1-2): 41-85 (1999)
  10. Rina Dechter, Irina Rish: Mini-buckets: A general scheme for bounded inference. J. ACM 50(2): 107-153 (2003)
  11. F. R. Kschischang, B. J. Frey and H.-A. Loeliger 2001. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory 47:2, February, 498-519.
  12. Payam Pakzad and Venkat Anantharam: A New Look at the Generalized Distributive Law. Submitted for publication to the IEEE Transactions on Information Theory.
  13. Irina Rish, Rina Dechter: Resolution versus Search: Two Strategies for SAT. J. Autom. Reasoning 24(1/2): 225-275 (2000)
  14. Richard Edwin Stearns, Harry B. Hunt III: An Algebraic Model for Combinatorial Problems. SIAM J. Comput. 25(2): 448-476 (1996) [available from the library]
  15. Richard Edwin Stearns, Harry B. Hunt III: Exploiting structure in quantified formulas. J. Algorithms 43(2): 220-263 (2002)
  16. Richard Edwin Stearns: Deterministic versus nondeterministic time and lower bound problems. J. ACM 50(1): 91-95 (2003)
  17. Jiri Vomlel: Exploiting functional dependence in Bayesian network inference. UAI'02.
mikko.koivisto(at)cs.helsinki.fi
Last updated March 24, 2005.

Feedback | Faculty homepage | University homepage