CAG Schedule of Talks: Fall 2003

Schedule of Talks: Fall 2003

If you would like to give a talk in our seminar series, please contact Wendy Myrvold ()

Schedule for Friday Talks:

Date Place Time Speaker Abbreviated Title
Sept. 12 DSB C 113 2:30 Stirling Chow Drawing Area-Proportional Venn and Euler Diagrams
Sept. 15 Cornett A 148 10:30 Jan van Vuuren Characterising efficient lottery design structures
Sept. 19 DSB C 113 2:30 Gary MacGillivray A algorithmic characterisation of k-cop win graphs and digraphs
Sept. 26 DSB C 113 2:30 Glenn Mahoney D-Trust: A Generalized Framework for Trust Modeling and Reasoning
Oct. 3 DSB C 113 2:30 Allan Scott Algorithmic Combinatorial Game Theory
Oct. 10 DSB C 113 2:30 Jennifer Bruce Concentric Bilinski Diagrams and Geodesics
Oct. 17 DSB C 113 2:30 Yong Du An Improvement of the IPO Pairwise Generation Strategy
Oct. 24 DSB C 113 2:30 Lorraine Dame Computing the Circumdiameter of a Strongly Connected Directed Graph
Oct. 31 HSD A 240 3:30 Daniel German Proud to be a Computer Geek
Nov. 8-10 UVic Combinatorial Potlatch and 5th Coast Combinatorics Conference
Dec. 6-8 No CAG. CMS Meeting in Vancouver
Dec. 12 DSB C 113 2:30 Kui Wu Coverage redundancy based scheduling for wireless sensor networks
Wed. Dec. 17 EOW 430 10:00 Jared Saia Scalable and Attack Resistant Peer-to-peer Networks

Upcoming Talks:

Coverage redundancy based scheduling for wireless sensor networks
Kui Wu
Dec. 12, DSB C 113, 2:30

Wireless sensor networks consist of a large number of tiny sensors that have only limited energy supply. One of the major challenges in constructing such networks is to maintain long network lifetime as well as sufficient sensing area. To achieve this goal, a broadly-used method is to turn off redundant sensors. In this talk, we will talk about the problem of estimating redundant sensing areas among neighbouring wireless sensors. We will present an interesting observation concerning the minimum and maximum number of neighbours that are required to provide complete redundancy and introduce simple methods to estimate the degree of redundancy without the knowledge of location or directional information. We also provide tight upper and lower bounds on the probability of complete redundancy and on the average partial redundancy. With random sensor deployment, our analysis shows that partial redundancy is more realistic for real applications, since complete redundancy is expensive, requiring up to 11 neighbouring sensors to provide a 90 percent chance of complete redundancy. Several open questions will be posed.

Scalable and Attack Resistant Peer-to-peer Networks
Jared Saia
Computer Science, University of New Mexico
Dec. 17, EOW 430, 10am

This talk will discuss preliminary results on a project to design scalable and attack-resistant distributed networks. Our notion of attack-resistance depends on the idea of protecting critical invariants from adversarial attack. Some important critical invariants include: (i) an arbitrarily large fraction (e.g. 99%) of the unattacked peers can access an arbitrarily large fraction (e.g. 99%) of the content stored in the network, (ii) an arbitrarily large fraction of the unattacked peers remain connected in the network, and (iii) an arbitrarily large fraction of the peers must either follow a fixed set of rules, or be disconnected from the network. We require that the networks be scalable in the sense that all major operations have polylogarithmic resource bounds.

We propose to maintain these invariants under attack by an omniscient adversary, i.e. we assume that the adversary knows, for example, the topology of the network, where content is stored in the network, and the network protocols. We further assume that the adversary can attack a constant fraction of the peers in the network. In a simple model of attack, the attacked peers will simply drop out of the network(i.e. the fail-stop fault model). In a more complicated model, the attacked peers can collude, and try to disrupt the functioning of the network by sending false information to other peers (i.e. the Byzantine fault model). We will discuss strategies for handling both types of attack.

Related papers:

Previous Talks:

Drawing Area-Proportional Venn and Euler Diagrams
Stirling Chow
Sept. 12, DSB C 113, 2:30

We consider the problem of drawing Venn diagrams for which each region's area is proportional to some weight (e.g., population or percentage) assigned to that region. These area-proportional Venn diagrams have an enhanced ability over traditional Venn diagrams to visually convey information about data sets with interacting characteristics. We develop algorithms for drawing area-proportional Venn diagrams for any population distribution over two characteristics using circles and over three characteristics using rectangles and near-rectangular polygons; modifications of these algorithms are then presented for drawing the more general Euler diagrams.

We present results concerning which population distributions can be drawn using specific shapes. A program to aid further investigation of area-proportional Venn diagrams is also described.

A algorithmic characterisation of k-cop win graphs and digraphs
Gary MacGillivray
Sept. 19, DSB C 113, 2:30

Cops and Robber is a pursuit game usually played on a digraph G with no vertices of outdegree zero, which may have loops at some vertices. To start the game, each of the k>0 cops chooses a vertex of G, and then the robber chooses a vertex of G. The cops and the robber then move alternately, with the cops moving first. A move for the cops consists of each cop travelling along an arc from his present vertex to a neighbouring vertex. A move for the robber is defined analogously. When a vertex has a loop, a cop or the robber can use it to remain at his current position. The game is played with perfect information, so that the cops and the robber always know each other's location. The cops win the game if they can move so that one of them eventually catches -- occupies the same vertex as -- the robber. The robber wins if he can move never to be caught. A digraph is k-cop-win if k cops have a winning strategy, and robber-win otherwise. Historically, 1-cop-win digraphs have been called cop-win.

This game was first described for reflexive undirected graphs with one cop and one robber by Nowakowski and Winkler, and Quilliot, independently. Both papers characterise the cop-win graphs. Beyond the one-cop case, no characterisations are known. It is a long standing open problem to characterise the k-cop-win reflexive undirected graphs for k>1. Cops and robber games on digraphs have not received as much attention. The reflexive digraphs on which a single cop can always win have also not been characterised.

We describe an algorithmic characterisation of the cop-win finite digraphs. It is in terms of an auxiliary digraph constructible in polynomial time. We then describe how any k-cop game can be reduced to a 1-cop game, thus giving a characterisation of the k-cop-win digraphs. We conclude by describing how these methods can be applied to some variants of the game.

D-Trust: A Generalized Framework for Trust Modeling and Reasoning
Glenn Mahoney
Sept. 26, DSB C 113, 2:30

Suppose Alice receives a request from Bob, a previously unknown entity, to play a movie she owns and controls the rights to. Further suppose that Alice previously delegated the power to grant access, or delegate access granting power, to a number of other entities. How does Alice determine the amount of trust she has in Bob, so that she can decide whether to allow him to view the content?

The D-Trust system is a graph-based approach to constructing generalized trust representations and performing trust metric computations.

This presentation is focused on exposing current challenges in both representing and processing graph-based models of trust, with a specific focus a particular abstract trust model created by Dr. U. Maurer (Federal Institute of Technology, Zurich).

Algorithmic Combinatorial Game Theory
Allan Scott
Oct. 3, DSB C 113, 2:30

Sooner or later, everyone figures out that in tic-tac-toe the first player will lose only if he makes an error. In general, it's a natural question for any sufficiently deterministic game to ask whether either player has a winning strategy. This question often turns out to be very difficult, and answers for most games are not nearly as forthcoming as for the simple case of tic-tac-toe. Algorithmic combinatorial game theory studies the algorithms and complexity of answering this and related problems for combinatorial games. It also encompasses similar study of one-player games, or puzzles

This talk surveys a few techniques and many of the results relevant to this field. Specific topics include Sprague-Grundy theory, board games, and combinatorial puzzles.

Concentric Bilinski Diagrams and Geodesics
Jennifer Bruce, Maryville College
Oct. 10, DSB C 113, 2:30

A Bilinski diagram is a labeling of the sets of vertices and faces of a planar map with respect to a given vertex x, called its center, and the regional distance of the other vertices of the map from x. Bilinski diagrams are of particular interest when this labeling corresponds to a planar embedding wherein the sets of vertices at the same regional distance from the center induce a sequence of concentric circuits about the center. A concentric Bilinski diagram is one with this property. If all Bilinski diagrams of a map, i.e., for every choice of center, are concentric, then we say that the map is uniformly vertex-concentric. Bilinski diagrams with such concentric properties are not only aesthetically appealing but are also an essential tool in constructing geodetic paths, rays, and double rays (geodesics) in planar maps. We establish tight sufficient conditions for an infinite, locally finite planar map to be uniformly vertex-concentric, consider some necessary conditions for uniform concentricity, and develop algorithms for constructing geodesics in such graphs.

An Improvement of the IPO Pairwise Generation Strategy
Yong Du
Oct. 17, DSB C 113, 2:30

In software testing, we often need to test functions with a list of parameters, where each parameter has a set of possible input values. A test generation strategy is an approach to iterating the input values of each parameter and generating a set of test cases for the function under test. The most fundamental test generation strategy is the Cartesian product generation, where the test set generated is the Cartesian product of the sets of input values of all parameters. Pairwise generation is a more specific generation strategy. Given n sets D1,D2,...Dn, A pairwise generation strategy creates a test set S that is a subset of D1*D2*...*Dn, where for each element x in Di and y in Dj (i,j=1..n and i!=j), there is at least one test case in S with x as the ith element and y as the jth element. A good pairwise generation strategy aims at creating a pairwise test set as small as possible. One of the algorithms for generating pairwise test sets is called In-Parameter-Order (IPO). In this talk, I am going to introduce an improvement of IPO based on iterating arrangements of a sequence of integers with repetitions. I will show that the improved algorithm always generates smaller test sets than the original IPO algorithm.

Computing the Circumdiameter of a Strongly Connected Directed Graph
Lorraine Dame
Oct. 24, DSB C 113, 2:30

A directed graph is primitive if for some fixed positive integer m and each ordered pair of vertices (u,v), there exists a walk of length m from u to v. The exponent of a primitive directed graph is the smallest such m. One walk touches another in a directed graph if they have a vertex in common. The circumdiameter of a strongly connected directed graph is the maximum, over all ordered pairs of vertices (u,v), of the length of a shortest walk from u to v that touches cycles of all lengths. The circumdiameter can be used, together with the Frobenius-Schur index, to give an upper bound on the exponent of a primitive directed graph. A rudimentary method of computing the circumdiameter is presented in the hope of requesting ideas for a better algorithm.

Proud to be a Computer Geek
Daniel German
Oct. 31, 3:30
Human and Social Development Building (HSD), Room A 240.

Presented by the UVic Computer Science Course Union (CSCU)
Free Pizza. All are welcome.

Are you in love with your computer? Are you fascinated by computational problems? Do you keep refreshing slashdot every 5 minutes? Are you more aware about the fight for first place between Opterons vs. G5s than the World Series or the Stanley Cup? Do you carry enough "tools" in your backpack that one day it might bend you backwards? Would you rather spend a night in front of a computer than doing the pub crawl scene? Do you message or mail your SO rather using the telephone? Do you hope to get an iPod next Christmas? If you reply yes to most or all of these questions, you might be a computer geek, even if you don't know it.

Eric Schmidt, CEO of Google, believes that "geek" is a badge of honor. "Anyone in any business in any industry with any hope of thriving knows that he or she is utterly dependent on geeks -- those technical wizards who create great software and the powerful hardware that runs it." [Mitchell, 1999]. Look around, we are becoming totally dependent on computers and we (the geeks) have been given the honour and the responsibility of creating and maintaining the science and the technology necessary to run this infrastructure.

I'll talk about geekdoom, famous geeks, geek fashion, how to communicate to your non-geek friends, how to step out of the closet, and more importantly: why we should be proud of being computer geeks. And remember, at the end, and as the sayings goes in Silicon Valley "Geeks shall inherit the Earth".

Dr. German is part of the Software Engineering Lab at UVic and specializes in the creation of complex systems for the World-Wide Web. He received his Ph.D. in Computer Science at the University of Waterloo. Some of his other research interests are: Hypermedia and Web Engineering, Software Engineering in Collaborative Open Source Projects and Topics on XML databases.

CAG Schedule of Talks: Fall 2003 / maintained by Wendy Myrvold / / revised Dec. 10, 2003