CATS 2009

List of Accepted Papers and Tentative Schedule

(All CATS talks are in the Angus room, including the business meeting)

Tuesday, January 20, 1600-1730:

Ching-Lueh Chang and Yuh-Dauh Lyuu.
Spreading of messages in random graphs (STUDENT PAPER)
Mehdi Karimi and Arvind Gupta.
Minimum Cost Homomorphism to Oriented Cycles with Some Loops (STUDENT PAPER)
Wataru Matsubara, Shunsuke Inenaga and Ayumi Shinohara.
Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program (STUDENT PAPER)

Wednesday, January 21, 0900-1000:

Adam Day.
On Process Complexity (STUDENT PAPER)
Ukachukwu Ndukwu and J.W. Sanders.
Reasoning about a distributed probabilistic system (STUDENT PAPER)

Wednesday, January 21, 1330-1530:

Toshimasa Ishii and Kazuhisa Makino.
Augmenting Edge-Connectivity between Vertex Subsets
Abusayeed Saifullah and Alper Ungor.
A Simple Algorithm For Triconnectivity of a Multigraph
Koji Nakazawa and Makoto Tatsuta.
Type Checking and Inference for Polymorphic and Existential types
Mark Utting, Petra Malik and Ian Toyn.
Transformation Rules for Z

Wednesday, January 21, 1600-1730:

Vlad Estivill-Castro and Mahdi Parsa.
Computing Nash equilibria gets harder: New results show hardness even for Parameterized Complexity
Hideaki Fukuhara and Eiji Takimoto.
Lower bounds on quantum query complexity for read-once decision trees with parity nodes (STUDENT PAPER)
Nutan Limaye, Meena Mahajan and Prajakta Nimbhorkar.
Longest Paths in Planar DAGs in Unambiguous Logspace (STUDENT PAPER)

Thursday, January 22, 0900-1000:

Jing Cao and Albert Nymeyer.
Formal Model of a Protocol Converter (STUDENT PAPER)
Kevin Henshall, Peter Schachte, Harald Sondergaard and Leigh Whiting.
Boolean Affine Approximation with Binary Decision Diagrams

Thursday, January 22, 1330-1530:

Andras Farago.
Structural Properties of Random Graph Models
Kira Vyatkina.
Linear Axis for Planar Straight Line Graphs
David Pearce, Gary Haggard and Gordon Royle.
Edge-Selection Heuristics for Computing Tutte Polynomials
Sumit Ganguly.
Distributing Frequency-Dependent Data Stream Computations

Thursday, January 22, 1600-1700:

Paper accepted, but unable to attend CATS:

Rod Downey, Victoria University of Wellington, NZ
Prabhu Manyem, University of Ballarat, Australia

Email for Rod Downey: firstName.familyName at mcs.vuw.ac.nz
Email for Prabhu Manyem: p.familyName at ballarat.edu.au