| Date | Time | Presenter | Paper / Topic / Title |
| Oct 14 | 2:00-3:00pm | Steph Durocher |
Recent Results in Art Galleries
Tom
Shermer
Proc. IEEE, 80 (9) 1384-1399, September 1992. |
| Oct 7 | 2:00-3:00pm | Chris Gray |
NP-hardness Results for Planar SAT Problems |
| May 6 | 3:30-4:30pm | Ellen Gethner |
Rotation Systems
from "Topological Graph Theory" by J. Gross and T. Tucker
|
| Apr 18 | 3:30-4:30pm | Ellen Gethner |
On representations of some thickness-two graphs
Hutchinson, Shermer, and Vince
Computational Geometry Theory and Applications, 13 (1999), 161-171.
|
| Apr 10 | 4:00-5:00pm | Will Evans |
Embedding Planar Graphs on the Grid
Walter Schnyder
Symposium on Discrete Algorithms pp. 138-148, 1990.
|
| Mar 20 | 4:00-5:00pm | Stephane Durocher |
Channel Capacity
from "Elements of Information Theory" by T. Cover and J. Thomas
|
| Mar 6 | 4:00-5:00pm | Christine Heitsch |
Kolmogorov Complexity - Part II
from "Elements of Information Theory" by T. Cover and J. Thomas
|
| Feb 27 | 4:00-5:00pm | Alex Brodsky |
Kolmogorov Complexity - Part I
from "Elements of Information Theory" by T. Cover and J. Thomas
|
| Feb 13 | 4:00-5:00pm | Will Evans |
Information Theory and Noisy Circuit Complexity
|
| Feb 6 | 4:00-5:00pm | Will Evans |
Information Theory Introduction
from "Elements of Information Theory" by T. Cover and J. Thomas
|
| Nov 28 | 3:30-4:30pm | Ellen Gethner |
Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon
Joan P. Hutchinson
Mathematics Magazine, 66(4) 211-226, October 1993.
|
| Nov 21 | 3:30-4:30pm | Hamish Carr |
The Four Colour Problem
|
| Nov 14 | 3:30-4:30pm | David Kirkpatrick |
Randomized Algorithms for Trapezoidal Decomposition
|
| Nov 7 | 3:30-4:30pm | David Kirkpatrick |
Optimal Algorithms for Probabilistic Solitude Detection
on Anonymous Rings
L. Higham, D. Kirkpatrick, K. Abrahamson, and A. Adler
J. Algorithms, 23 (1997), 291-328.
|
| Oct 31 | 3:30-4:30pm | Stephane Durocher |
Randomized Byzantine Agreement
|
| Oct 24 | 3:30-4:30pm | Will Evans |
Permutation Routing on the Hypercube
|
| Oct 17 | 3:30-4:30pm | Nando de Freitas |
Lower Bounds in Large Deviation Theory
|
| Oct 10 | 3:30-4:30pm | Nando de Freitas |
Large Deviation Theory
Concentration of Measure for Randomized Algorithms:
Techniques and Analysis
Devdatt Dubhashi and Sandeep Sen
|
| Oct 3 | 3:30-4:30pm | Joel Friedman |
Expansion, Conductance, Eigenvalues, and Rapid Mixing
A Polynomial-Time Approximation Algorithm for the Permanent
of a Matrix with Non-Negative Entries
Mark Jerrum, Alistair Sinclair, Eric Vigoda
ECCC Report TR00-079
contains a recent result on approximating the number of perfect matchings
and is more verbose than the
STOC paper
.
Approximating the Permanent
Mark Jerrum and Alistair Sinclair
SIAM Journal on Computing 18(6): 1149-1178(1989)
provides more background.
|
| Sept 26 | 3:30-4:30pm | Will Evans |
More Markov Chain Monte Carlo Methods |
| Sept 19 | 3:30-4:30pm | Will Evans |
Orientation & Markov Chain Monte Carlo Methods |
| Aug 30 | 1-2pm | Nick Pippenger |
STOC 2001 Report Part II
Learning DNF in Time 2~O(n1/3)
, Page 258
Sharp Threshold and Scaling Window for the Integer Partitioning
Problem
, Page 330.
Almost Optimal Permutation Routing on Hypercubes
, Page 530.
A Polynomial-Time Approximation Algorithm for the Permanent
of a Matrix with Non-Negative Entries
, Page 712.
|
| Aug 23 | 1-2pm |  |
|
| Aug 16 | 1-2pm | Alex Brodsky |
STOC 2001 Report Part I
Quantum mechanical algorithms for the nonabelian hidden
subgroup problem
, Page 68
Quantum computers that can be simulated classically in
polynomial time
, Page 114.
Smoothed analysis of algorithms: why the simplex algorithm
usually takes polynomial time
, Page 296.
Computing crossing numbers in quadratic time
, Page 231.
|
| Aug 9 | 1-2pm | Bettina Speckmann |
Tight Degree Bounds for Pseudo-triangulations of Points
|
| Aug 2 | 1-2pm | |
|
| July 26 | 1-2pm | Jack Snoeyink |
Protein Chain Folding
NP-hardness of the HP model
Algorithms used with the HP model
Chain growing with more advanced models
Ideas appearing in the last CASP competition winner
|
| July 19 | 1-2pm | Dieter van Melkebeek |
Time-Space Tradeoffs for Satisfiability
|
| July 12 | 1-2pm | Sergei Bespamyatnikh |
Shortest Paths in the Plane with Polygonal Obstacles
James A. Storer and John H. Reif.
Journal ACM, 41(5):982-1012, 1994.
|
| July 5 | 1-2pm | Bettina Speckmann
David Kirkpatrick |
Symposium on Computational Geometry Trip Report |
| June 28 | 1-2pm | |
|
| June 21 | 1-2pm | Lila Kari |
Formal Language Theory and DNA Computing |
| June 14 | 1-2pm | Stephane Durocher |
Paths, Trees, and Flowers
Jack Edmonds.
Canadian Journal of Mathematics, 17:449-467, 1965.
|
| June 7 | 1-2pm | Alex Brodsky |
Reversible Space Equals Deterministic Space
K. Lange and P. McKenzie and A. Tapp.
Journal of Computer and System Sciences, 60(2):354-367, 2000.
|
| May 31 | 1-2pm | Will Evans |
Even More Hardness of Approximation |
| May 24 | 1-2pm | Will Evans |
More Hardness of Approximation |
| May 17 | 3-4pm | Will Evans |
Orientation & Hardness of Approximation |