Matt Streeter




Computer Science Department
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213

Phone: (412) 268-7228
Office: Wean Hall 8116

I graduated from the Computer Science Ph.D. program after defending my thesis in December 2007. I then spent a semester as a postdoc in the CMU Robotics Institute, working with my graduate advisor Stephen Smith. I now work at Google in Pittsburgh.
Here are descriptions of some of my research projects: Before coming to CMU I worked with John Koza at Genetic Programming, Inc. using evolutionary algorithms to synthesize analog electrical circuits. In 2005 we received a patent for one of our evolved circuits. It is one of the first patents ever granted for a machine-generated invention, and has prompted a patent law puzzle as well as some theological confusion.

In the fall of 2006 I presented a thesis proposal.

Selected Publications by Topic

Click here for a chronological list of all publications.

Online Algorithms

Online Learning of Assignments
with Daniel Golovin and Andreas Krause, in Proceedings of the Twenty-Third Annual Conference on Neural Information Processing Systems (NIPS 2009)
[Paper] [Longer technical report]

Tighter Bounds for Multi-Armed Bandits with Expert Advice
with Brendan McMahan, in Proceedings of the Twenty-Second Conference on Computational Learning Theory (COLT 2009)
[Paper]

An Online Algorithm for Maximizing Submodular Functions
with Daniel Golovin, in Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS 2008)
[Paper] [Longer technical report]

Algorithm Portfolios

New Techniques for Algorithm Portfolio Design
with Stephen Smith, in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI 2008)
[Paper]

Combining Multiple Heuristics Online
with Daniel Golovin and Stephen Smith, in Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI 2007)
[Paper] [Slides (PDF,QuickTime)]

Restart Schedules for Ensembles of Problem Instances
with Daniel Golovin and Stephen Smith, in Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI 2007)
[Paper] [Slides (PDF,QuickTime)]

Using Decision Procedures Efficiently for Optimization
with Stephen Smith, in Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007)
[Paper] [Slides (PDF,QuickTime)]

The Max k-Armed Bandit Problem

A Simple Distribution-Free Approach to the Max k-Armed Bandit Problem
with Stephen Smith, in Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP 2006)
[Paper] [Slides]

An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem
with Stephen Smith, in Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI 2006)
[Paper] [Slides]
A preliminary version appeared as a CMU technical report.

Job Shop Scheduling

Exploiting the Power of Local Search in a Branch and Bound Algorithm for Job Shop Scheduling
with Stephen Smith, in Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS 2006)
[Paper] [Slides]

How the Landscape of Random Job Shop Scheduling Instances Depends on the Ratio of Jobs to Machines
with Stephen Smith, in Journal of Artificial Intelligence Research 26
[Paper]
A preliminary version appeared as a CMU technical report.

Characterizing the Distribution of Low-Makespan Schedules in the Job Shop Scheduling Problem
with Stephen Smith, in Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS 2005)
[Paper] [Slides]

Evolutionary Computation Theory

Upper Bounds on the Time and Space Complexity of Optimizing Additively Separable Functions
in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004)
[Paper] [Slides] [Source code, etc.]

Two Broad Classes of Functions for which a No Free Lunch Result Does Not Hold
in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003)
[Paper] [Slides]

Genetic Programming

Genetic Programming IV: Routine Human-Competitive Machine Intelligence
with John Koza, Martin Keane, Bill Mydlowec, Jessen Yu, and Guido Lanza, Kluwer Academic Publishers
[Description] [Chapter 1]

Evolving Inventions
with John Koza and Martin Keane, in Scientific American
[Abstract]

What's AI Done for Me Lately? Genetic Programming's Human-Competitive Results
with John Koza and Martin Keane, in IEEE Intelligent Systems
[Paper]

Automated Discovery of Numerical Approximation Formulae via Genetic Programming
with Lee Becker, in Genetic Programming and Evolvable Machines, 4(3):255-286
[Abstract]

The Root Causes of Code Growth in Genetic Programming
in Proceedings of EuroGP 2003
[Paper]

Automatic Synthesis using Genetic Programming of Improved PID Tuning Rules
with Martin Keane and John Koza, in Proceedings of the 2003 Intelligent Control Systems and Signal Processing Conference (ICONS 2003)
[Paper] [Slides]

Iterative Refinement of Computational Circuits using Genetic Programming
with Martin Keane and John Koza, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002)
[Paper] [Slides]

Automatic Synthesis using Genetic Programming of an Improved General-Purpose Controller for Industrially-Representative Plants
with Martin Keane and John Koza, in Proceedings of the NASA/DoD Conference on Evolvable Hardware
[Paper]