Held weekly on Wednesday at 13:30 in room X530 (seminar room by the beta lab)
We have weekly research meetings of people working on automated algorithm design/configuration/selection right after the talk. In some weeks, we don't have a talk but only the research meeting.
This reading group focuses on empirical aspects of computer science. Every computer science student takes a lot of math and theory courses, but typically not even a single course about the design of meaningful experiments and the analysis of their results. In this group, we discuss research papers with a focus on empirical issues; the papers typically concern solving hard computational problems (SAT, TSP, scheduling, etc) and computer aided algorithm design.
Since this is a joint BETA/LCI reading group we often discuss AI papers, but we are open to other areas and also have a theoretician amongst us. Our meeting format is presentations with lots of audience interaction, so you can come without having read the paper (though you may get more out of it if you read it).
If you are planning to attend our meetings, you should sign up to the mailing list (earg), where the papers and schedules will be announced: just send an email to majordomo@cs.ubc.ca with the command "subscribe earg" in the body of your message.
Upcoming presentations
Date  Time  Presenter  General Topic  Paper / Title 

April 2, 2014  13:30  14:30  Steve Ramage  TBD  TBD 
Previous presentations
Date  Time  Presenter  General Topic  Paper / Title 

March 26, 2014  14:30  15:30  Alex Fréchette  Bandits 
Continued: Sébastien Bubeck, Rémi Munos, Gilles Stoltz, Csaba Szepesvári XArmed Bandits (continued) 
March 5, 2014  13:00  14:00  Alex Fréchette  Bandits 
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, Csaba Szepesvári XArmed Bandits 
February 12, 2014  13:00  14:00  Sam Bayless  SAT instance generation 
Sam Bayless, Dave A.D. Tompkins, Holger H. Hoos Evaluating Instance Generators by Configuration 
January 29, 2014  13:00  14:00  Chris Fawcett  Parallel SAT 
Alejandro Arbelaez, Charlotte Truchet, Philippe Codognet
Using sequential runtime distributions for the parallel speedup prediction of SAT local search 
November 6, 2013  13:0014:00  Manuel LópezIbáñez  Grammarbased algorithm design  From grammars to parameters: How to use irace to design algorithms from a grammar description 
October 29, 2013  15:4516:45  Chris Thornton  MSc. thesis presentation  AutoWEKA: Combined Selection and Hyperparameter Optimization of Supervised Machine Learning Algorithms 
October 9, 2013  12:3013:30  Sam Bayless  SAT 
Sam Bayless, Celina G. Val, Thomas Bally, Holger H. Hoos, and Alan J. Hu
Efficient Modular SAT Solving for IC3 
September 11, 2013  12:3013:30  Sam Bayless  Parallel SAT 
Martin Aigner, Armin Biere, Christoph M. Kirsch, Aina Niemetz, and Mathias Preiner
Analysis of PortfolioStyle Parallel SAT Solving on Current MultiCore Architectures. 
July 22, 2013  12:0013:00  Steve Ramage  ACLib  An introduction to ACLib 
June 5, 2013  12:3013:30  Steve Ramage  Algorithm configuration 
Aldy Gunawan, Hoong Chuin Lau, Lindawati
FineTuning Algorithm Parameters Using the Design of Experiments Approach. 
April 3, 2013  12:3013:30  Chris Fawcett  Algorithm Parameter Importance  Informal presentation of Ablation Analysis paper submitted to MIC 2013 
March 13, 2013  12:3013:30  Frank Hutter  Algorithm Parameter Importance  Last presentation before leaving UBC, covering functional ANOVA for parameter importance 
February 27, 2013  12:3013:30  Sam Bayless  Incremental SAT Solving  
February 21, 2013  12:3013:30  Alex Fréchette  Algorithm portfolios 
Mladen Nikolić, Filip Marić, and Predrag Janičić
Simple algorithm portfolio for SAT. 
February 6, 2013  12:3013:30  Chris Thornton  Hyperparameter optimization 
Jasper Snoek, Hugo Larochelle, and Ryan P. Adams
Practical Bayesian Optimization of Machine Learning Algorithms. 
December 5, 2012  12:3013:30  Quinn Hsu  HAL  The future of scripting support in HAL 
November 28, 2012  12:3013:30  Lin Xu  Empirical analysis 
Simon F. Goldsmith, Alex S. Aiken, and Daniel S. Wilkerson
Measuring Empirical Computational Complexity. 
November 21, 2012  12:3013:30  Chris Thornton  Matching 
Laurent Charlin, Richard S. Zemel, Craig Boutilier
A Framework for Optimizing Paper Matching. 
November 14, 2012  12:3013:30  Chris Fawcett  Algorithm portfolios 
Jendrik Seipp, Manuel Braun, Johannes Garimort, and Malte Helmert
ICAPS 2012: Learning Portfolios of Automatically Tuned Planners. 
November 7, 2012  12:3013:30  Alex Fréchette  Algorithm portfolios 
Holger Hoos, Kevin LeytonBrown, Torsten Schaub, and Marius Schneider
CoCoMile 2012: Algorithm Conﬁguration for Portfoliobased Parallel SATSolving. 
October 24, 2012  12:3013:30  Sam Bayless  SAT solving 
Laurent Simon and Gilles Audemard
IJCAI09: Predicting Learnt Clauses Quality in Modern SAT Solvers. 
October 3, 2012  12:3013:30  Lin Xu  Algorithm selection 
Serdar Kadioglu, Yuri Malitsky, and Meinolf Sellmann. AAAI12: NonModelBased Search Guidance for Set Partitioning Problems. 
September 26, 2012  12:3013:30  Alexandre Fréchette  Robust network design  Presentation of M.Sc. work. 
September 19, 2012  12:3013:30  Nick Harvey  Submodularity  Submodular Functions: Learnability, Structure, and Optimization 
August 22, 2012  12:3013:30  Torsten Schaub  Answerset programming 
Martin Gebser, Benjamin Kaufmann, and Torsten Schaub. Multithreaded ASP Solving with clasp 
August 15, 2012  12:3013:30  Lin Xu  Algorithm selection; Portfolio construction  Practice talk: MIP and evaluating candidate solvers 
August 8, 2012  12:3013:30  Lin Xu  SAT solving 
Shaowei Cai and Kaile Su. AAAI12: Configuration Checking with Aspiration in Local Search for SAT. 
August 1, 2012  12:3013:30  Sam Bayless  Deltadebugging  Modelbased delta debugging 
July 25, 2012  12:3013:30  Quinn Hsu  HAL  Demo of the 1.1.0 release candidate 
July 11, 2012  12:3013:30  Frank Hutter  Bias/variance tradeoffs 
Trevor Hastie, Robert Tibshirani, Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Chapter 7, continued. 
June 20, 2012  12:3013:30  Frank Hutter  Bias/variance tradeoffs 
Trevor Hastie, Robert Tibshirani, Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Chapter 7. 
May 16, 2012  12:3013:30  Chris Thornton  Hyperparameter optimization 
James Bergstra, Rémi Bardenet, Yoshua Bengio, Balázs Kégl. NIPS11: Algorithms for HyperParameter Optimization. 
April 25, 2012  12:3013:30  Lin Xu  Algorithm selection  Continuation of 3S. 
April 11, 2012  12:3013:30  Lin Xu  Algorithm Selection  Informal discussion about 3S 
March 28, 2012  12:3013:30  Chris Fawcett  Empirical distributions  Sampling from multivariate empirical distributions 
March 21, 2012  12:3013:30  Chris Thornton  Hyperparameter optimization 
James Bergstra and Yoshua Bengio. JMLR: Random Search for HyperParameter Optimization. 
March 14, 2012  12:3013:30  Roman from Westgrid  Cluster allocation and scheduling issues  
Feb 29, 2012  12:3013:30  Sam  SAT submission #2  
Feb 22, 2012  12:3013:30  Chris F  
Feb 15, 2012  12:3013:30  Everyone  Adding papers and topics to the queue.  
Feb 8, 2012  12:3013:30  Chris T  
Feb 1, 2012  12:3013:30  Lin  Runtime prediction  Ling Huang, Jinzhu Jia, Bin Yu, ByungGon Chun, Petros
Maniatis, Mayur Naik. NIPS 2010: Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression 
Jan 11, 2012  12:3013:30  James  Algorithm configuration  James Styles, Holger Hoos, Martin Mueller. LION 2012: Automatically Configuring Algorithms for Scaling Performance 
Jan 4, 2012  12:3013:30  Martin Brain  Automated Music Composition  Title : Computational Music Theory Abstract : Most automated composition systems use machine learning techniques to produce a pastiche of their training set. This talk presents Anton, an automatic composition system that uses an alternative approach. Knowledge representation technology is used to express music theory in a declarative logic programming language. Techniques similar to constraint and SAT solving can be used to compose novel pieces of melodic, harmonic and rhythmic music in the modelled style. No prior knowledge of music, music theory or answer set programming is be required and there will be demos and music. About the speaker : Martin Brain is a postdoc researcher working jointly with University of Bath and AltranPraxis Limited. Current projects include developing an algebra of search spaces, building program verification tools and trying to untangle the mess that is floating point reasoning. More at http://www.cs.bath.ac.uk/~mjb/ 
Nov 30, 2011  14:0015:00  James  P, NP, etc  Russel Impagliazzo: "A Personal View of AverageCase
Complexity" (http://portal.acm.org/ http://cseweb.ucsd.edu/~ 
Nov 23, 2011  14:0015:00  Chris T  Robot soccer software  Using genetic algorithms to optimize robot soccer players. 
Nov 16, 2011  14:0015:00  Chris F  Scheduling  Solving realworld scheduling problems, both for UBC exams and NSERC reviews 
Nov 2, 2011  14:0015:00  Sam  Formal verification  A tutorial on SATbased formal verification 
Oct 19, 2011  14:0015:00  Lin  Algorithm portfolios  Work in progress on experiments with modelfree portfolios 
Oct 10, 2011  14:0015:00  James  Algorithm configuration  Work in progress for LION 
Oct 3, 2011  14:0015:00  Chris N  HAL  MSc thesis presentation 
Sept 29, 2011  14:0015:00  Kevin LB  Algorithm configuration & selection  Review of "Beyond Worst Case Complexity" Workshop 
Sept 21, 2011  14:0015:00  Rui  Summary of summer project  
Sept 1, 2011  14:0015:00  Maverick/Jonathan/Rui  Summary of summer projects  
August 24, 2011  11:0013:00  Lin  Visualization of configuration spaces  From Satenstein journal paper 
June 23 & 30, 2011  14:0015:00  Sam  Delta debugging  
June 16, 2011  14:0015:00  James  Parameter tuning  Parameter tuning by
simple regret algorithms and multiple simultaneous hypothesis testing Amine Bourki, Matthieu Coulm, Philippe Rolet, Olivier Teytaud, Paul Vayssiere, ININCO 2010. 
June 9, 2011  14:0015:00  Dave  SLS for SAT  SAT practice talk 
June 7, 2011  14:0015:30  Chris F  Automated Configuration of Planners  2 ICAPS workshop practice talks 
March 30, 2011  13:3014:30  Chris F  Parallel SAT solving  Improving Parallel Local
Search for SAT Alejandro Arbelaez and Youssef Hamadi, LION 2011. 
March 23, 2011  13:3014:30  Sam  Systematic SAT Solvers  Watched literals and Sam's work on improving them 
March 16, 2011  13:3014:30  Lin  PerInstance Algorithm Configuration  InstanceBased
Selection of Policies for SAT Solvers. Mladen Nikolic, Filip Maric and Predrag Janicic. SAT 2009. 
March 3, 2011  10:3011:30  Maverick  Algorithm Configuration  Update on the implementation of SMAC in HAL 
February 24, 2011  10:3011:30  Marius Schneider  Algorithm Configuration for ASP and for Parallel Solvers  Update on the work done in Potsdam 
February 10, 2011  10:3011:30  Dave T  Random Instance Generation for SAT  Towards
IndustrialLike Random SAT Instances. Carlos Ansotegui, Jordi Levy, and Maria Luisa Bonet. IJCAI09. 
February 3, 2011  10:3011:30  James  GPU computing, Performance tuning  Automatic
Tuning Matrix Multiplication Performance on Graphics Hardware Changhao Jiang and Marc Snir. Technical Report UIUC DCSR20052558 Department of Computer Science, UIUC 
Jan 13, 2011  1pm3pm  Chris N. Frank 
Metaalgorithmics Algorithm configuration 
Practice talks for LION5: HAL: A Framework for the Automated Analysis and Design of HighPerformance Algorithms. Christopher Nell, Chris Fawcett, Holger H. Hoos, and Kevin LeytonBrown. Sequential ModelBased Optimization for General Algorithm Configuration. Frank Hutter, Holger Hoos, and Kevin LeytonBrown. 
Dec 23, 2010  1pm2pm  Chris N  Metaalgorithmics  Practice talk for LION: HAL: A Framework for the Automated
Analysis and Design of HighPerformance Algorithms. Christopher Nell, Chris Fawcett, Holger H. Hoos, and Kevin LeytonBrown 
Nov 24, 2010  1pm2pm  Chris F.  Timetabling  Chris's work on UBC's exam scheduling. Slides 
Nov 2, 2010  1pm2pm  Chris N  Metaalgorithmics  Experiment
design and administration for computer clusters for SATsolvers (EDACC)
 System description Adrian Balint, Daniel Gall, Gregor Kapler, and Robert Retz Journal on Satisfiability, Boolean Modeling and Computation 7 (2010) 77–82. 
Sept 8, 2010  1pm2pm  Lin  Algorithm selection + configuration  ISAC  Instance Specific Algorithm Configuration. Serdar Kadioglu, Yuri Malitsky, Meinolf Sellmann, Kevin Tierney. ECAI '10: Proceedings of the 19th European Conference on Artificial Intelligence (2010) 
Aug 10, 2010  4:155:15pm  Mike Osborne  Gaussian Processes  Gaussian Processes for Sequential
Prediction 
July 21 (Wed!), 2010  4:155:15pm  Alvaro Fialho  Dynamic Bandits  
June 29, 2010  4:155:15pm  Frank  Algorithm Configuration  "Automated Tuning of Optimization Software Parameters" (2007
Tech Report, see http://www.optimization and "How much do we pay for using default parameters? (2009 paper in the Journal of Computational Optimization and Applications, see http://www.springerlink.com/ 
June 8, 2010  4:155:15pm  Frank  Algorithm Configuration  Automated
Configuration of Mixed Integer Programming Solvers Frank Hutter, Holger H. Hoos and Kevin LeytonBrown. Accepted at CPAIOR10. Practice talk for CPAIOR. 
May 25, 2010  4:155:15pm  Kevin LB  Empirical research in game theory   
May 18, 2010  4:155:15pm  Lin  Algorithm selection + configuration  Hydra: Automatically Configuring Algorithms for
PortfolioBased Selection Lin Xu, Holger Hoos, and Kevin LeytonBrown. To appear in AAAI10. 
Mar 16, 2010  4:155:15pm  Dave  SAT  Dynamic Scoring Functions with Variable Expressions: New SLS
Methods for Solving SAT Dave Tompkins and Holger H. Hoos. Accepted to SAT10. 
Mar 9, 2010  4:155:15pm  Frank  Parameter Tuning  Tuning
Local Search by AverageReward Reinforcement Learning. Steven Prestwich. LION 2 (2008) 
Feb 9, 2010  3:454:45pm  Fahiem Bacchus  SAT  Preprocessing SAT instances with hyperbinary resolution 
Presentations 2009
Date  Time  Presenter  General Topic 
Paper / Title 

Jan 20, 2009  12:302pm  Ashique  Automated algorithm configuration  Ashique's MSc thesis presentation 
Feb 3, 2009  12:302pm  Chris  Automated algorithm configuration  Bryan A. Tolson and Christine A. Shoemaker Dynamically dimensioned search algorithm for computationally efficient watershed model calibration Water Resources Research, 2005 
Mar 3, 2009  12:302pm  Dave Thompson  Empirical Algorithmics in Game Theory  David Robert Martin Thompson and Kevin
LeytonBrown Computational Analysis of PerfectInformation Position Auctions Submitted to the 10th ACM Conference on Electronic Commerce 
Mar 10, 2009  12:302pm  Dave Thompson  Empirical Algorithmics in Game Theory  Dave's presentation continued 
Mar 24, 2009  12:302pm  Lin  Empirical Hardness Models  Eric A. Brewer HighLevel Optimization via Automated Statistical Modeling Principles and Practice of Parallel Programming, 1995 
Apr 6, 2009  12:302pm  Lin  Empirical Hardness Models  Lin's
presentation continued 
May 5, 2009  12:302pm  Lin  Feature selection  Material from various sources 
June 2, 2009  12:302pm  Chris F  Algorithm synthesis  JeanNoel Monette, Yves Deville, and
Pascal Van Hentenryck AEON: Synthesizing Scheduling Algorithms from HighLevel Models Operations Research and CyberInfrastructure 
Summer 2009      Research  Informal meetings to discuss various research topics 
Sept 16, 2009  1:302:30pm  Frank  Algorithm configuration  PhD thesis defence practice talk. Thesis defence: 12:30pm on Friday, Sept 18, room 200, Graduate Student Centre. 
Sept 23, 2009  1:302:30pm  Massih Khorvash  Maximum Cliques  MSc thesis defence. Thesis title: On uniform sampling of maximum cliques. 
Oct 7, 2009  1:302:30pm  Chris F  Algorithm synthesis  Arne Lokketangen and Roland Olsson Generating MetaHeuristic Optimization Code using ADATE (paper under review at Journal of Heuristics; no, Chris is not the reviewer, he got a preprint at SLS 2009) 
Oct 14, 2009  1:302:30pm  Fahiem Bacchus  Constraint Optimization, Branch and Bound  Solving Constraint Optimization Problems with Branch and Bound 
Oct 28, 2009  11:302:30pm  Fahiem Bacchus  Constraint Optimization, Branch and Bound  Solving Constraint Optimization Problems with Branch and Bound 
Nov 25, 2009  1:302:30pm  Chris N  Learning Heuristics 
Learning Heuristics for the Superblock Instruction Scheduling
Problem T. Russell, A.M. Malik, M. Chase, and P. van Beek. IEEE Transactions on Knowledge and Data Engineering, 21 (10). p.14891502 (Oct. 2009) http://ai.uwaterloo.ca/~ 
Previous presentations 2008
Date  Time  Presenter  General Topic 
Paper / Title 

January 30, 2008  12:001:30pm  Lin  Statistics 
Statistical analysis of experiments. Not based on a paper. 
February 13, 2008  12:001:30pm  Lin  Statistics  Continued: statistical analysis of experiments. Not based on a paper. 
February 20, 2008      Reading week   
February 27, 2008  12:001:30pm  Frank 
Automated parameter tuning 
Parameter tuning using response surfaces. No paper, discussion of ongoing work. Slides 
March 5, 2008  12:001:30pm  Frank  Automated parameter tuning  Continued: parameter tuning using response surfaces. No paper, discussion of ongoing work. Updated slides 
March 12, 2008  12:001:30pm  Chris 
Scheduling Competition  A Modular Multiphase Heuristic Solver for Post Enrolment
Course Timetabling Marco Chiarandini, Chris Fawcett, Holger H. Hoos A Competition Retrospective. Slides 
March 26, 2008  12:001:30pm  Erik  Empirical algorithmics course presentation  Simple Search Methods For Finding A Nash Equilibrium by
Porter, Nudelman and Shoham (http://robotics.stanford.edu/ 
April 2, 2008  12:001:30pm  Chris & Zoreh  Empirical algorithmics course presentations  Chris: Panagopoulou, P. N. and Spirakis, P. G.
2007. Algorithms for pure Nash equilibria in weighted congestion
games. J. Exp. Algorithmics 11 (Feb. 2007), 2.7. (http://www.cs.ubc.ca/~hutter/earg/papers08/p1panagopoulou.pdf) Slides Zoreh: W. Spears, V. Anand, A Study of Crossover Operators in Genetic Programming, Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems.(http://citeseer.ist.psu.edu Slides 
April 9, 2008  12:001:30pm  Ashique & Xiaofei  Empirical algorithmics course presentations  Ashique: C. M. Li, W. Wei, and H. Zhang. Combining
Adaptive Noise and LookAhead in Local Search for SAT. In
Proceedings of LSCS2006, pages 2–16, 2006. (http://www.springerlink.com Slides Xiaofei: Ozun, Alper and Cifter, Atilla (2007): Nonlinear Combination of Financial Forecast with Genetic Algorithm. MPRA Paper 2488, University Library of Munich, Germany. (http://mpra.ub.unimuenchen.de 
April 23, 2008  12:001:30pm  Dave  Local search for SAT  Advances in Local
Search for Satisfiability Duc Nghia Pham, John Thornton, Charles Gretton, and Abdul Sattar 
May 7, 2008  12:001:30pm  Xiaofei  Empirical algorithmics course presentation  K. Jamieson, H. Balakrishnan, "PPR: Partial Packet Recovery
for Wireless Networks", SIGCOMM 2007. (http://nms.lcs.mit.edu/papers 
June 11, 2008  12:001:30pm  Frank  Online parameter tuning  Online Estimation of SAT
Solving Runtime by Shai Haim and Toby Walsh, SAT 2008 
July 2, 2008  12:001:30pm  Ashique  Bandits for parameter tuning  Adaptive
Operator Selection with Dynamic MultiArmed Bandits Luis DaCosta, Álvaro Fialho, Marc Schoenauer, Michèle Sebag GECCO 2008 
July 16, 2008  12:001:30pm  Lin  Backdoors  Backdoors To
Typical Case Complexity Ryan Williams, Carla P. Gomes, Bart Selman IJCAI03 
August 13, 2008  121:30pm  Chris (practice talk)  Timetabling  Marco Chiarandini, Chris Fawcett, and Holger H. Hoos. A Modular Multiphase Heuristic Solver for Post Enrolment Course Timetabling In PATAT 2008 
Oct 3, 2008  1112:30  Frank  Automated Parameter Tuning  J. Gratch and S. Chien Adaptive Problemsolving for Largescale Scheduling Problems: A Case Study JAIR 1996 Slides 
Oct 15, 2008  1112:30  Chris  Experimental Methodology  Marco Chiarandini, Luis Paquete, Mike Preuss and Enda Ridge Experiments on Metaheuristics: Methodological Overview and Open Issues Technical report Slides 
Oct 22, 2008  1112:30  Dave  Experimental Methodology  J.N. Hooker Testing Heuristics: We Have It All Wrong Journal of Heustics, 1995 Slides 
Oct 29, 2008  1112:30  Lin  Algorithm Portfolios, Bandits  Matteo Gagliolo and Juergen M. Schmidhuber Algorithm Selection as a Bandit Problem with Unbounded Losses Technical report, 2008 
Nov 5, 2008  1112:30  Ashique  Statistical Tests  Oren Etzioni and Ruth Etzioni Statistical Methods for Analyzing Speedup Learning Experiments Journal of Machine Learning, 1994 
Nov 12, 2008  1112:30  Frank  Algorithm Portfolios, Bandits  Matteo Gagliolo and Juergen M. Schmidhuber Learning Dynamic Algorithm Portfolios Technical Report, 2007 
Nov 19, 2008  1112:30  Frank  Algorithm Portfolios, Bandits  Continued: Matteo Gagliolo and Juergen M. Schmidhuber Learning Dynamic Algorithm Portfolios Technical Report, 2007 
Nov 26, 2008  1112:30  Holger  Algorithm configuration  Alex Fukunaga Automated Discovery of Local Search Heuristics for Satisfiability Testing  not available online, come get a copy from me Evolutionary Computation, 2008 
Dec 3, 2008  1112:30  Evgeny  Local Search, Theory  Andrei A. Bulatov and Evgeny S. Skvortsov Phase transition for Local Search on planted SAT 
Previous presentations fall 2007
Date  Time  Presenter  General Topic 
Paper / Title 

Dec 13, 2007  11:30am1pm  Hoyt  Clustering  Hoyt A. Koepke and Bertrand Clarke. A Bayesian Approach to Cluster Validation To appear in the International Symposium on AI & MATH '08. 
Nov 30, 2007  11:30am1pm  Ashique  Structure in SAT  R. Ostrowski, E. Gregoire, B. Mazure and L. Sais. Recovering and Exploiting Structural Knowledge from CNF Formulas CP 2002 
Nov 23, 2007  11:30am1pm  Firas  PhD defense practice talk  Samplingbased approaches to inference in undirected graphical models 
Nov 16, 2007  11:30am1pm  Guest speaker: Alexander Skopalik 
Game theory  Local search and computing equilibria in congestion games (research talk) Abstract: Congestion games are games where the cost of a player from using a certain resource depends on the total number of players that are using the same resource. In this talk, we present new results on the complexity of computing and approximating pure Nash equilibria (PNE) in congestion game. We start by giving an overview over the complexity class PLS that contains many interesting local search problems. It is known that computing PNE in congestion games is PLShard. A natural and convincing notion of approximation for equilibria in congestion games assumes that agents are ambivalent between strategies whose delay differs by less than a factor of $\alpha$, for some $\alpha$ > 1. In this talk, we show that computing an $\alpha$approximate equilibrium is PLScomplete. Thus finding an approximate Nash equilibrium is as hard as finding an exact Nash equilibrium or solving any other problem in PLS. 
Nov 9, 2007  EARG cancelled due to talk by Avi Pfeffer, Harvard
University, 11am12:30. Title: Modeling the Reasoning of Agents in Games Abstract: Why do agents (people or computers) do things in strategic situations? Answering this question will impact how we build computer systems to assist, represent or interact with people in interactions with other agents such as negotiations and resource allocation. We identify four reasoning patterns that agents might use: choosing an action for its direct effect on the agent's utility, attempting to manipulate another agent, signalling information to another agent that the first agent knows, or revealing or hiding information from another agent that the first agent itself does not know. We present criteria that characterize each reasoning pattern as a pattern of paths in a multiagent influence diagram, a graphical representation of games. We define a class of strategies in which agents do not make unmotivated distinctions, and show that if we assume all agents play these kinds of strategies, our categorization of reasoning patterns is complete and captures all situations in which an agent has reason to make a decision. We then study how people use two reasoning patterns in a particular negotiation game. We use machine learning to learn models of people's play, and embed our learned models in computer negotiators. We find that negotiators that use our learned model outperform classical gametheoretic agents and also outperform people. Finally, we learn models of the way people's behavior changes in ongoing interactions with the same agent, particularly the degree to which retrospective (rewarding or punishing past behavior) and prospective (attempting to induce future good behavior) reasoning play a role. 

Nov 2, 2007  11:30am1pm  Lin  No free lunch theorems  David H. Wolpert and William G. Macready No free lunch theorems for optimization IEEE Transactions on Evolutionary Computation, 1997 
Oct 25, 2007  11:30am1pm  Ashique  SAT 
Lintao Zhang, Sharad Malik The Quest for
Efficient Boolean Satisfiability Solvers 
Oct 18, 2007  Frank  Automated parameter tuning 
Thomas Bartz–Beielstein and Sandor Markon. In Congress on Evolutionary Computation (CEC'04) Frank's slides 
On the stack  please feel free to pick one of these if you are looking for a paper to present. Other papers are of course also welcome.
Date  Time  Presenter  General Topic 
Paper / Title 

Global optimization survey 
Donald R. Jones 

Global optimization: one approach 
Brigham S. Anderson, Andrew W. Moore, and David Cohn. 

Global optimization: one approach 
Mauro Brunato, Roberto Battiti and Srinivas Pasupuleti 

Experimental Design: foundations 
Merlise A. Clyde 

Experimental Design: applications 
Steven Coy, Bruce L. Golden, George C. Runger, Edward A. Wasil 

Runtime prediction 
Philip Kilby, John Slaney, Sylvie Thiebaux, and Toby Walsh 

Learning of search space structure 
Shumeet Baluja and Scott Davies 

Combining local and global search 
Meinolf Sellmann and Carlos Ansotegui 
Previous discussions spring and summer 2007
Date  Time  Presenter  General Topic 
Paper / Title 

Aug 30, 2007  12:3014:00  Lin  Portfolios for SAT 
Lin Xu, Frank Hutter, Holger Hoos, Kevin LeytonBrown. SATzilla07: The Design and Analysis of an Algorithm Portfolio for SAT Practice talk for CP 
Aug 23, 2007  12:3014:00  Lin  Expectation Maximization for CSPs 
Eric I. Hsu and Matthew Kitching and Fahiem Bacchus and Sheila A. McIlraith 
Aug 8, 2007  12:3014:00  Hoyt  Feature selection 
Huan Liu and Lei Yu Toward Integrating Feature Selection Algorithms for Classification and Clustering Available online at http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1401889 
Aug 1, 2007  12:3014:00  Erik  Statistical evaluation 
Eric Sodomka, John Collins, and Maria Gini Efficient Statistical Methods for Evaluating Trading Agent Performance AAAI 07 
July 10, 2007  12:3014:00  Erik  Machine learning 
Thomas G. Dietterich 
July 3, 2007  12:3014:00  Frank  Reinforcement learning for SAT 
Michail G. Lagoudakis and Michael L. Littman. Learning to Select Branching Rules in the DPLL Procedure for Satisfiability 
June 19, 2007  12:3014:00  Lin  Reinforcement learning 
Slides by Ann Nowe based on the book by Sutton and Barto: http://www.cs.ualberta.ca/~sutton/book/ebook/thebook.html

June 5, 2007  12:3014:00  Frank  Automated parameter tuning 
Prasanna Balaprakash, Mauro Birattari, and Thomas Stuetzle Improvement
Strategies for the FRace algorithm: Sampling Design and Iterative
Refinement 
Apr 17, 2007  12:3014:00  Erik  Stochastic optimisation 
L. Mercier and P. Van Hentenryck. Performance
Analysis of Online Anticipatory Algorithms for Large Multistage
Stochastic Integer Programs A slide show is available at http://www.cs.brown.edu/people/mercier/slides/IJCAI_07_AnticipatoryAlg.html 
Apr 3, 2007  12:3014:00  Frank  Stochastic local search 
Duc Nghia Pham, John Thornton, and Abdul Sattar Building Structure
into Local Search for SAT

Mar 20, 2007  12:3014:00  Ashique  Algorithm portfolios 
Carla Gomes and Bart Selman. Artificial Intelligence Journal,
Vol. 126, 2001, 4362 
Mar 13, 2007  12:3014:00  Invited speaker: Karl Lieberherr  Experimental studies in theory 
Karl J. Lieberherr 
Feb 27, 2007  12:3014:00  Lin  Machine learning 
Chris Bishop and Markus Svensen 
Feb 22, 2007  Statistics in medicine 
Interesting & relevant article in the economist, found by KLB: Signs of the times http://www.economist.com/science/displaystory.cfm?story_id=8733754 

Feb 13, 2007  12:3014:00  Mike L  Experimental studies in theory 
Kamesh Madduri, David A. Bader, Jonathan W.Berry, and Joseph
R. Crobak 
Jan 22, 2007  12:3014:00  Frank  Bandits 
Matthew J. Streeter and Stephen F. Smith Here is Matthew's presentation from CP 
Previous discussions fall term 2006/07
Date  Time  Presenter  General Topic 
Paper / Title 

Dec 13, 2006  12:3014:00  Frank  Automated parameter tuning 
Frank talking about his ongoing research on local search for parameter tuning. Here are the slides 
Nov 29, 2006  12:3014:00 
Cancelled because of Geoff Hinton's talk 

Nov 15, 2006  12:3014:00  Kevin LB  Restart Strategies 
Matteo Gagliolo and Juergen M. Schmidhuber. 
Nov 1, 2006  12:3014:00  Holger  Multiobjective optimization  Continuation of Chapter 4 of SLS:FA, and multiobjective optimization 
Oct 25, 2006  12:3014:00  Holger  Experimental analysis of Las Vegas algorithms  Chapter 4 of SLS:FA 
Oct 18, 2006  12:3014:00  Michael L  Experimental analysis in the theoretical algorithms community 
Arthur Brady and Lenore Cowen 
Oct 11, 2006  12:3014:00  Mirela  Bayesian learning 
Continuation of Bayesian CART and start of Mick's presentation 
Oct 4, 2006  12:3014:00  Mirela  Bayesian learning 
Yuhong Wu, Hakon Tjelmeland and Mike West. 
Sep 27, 2006  12:3014:00  Lin  Runtime prediction 
Continuation of: 
Sep 20, 2006  12:3014:00  Lin  Runtime prediction 
Matteo Gagliolo and Juergen M. Schmidhuber I'll see Matteo at CP  if you have comments or questions please let me know. 
Sep 13, 2006  12:3014:00  Alena  PhD defense 
Title: Novel Heuristic Search Methods for Protein Folding and Identification of Folding Pathways Abstract: Proteins form the very basis of life. If we were to open up any living cell, we would find, apart from DNA and RNA molecules whose primary role is to store genetic information, a large number of different proteins that comprise the cell itself (for example the cell membrane and organelles), as well as a diverse set of enzymes that catalyze various metabolic reactions. If enzymes were absent, the cell would not be able to function, since a number of metabolic reactions would not be possible. Functions of proteins are the consequences of their functional 3D shape. Therefore, to control these versatile properties, we need to be able to predict the 3D shape of proteins; in other words, solve the protein folding problem. The prediction of a protein's conformation from its aminoacid sequence is currently one of the most prominent problems in molecular biology, biochemistry and bioinformatics. In this thesis, we address the protein folding problem and the closelyrelated problem of identifying folding pathways. The leading research objective for this work was to design efficient heuristic search algorithms for these problems, to empirically study these new methods and to compare them with existing algorithms. This thesis makes the following contributions: (1) we show that biologically inspired approaches based on the notion of stigmergy – where a collection of agents modifies the environment, and those changes in turn affect the decision process of each agent (particularly artificial colonies of ants that give rise to such properties as selforganization and cooperation also observed in proteins) is a promising field of study for the protein folding problem; (2) we develop a novel adaptive search framework that is used to identify and to bin promising candidate solutions and to adaptively retrieve solutions when the search progress is unsatisfactory; (3) we develop a new method that efficiently explores large search neighbourhoods by performing biased iterated solution construction for identifying folding pathways; and (4) we show that our algorithms efficiently search the vast search landscapes encountered and are able to capture important aspects of the process of protein folding for some widely accepted computational models. 
Sep 6, 2006      LCI open house   
Aug 23, 2006  12:3014:00  Frank  Experimental design for optimization 
Belarmino AdensoDíaz and Manuel Laguna, Here are my slides. There was a life demonstration of their CALIBRA software: I ran CALIBRA on the branin test function with a wrapper outputting which parameter settings are begin run into a file. Then I used Matlab to visualize that trajectory. I packed all this into a zip file. My Summary: 
Aug 16, 2006  13:00 14:00 
Kevin LB/ Frank  Model counting 
Model Counting:
A New Strategy for Obtaining Good Bounds Here are the original slides of the AAAI talk 
Previous paper discussions 2004  2006
Date  Time  Presenter  General Topic 
Paper / Title 

Feb 23, 2006  16:0017:30  Kevin M  Experimental design for optimization 
Efficient Global Optimization of Expensive Black Box Functions Donald R. Jones, Matthias Schonlau, William J. Welch. Journal of Global Optimization (?), 1998. This is very well written and the basis of section 6.3.5 of the DACE book. 
Feb 9, 2006  16:0017:30  Kevin M  Active learning  Chapter 6 of the DACE book. Please see Frank for a copy. 
Nov 21, 2005  17:3019:00  Holger  Spacefilling designs for computer experiments  Chapter 5 of the DACE book. Please see Frank for a copy. 
Nov 14, 2005  13:3015:00  Lin  Additional topics in prediction methodology  Chapter 4 of the DACE book, continued. Please see Frank for a copy. Lin's slides. 
Nov 7, 2005  13:3015:00  Lin  Additional topics in prediction methodology  Chapter 4 of the DACE book. Please see Frank for a copy. Lin's slides. 
Oct 31, 2005  17:3019:00  Kevin LB  Predicting output from computer experiments  Chapter 3 of the DACE
book. Please see Frank for a copy. Kevin's
slides 
Oct 24, 2005  13:3015:00  Hendrik  Gaussian processes  Section 2.3 of the DACE book.
Please see Frank for a copy. Since this is all about Gaussian processes, please also read Carl Rasmussen's tutorial Gaussian processes in Machine Learning. Although Hendrik won't present this paper, we will discuss questions and comments people have ... 
Oct 3, 2005  17:3019:00  Frank  Introduction to DACE  Chapter 1 and sections 2.12.2 of the DACE book. Please see Frank for a copy. My slides. 
May 4, 2005  14:3016:00  Kevin M  Experimental design  Sacks, Welch, Michtell & Wynn, 1989: Design and Analysis of Computer Experiments 
Apr 28, 2005  14:3016:00  Kevin LB  Experimental design  Design and Analysis with Quantitative Predictors and Factors, chapters 1419 in the book, part 3 
Apr 21, 2005  14:3016:00  Kevin LB  Experimental design  Design and Analysis with Quantitative Predictors and Factors, chapters 1419 in the book, part 2 
Apr 14, 2005  14:3016:00      cancelled 
Apr 7, 2005  14:3016:00  Kevin LB  Experimental design  Design and Analysis with Quantitative Predictors and Factors, chapters 1419 in the book, part 1 
Mar 30, 2005  14:3016:00  Frank  Experimental design  Design and Analysis with Random Effects, chapters 913 in the book continued 
Mar 23, 2005  14:3016:00  Frank  Experimental design  Design and Analysis with Random Effects, chapters 913 in the book 
Mar 16, 2005  14:3016:00  Clint  Experimental design 
Fractional Factorial Experiments, chapters 78 in the book 
Mar 9, 2005  14:3016:00  Jacek  Experimental design 
Analysisofvariance, chapters 6 in the book 
Mar 2, 2005  14:3016:00  Jacek  Experimental design 
Design of Factorial Experiments, chapters 45 in the book, finished by Kevin LB: Here's Kevin's slides Analysisofvariance, chapters 6 in the book; started by Jacek 
Feb 23, 2005  14:3016:00  Kevin LB  Experimental design 
Design of Factorial Experiments, chapters 45 in the book,
to be finished 
Feb 16, 2005  14:3016:00    Reading week  All but reading :) 
Feb 9, 2005  14:3016:00  Kevin M  Reading week  Why I am a Bayesian Here's Kevin's slides 
Feb 2, 2005  14:3016:00  Holger  Experimental design  Statistical tests, chapters 23 in the book  continued and finished. 
Jan 26, 2005  14:3016:00    Experimental design 
Talk by and meeting with David Johnson. 
Jan 19, 2005  14:3016:00  Holger  Experimental design  Statistical tests, chapters 23 in the book, to be continued 
Jan 12, 2005  14:3016:00  Holger  Experimental design  Foundations of statistical experimental design, chapter 1 in the book 
Dec 9, 2004  15:0016:00    Organizational meeting   
Dec 2, 2004  15:0016:00  Clinton  Experimental design  Statistical Design of Experiments  specific topic & paper to be agreed upon 
Nov 25, 2004  15:0016:00  Dan  Experimental Design  Statistical Design of Experiments (continued) 
Nov 18, 2004 
15:0016:00  Asher / Dan  Experimental design 
“Designing and Reporting Computational Experiments with Heuristic Methods” by Barr, R. S., B. L. Golden, J. P. Kelly, M. G. C. Resende and W. R. Stewart (1995). [pdf] continued and some stuff on Statistical Design of Experiments Dan will let us know about soon ... 
Nov 11, 2004  No meeting    Remembrance day   
Nov 4, 2004 
15:0016:00  Asher  Experimental design 
“Designing and Reporting Computational Experiments with Heuristic Methods” by Barr, R. S., B. L. Golden, J. P. Kelly, M. G. C. Resende and W. R. Stewart (1995). [pdf] 
Oct 28, 2004  15:0016:00  Kevin LeytonBrown  Search in Game Theory  Computing Nash Equilibria of ActionGraph Games. Bhat, LeytonBrown. Presented at the 20th Conference on Uncertainty in Artificial Intelligence (UAI2004) [pdf] 
Oct 21, 2004  15:0016:00  Frank / Dave  Search in Game Theory 
MultiAgent Algorithms for Solving Graphical Games [pdf] (continued) and Multiagent oriented constraint satisfaction [pdf] (local search for CSP cast as collaborating agents) 
Oct 14, 2004  15:0016:00  Frank  Search in Game Theory 
MultiAgent Algorithms for Solving Graphical Games [pdf] This is a local search paper for a compact set of games called graphical games (basically Bayes nets for games) 
Oct 7, 2004  15:0016:00  Asher  Search in Game Theory 
Simple Search Methods for Finding a Nash Equilibrium [pdf] This paper concerns complete search. 
Sep 30, 2004  15:0016:00  Kevin Smyth  Search space analysis  Holger H. Hoos, Kevin Smyth, and Thomas St¨utzle. Search Space Features Underlying the Performance of Stochastic Local Search Algorithms for MAXSAT. In Parallel Problem Solving from Nature – PPSN 2004, 2004. [pdf] 
Sep 23, 2004  15:0016:00  Alena Shmygelska  Ant Colony Optimisation  Dorigo M., G. Di Caro & L.
M. Gambardella (1999). Ant Algorithms for Discrete Optimization.
Artificial Life, 5(2):137172. [pdf]
Relevant Sections (4.5 pages): 
Here's the old EARG site with all previous papers
Original site creation and maintenance: Frank Hutter.
Currently maintained by: Chris Fawcett.