Theory Problem Solving Group

Overview

The Theory Problem Solving Group is a discussion group within UBC's Computer Science department. We meet weekly to discuss and (hopefully) solve open problems in theoretical computer science. Our focus is on fun, easily accessible problems and the meetings are open to everyone.

Schedule

We meet on Tuesdays from 4:00 to 5:00 in the BETA lab (CICSR 153), except on Tuesdays when there is a BETA seminar. It's very casual, so if you have to come late or leave early it's not a problem.

Problems

If you have a problem that you would like to discuss in the problem solving group, by all means email me or just come to a meeting and bring it up :-)

Open (?) Problems

These are problems that, to the best of our knowledge, are open. Some of these may have already been solved. Also, some of the open problems may be better studied than we know.

Floodlight (Stage Illumination) (introduced to the group by Jamie King)(Nov 2004)
Beta-Skeleton Dilation (introduced to the group by Will Evans) (Oct 2004)
Field Scheduling (introduced to the group by Chris Gray) (summer 2004)
Running Time of the Dreidel Game (introduced to the group by Cyril Banderier) (summer 2004)
Reducing 2SAT to Max Flow (introduced to the group by Mohammad Safari) (summer 2004)
Complexity of the Coin Sliding Puzzle on a Hex Lattice (introduced to the group by Bob Hearn) (summer 2004)
Triangulating Regular Polygons to Minimize Dilation (introduced to the group by Chris Gray) (summer 2004)
Maximum Distant String Sets (introduced to the group by Dan Tulpan) (summer 2004)

Problems Solved by Others

These are problems that we investigated because we did not know of a solution, then discovered that they had already been solved.

Minimum Line Covering of Vertices (introduced to the group by Jonathan Backer) (solution located by Mohammad Safari)

Problems Solved by Us

Connecting Vertices of Simple Polygons with Arcs (solution by Warren Cheung, Steph Durocher, Chris Gray, and Jamie King)