Held weekly, Wednesdays 16:00-17:00 CICSR/CS 153 (BETA-Lab).
This reading group focuses on the empirical analysis of algorithms for hard combinatorial problems. Much of our previous discussion has revolved around Stochastic Local Search (SLS) algorithms for Propositional Satisfiability (SAT) and MaxSAT - however this term we are expanding the discussion to include topics such as Experiment Design as well as other problems such as Travelling Salesman Problem (TSP) and hard problems on graphs. As always, new topics and faces are always welcome.
The general format of the meetings will be introductions, if necessary, followed by research updates and then an interactive paper discussion.
Upcoming paper discussions
| Date | Time | Presenter | Paper / Topic / Title |
|---|---|---|---|
| Aug 18, 2004 | 16:00-17:00 | TBA | Understanding Random SAT: Beyond the Clauses-to-Variables Ratio. Nudelman, Leyton-Brown, Devkar, Shoham, Hoos. To be presented at the Tenth International Conference on Principles and Practice of Constraint Programming (CP-04) [pdf] |
| TBA | TBA | Baharak Rastegari | TBA |
| TBA | TBA | Mohammad Safari | TBA |
Previous paper discussions
| Date | Time | Presenter | Paper / Topic / Title |
|---|---|---|---|
| Aug 11, 2004 | 16:00-17:00 | Dave Tompkins | Understanding Random SAT: Beyond the Clauses-to-Variables
Ratio. Nudelman, Devkar, Shoham, Leyton-Brown. Submitted to Tenth
International Conference on Principles and Practice of Constraint Programming
(CP-04). [pdf] There final copy of this paper is available here: [pdf] |
| Aug 4, 2004 | 16:00-17:00 | Kevin Smyth | Ling Zhao and Martin Mueller: Game-SAT: A Preliminary Report. SAT-04 [pdf] |
| July 19, 2004 | 16:00-17:00 | Dave Tompkins | H. Fang and W. Ruml: Complete Local Search for Propositional Satisfiability. AAAI'04 [pdf] |
| May 5, 2004 | 16:00-17:00 | Alena Shmygelska | Travelling Salesperson Problem (TSP). Reading material:
|
| Mar 29, 2004 | 15:30-16:30 | Kevin Leyton-Brown | Empirical Hardness Models
Reading: Chapters 9&10 of KLB's Ph.D. Thesis (part 2) |
| Mar 15, 2004 | 15:30-16:30 | Kevin Leyton-Brown | Empirical Hardness Models
Reading: Chapters 9&10 of KLB's Ph.D. Thesis (part 1) |
| Mar 8, 2004 | 15:30-16:30 | Holger Hoos | Introduction to Empirical Algorithmics (part 2) |
| Mar 1, 2004 | 15:30-16:30 | Holger Hoos | Introduction to Empirical Algorithmics (part 1) |
| Feb 9 & 23, 2004 | 15:30-16:30 | Kevin Smyth | General introduction to research done in the department in the area of Search Space Analysis of SAT instances and algorithms. Reading material available by email. |
| Feb 2, 2004 | 15:30-16:30 | Dave Tompkins | General introduction to the Propositional Satisfiability (SAT) problem, and algorithms to solve it. Please contact Dave Tompkins for the reading. |
| Nov 12, 2003 | 16:30-17:30 | Dave Tompkins | Alfonso San Miguel Aguirre and Moshe Y. Vardi: Random 3-SAT and BDDs: The Plot Thickens Further. [pdf] |
| Nov 05, 2003 | 16:30-17:30 | Kevin Smyth | Charles Sauerbier: A polynomial time (heuristic) SAT algorithm. [pdf] |
| October 22, 2003 | 16:30-17:30 | Dave Tompkins | Pascal Van Hentenryck and Laurent Michel: Control Abstractions for Local Search. [pdf] |
| October 15, 2003 | 16:30-17:30 | Kevin Smyth | Corfa et al. Random 3-SAT: The Plot Thickens. [pdf] |
| April 22, 2003 | 15:30-16:30 | Kevin Smyth | O. Kullman. Towards an adaptive density based branching rule for {SAT} solvers, using a database for mixed random conjunctive normal forms built upon the Advanced Encryption Standard ({AES}). SAT 2002 190-200, 2002. [pdf] |
| April 1, 2003 | 15:30-16:30 | Dave Tompkins | E. Dantsin, M. Gavrilovich, and E. Hirsch. Approximation algorithms for MaxSAT: a better performance ratio at the cost of a longer running time. Technical Report PDMI preprint 14/1998, Steklov Institute of Mathematics at St. Petersburg, 1998. [pdf] |
| March 4, 2003 | 15:30-16:30 | Kevin Smyth | Uwe Schoening. A Probabilistic Algorithm for k-SAT and CSPs.
[pdf]
Also of interest: Schuler et al. An Improved Randomized Algorithm for 3-SAT. [pdf] Paturi et al. Satisfiability Coding Lemma. [pdf] Paturi et al. An Improved Randomized Algorithm for k-SAT. [pdf] |
| Februray 4 & 25, 2003 | 15:30-16:30 | Kevin Smyth | E. Hirsch and A. Kojevnikov. UnitWalk: A new SAT solver that uses local search guided by unit clause elimination. SAT 2002 35-42, 2002. [pdf] |
| January 28, 2003 | 15:30-16:30 | Dave Tompkins | S. Kirkpatrick, C. Gelattm, and M. Vecchi. Optimization by simulated annealing. Science 1983. [pdf] |
| TBA | TBA | TBA | S. Prestwich. Local Search and Backtracking vs Non-Systematic Backtracking. AAAI 2001. [pdf] |
| December 11, 2002 | 14:10-15:10 | Dave Tompkins | Articles from Science (see below) |
| November 27, 2002 | 14:10-15:10 | Janek Klawe | Moskewicz et. al. Chaff: Engineering an Efficient SAT Solver. DAC2001. [pdf] |
| November 13, 2002 | 14:10-15:10 | Kevin Smyth | W. Wei and B. Selman. Accelerating Random Walks. CP2002. [pdf] |
| November 6, 2002 | 14:10-15:10 | Dave Tompkins | Chen, Gomes, and Selman. Formal Models of Heavy-Tailed Behavior in Combinatorial Search. CP 2001. |
| October 30, 2002 | 14:10-15:10 | Kevin Smyth | E. Goldberg. Testing satisfiability of CNF formulas by computing a stable set of points |
| October 23, 2002 | 14:10-15:10 | Holger Hoos | P. Hansen and B. Jaumard. Algorithms for the maximum satisability problem |