Games, Puzzles, and Computation


One can frame a game or a puzzle as a decision problem: from this configuration, does the puzzle have a solution? Can Black win the game? The computational complexity of the decision problem can then be investigated. I will begin by reviewing the properties of the complexity classes I'll be discussing (NP-complete, PSPACE-complete, etc.), then briefly present several recent hardness results, including sliding-block puzzles, sliding-coin puzzles, TipOver, Rush Hour, Sokoban, hinged polygon dissections, plank puzzles, the Dyson telescope game, Amazons, and Konane.

Theorems, theories, and things: Computing is more than a science


As researchers in computing, we claim our field is most definitely a science---and we have the gargoyles to prove it! Yet many of the touchstones of science are conspicuously absent from computing "science", or present only on the periphery. Experiments are rare and empirically-supported quantitative laws still rarer. Such empirical results that we do posess seem far more context-sensitive than the universal laws forming the common currency of physical science.

Towards Internationalization: Computer Science and Technology at Tsinghua University


Prof. Xu will tell us about research foci and educational programs at Tsinghua University. Prof. Xu and Prof. Maosong Sun, the Chair of the department, will be attending our CPATH workshop the following weekend. We hope to find areas of research and educational collaboration between our two departments as well as to promote the CPATH Pacific Rim partnerships.

The CS department at Tsinghua is the leading computer science department in China.

CIS Department Photograph


The department has had a long standing tradition of having a graduation photo taken midway through spring term. If you have graduated, are planning to graduate this spring, or just planning to walk in this year's ceremony and graduating in the summer or next fall, please join us. This is not a formal occasion, just a relaxed group picture. We will have refreshments at 3:30 pm, with the photo being taken around 3:45 pm. All that participate in the photo will be given a copy at commencement inside your diploma cover.

Certifying Algorithms and the Undergraduate Curriculum


A proof of correctness of an algorithm is no guarantee that an implementation of it has no bugs. Software engineers typically try to reduce the probability of bugs through extensive testing, but this does not supply certainty. An alternative is a detailed proof that the implementation is correct, but such a proof, being even more complicated than the program it addresses, can be even more prone to human error.


Subscribe to RSS - Colloquium