CAG Schedule of Talks: Fall 2008

Schedule of Talks: Fall 2008

If you would like to give a talk in our seminar series, please contact Wendy Myrvold ( To get e-mail notification of our seminars and other events, you can subscribe to the CAG e-mail list at

Schedule for Talks:

Date Place Time Speaker Abbreviated Title
Mon. Sept. 8 10:00am Cle C 112 Patrick Fowler Molecular Conduction and the Characteristic Polynomial
Fri. Sept. 12 2:30pm DSB C 112 Reji Kumar Structure of the Set of all Minimal Dominating Functions of a Graph
Sept. 19 _ _ _ No CAG- CSC coffee house
Sept. 26 2:30pm ECS 660 Mahdad Khatirinejad Equiangular Lines: What We Know and What We Almost Know
Oct. 10 2:30pm ECS 660 Joergen Bang-Jensen Paths, Cycles and Strong Subdigraphs in Directed Graphs
Oct. 17 2:30pm DSB C 126 Dimitri Marinakis Topological Mapping with Weak Sensory Data
Oct. 24 2:30pm ECS 660 Sarada Herke Classes of Radial Trees
Oct. 31 2:30pm ECS 660 Valentine Kabanets Uniform Direct Product Theorems: Simplifed, Optimized, and Derandomized
Nov. 7 2:30pm ECS 660 Amanda Malloch On the Asymptotic Existence of Equireplicate Graph Designs
Nov. 14 2:30pm Cancelled _ Special Faculty of Engineering Meeting
Nov. 21 2:30pm ECS 660 David Kirkpatrick Input-thrifty Algorithms
Nov. 28 2:30pm ECS 660 Cobus Swarts Weak Near-Unanimity Functions
Dec. 3 3:30pm ECS 660 Frank McSherry Differentially Private Approximation Algorithms
Dec. 4 2:30pm DSB 103 Reinhard Illner Stuck in Traffic: The Mathematics of Traffic Flow on Freeways
Dec. 5 2:30pm DSB C 128 Brian Alspach Hamilton Paths in Vertex-transitive Graphs
Dec. 17 2:30pm ECS 128 Aaron Williams A New Approach to Generating Permutations with Repetitions
Dec. 18 3:30pm ECS 660 Funda Ergun On Distance to Monotonicity and Longest Increasing Subsequence of a Data Stream

Upcoming Talks

A New Approach to Generating Permutations with Repetitions
Aaron Williams
Wednesday Dec. 17, 2:30pm, ECS 128

Suppose you have a string of symbols with repetitions allowed (such as "victoria"). And suppose you are allowed to rearrange the string by choosing a symbol and moving it to the front of the string (such as "rvictoia"). Finally, suppose you'd like to go through all of the possible rearrangements exactly once. Is it always possible to do this? This talk shows that the answer is "yes", and furthermore for each rearrangement there is a simple rule that allows you to determine which symbol to move to the front. This leads to a highly-efficient loopless algorithm (each rearrangement is obtained in O(1)-time) that uses a constant number of additional variables (two additional pointers). Using the appropriate nomenclature, this is the first multiset permutation generation algorithm that is loopless and uses a constant number of additional variables. It is also the first prefix-shift Gray code for multiset permutations. As an added bonus, implementations of the algorithm are shorter than this Abstract.

[This is a practice talk for SODA 09.]

On Distance to Monotonicity and Longest Increasing Subsequence of a Data Stream
Funda Ergun, Computing Science, Simon Fraser University
Thursday Dec. 18, 3:30pm, ECS 660

In this work we consider problems related to the sortedness of a data stream. First we investigate the problem of estimating the distance to monotonicity; given a sequence of length n, we give a deterministic 2+epsilon streaming algorithm for estimating its distance to monotonicity in space O(1/epsilon^2 log^2 n). This improves over the randomized 4+epsilon approximation algorithm of Gopalan et al.

We then consider the problem of approximating the length of the longest increasing subsequence of an input stream of length n. We use techniques from multi-party communication complexity combined with a direct-sum approach to prove that any deterministic streaming algorithm that approximates the length of the longest increasing subsequence within 1+epsilon for an arbitrarily small constant requires at least Omega(sqrt(n)) space. This proves the conjecture of Gopalan et al.

This is joint work with Hossein Jowhari (SFU).

Previous Talks

Molecular Conduction and the Characteristic Polynomial
Patrick W. Fowler
Dept. of Chemistry
University of Sheffield
Monday Sept. 8, 10:00am, Cle C 115

Standard Huckel theory of conjugated hydrocarbons is equivalent to the problem of determining the spectrum of the adjacency matrix of the molecular graph. Ballistic conduction of an electron through a molecular electronic device is here modelled by an extension of this theory. Conductance varies strongly with the eigenvalue (the energy of the electron) and is determined by a combination of four characteristic polynomials: those of the molecular graph and three vertex-deleted sub-graphs. Closed-form results for many classes of chemical graphs follow.

Structure of the Set of all Minimal Dominating Functions of a Graph
Reji Kumar
BOYSCAST Fellow, DST, India
Friday Sept. 12, 2:30pm, DSB C 112

We start by discussing the basic ideas and results in the theory of dominating sets (DSs) and dominating functions (DFs), which is followed by the conditions of minimality and convexity. A subset S of the vertex set of the graph G=(V, E) is called a dominating set if each vertex not in S is adjacent to at least one vertex in S. The function f : V -> [0,1] is a dominating function, if the sum of the function values taken over the closed neighbourhood of every vertex is at least one. A DF f is a minimal DF (MDF) if the function values at the vertices cannot be reduced to get another DF. The convex combination of two dominating functions f and g is h = a.f + (1-a)g where 0 < a < 1. The concept of a basic minimal dominating function (BMDF) is fundamental to the study of the structure of the set of all MDFs of any graph. An MDF f is a basic MDF, if it cannot be expressed as the convex combination of two or more different MDFs. Many properties of BMDFs are given. A strong characterization of BMDF is known. Using this characterization, we are able to develop an algorithm to determine whether a given MDF is basic or not. There exists a bijection from the set of all MDFs to a subset of the unit n cube in the n dimensional Euclidean space where n is the number of vertices in the graph G. The image of this bijection is a simplicial complex, in general. As the image set and the set of all MDFs are isomorphic, we can understand the structure of the former set instead of studying the latter. The structure for some classes of graphs is given and finally we conclude with a few open problems.

Equiangular Lines: What We Know and What We Almost Know
Mahdad Khatirinejad
Department of Mathematics
Simon Fraser University
Friday September 26, 2:30pm, ECS 660

A set of lines is called equiangular if the angle between each pair is the same. We present a brief overview of the study of such a set of lines in the last 60 years. We also give the important properties of such a structure of lines in a general setting that includes real, complex and quaternionic spaces. There have been many attempts to construct equiangular set of lines. We discuss some of these methods and give a few (numerical and exact) examples.

Paths, Cycles and Strong Subdigraphs in Directed Graphs
Joergen Bang-Jensen
Head of section for Industrial Applications of Computer Science
Department of Mathematics and Computer Science
Southern Danish University
Friday Oct. 10, 2:30pm, ECS 660

We survey a number of recent results concerning paths, cycles or strong subdigraphs of digraphs. We illustrate proof techniques and also the richness of the topic by a giving number of results and open problems in the area. The talk is based on the second edition of the book "Digraphs: Theory, Algorithms and Applications", Bang-Jensen and Gutin, to be published by Springer in late 2008.

Topological Mapping with Weak Sensory Data
Dimitri Marinakis
Dept. of Computer Science
McGill University
Friday Oct. 17, 2:30pm, Room DSB C 126

In this presentation, we consider the exploration of topological environments by a robot with weak sensory capabilities. We assume only that the robot can recognize when it has reached a vertex, and can assign a cyclic ordering to the edges leaving a vertex with reference to the edge it arrived from. Given this limited sensing capability, and without the use of any markers or additional information, we will show that the construction of a topological map is still feasible. This is accomplished through both the exploration strategy which is designed to reveal model inconsistencies and by a search process that maintains a bounded set of believable world models throughout the exploration process. Plausible models are selected through the use of a ranking heuristic function based on the principle of Occam's Razor. We conclude with numerical simulations demonstrating the performance of the algorithm.

Classes of Radial Trees
Sarada Herke

Friday Oct. 24, 2:30pm, ECS 660

Suppose that in order to communicate in a network, certain nodes are given transmitters. In a domination problem, the transmitters can communicate to nodes at distance one away. We consider the situation in which the transmitters can be made more powerful, but with an additional cost. We wish to communicate to the entire network with minimumm total cost. This is modeled by a broadcast on a graph G in which every vertex is assigned a non-negative integer value at most the diameter of G. The broadcast number of a graph is the minimum cost of a dominating broadcast. This number is bounded above by the radius of the graph, as well as by the domination number. Graphs for which the broadcast number is equal to the domination number are called radial. We discuss the relationship between the broadcast number of a graph and of its spanning trees. We then prove some results about classes of radial trees, which begins to solve the problem of characterizing them completely.

Uniform Direct Product Theorems:
Simplifed, Optimized, and Derandomized
Valentine Kabanets
Dept. of Computer Science, Simon Fraser University
Friday Oct. 31, 2:30p, ECS 660

The classical Direct-Product Theorem for circuits says that if a Boolean function f: {0,1}n to {0,1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function fk(x1,...,xk)=(f(x1),...,f(xk)) (where each xi is in {0,1}n) is significantly harder to compute on average by slightly smaller circuits.

We prove a fully uniform version of the Direct-Product Theorem with information-theoretically optimal parameters, up to constant factors. Our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct-product codes (encoding a function by its values on all k-tuples) with optimal parameters. We generalize it to a family of "derandomized" direct-product codes, which we call intersection codes, where the encoding provides values of the function only on a subfamily of k-tuples. The quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. As a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of k) increase in the input length. Finally, this general setting naturally allows the decoding of concatenated codes, which further yields nearly optimal derandomized amplification.

This is joint work with Russell Impagliazzo, Ragesh Jaiswal, and Avi Wigderson.

On the Asymptotic Existence of Equireplicate Graph Designs
Amanda Malloch
Friday Nov. 7, 2:30pm, ECS 660

Suppose G is an undirected graph on n vertices and m edges. A G-decomposition of Kv is a set {H1, H2, ..., Ht} of subgraphs of the complete graph Kv such that every edge belongs to exactly one Hi and each subgraph Hi is isomorphic to the given graph G; this is equivalent to a graph design with lambda=1. A G-decomposition is called equireplicate when each vertex of the complete graph appears in the same number r of subgraphs of the decomposition. In order to have an equireplicate graph decomposition we require v*(v-1) congruent to 0 (mod 2m) and that there is a nonnegative integer combination of degrees equal to v-1, say sumi=1 to n (ti * di) = v-1, such that sumi=1 to n ti = r, the common number of blocks through any vertex. We will show that given a graph G, Kv can be equireplicately G-decomposed for all sufficiently large integers v satisfying the necessary conditions.

Input-thrifty Algorithms
David Kirkpatrick
Dept. of Computer Science, UBC
Friday Nov. 21, 2:30pm, ECS 660

In many natural computational settings the inputs are (re)presented hierarchically; a coarse approximation is available at low cost but if you want more information (precision) you must pay in proportion. Sometimes, it becomes evident after the fact that a computation could have reached its desired conclusion with much less (collective) input. This reveals a potential source of computational saving in situations where the cost of acquiring data (or navigating data structures) is dominant. An algorithm is said to be input-thrifty if the total amount of input that it examines for each problem instance is somehow bounded by the amount of input that is actually required to certify a solution to that instance.

The objective of this talk is to explore the concept of input-thriftiness in the context of geometric algorithms through concrete instances of the following: Let S be a sequence of n points whose coordinates are given initially only to some limited precision, with additional precision available at some additional cost per bit. Suppose that we wish to determine some property P of S, for example, "which point of S is extreme in some specified direction", or "are the red points in S linearly separable from the blue points in S". For some problem instances, many bits of all (or most) of the points need to be determined in order to establish P; for other instances P can be established with the knowledge of only a relatively small (total) number of bits. We would like to design algorithms whose cost (number of bits examined) adapts to the intrinsic cost (shortest computation or "proof" of the property P) for a given instance. This talk describes some results concerning several very basic questions of this type, focusing primarily on point sets in 1-d (where, of course, geometry is not much of an issue). In particular, for the separability question in 1-d, we define a notion of intrinsic cost c(I) of an instance (input set) I and show that
(i) any algorithm can be forced to examine c(I) bits in the worst case (over all presentations of I as an input sequence), even if I (but not its presentation) is known,
(ii) there is an algorithm that examines only O(c(I)log(c(I))) bits in the worst case, even if I is not known, and
(iii) any algorithm can be forced to examine O(c(I)log(c(I))) bits in the worst case (over all presentations of inputs with intrinsic cost c(I)), even if c(I) is known.

[Based on joint work with Raimund Seidel, Univ. des Saarlandes.]

Weak Near-Unanimity Functions
Cobus Swarts
Friday Nov. 28, 2:30pm, ECS 660

If H is a digraph, the problem of deciding whether a given digraph G has a homomorphism to H is known as the H-colouring problem. During the last decade a new approach to studying the complexity of the H-colouring problem has emerged. This approach focuses attention on so-called weak near-unanimity functions (WNUFs). A conjecture of Bulatov, Jeavons and Krokhin states that if a digraph H has a WNUF, then the H-colouring problem is in P, otherwise (if it doesn't have one) H-colouring is NP-complete (the latter part is already known).

In this talk we will see that some well-known polynomial cases all have WNUFs. On the other hand we will show that there are some interesting parallels between traditional NP-completeness proofs (for H-colouring) and proofs for the non-existence of WNUFs. This lends some support to the conjecture that WNUFs are the right measure for the complexity of H-colouring.

This is joint work with Gary MacGillivray.

Differentially Private Approximation Algorithms
Frank McSherry
Microsoft Research Silicon Valley Lab
Wednesday Dec. 3, 3:30pm, ECS 660

We consider the problem of designing approximation algorithms for discrete optimization problems over private data sets, in the framework of differential privacy (which formalizes the idea of protecting the privacy of individual input elements). Our results show that for several commonly studied combinatorial optimization problems, it is possible to release approximately optimal solutions while preserving differential privacy; this is true even in cases where it is impossible under cryptographic definitions of privacy to release even approximations to the value of the optimal solution.

In this [self contained] talk, we will start with the definition of differential privacy, and motivate its applications in statistical settings. We then transport the definition to the vertex cover problem, where some set of edges must each be covered by a vertex. Treating the set of edges as sensitive (the presence or absence of each edge should not be disclosed) we show a factor two approximation to the value, and a factor (2 + 16/epsilon) approximate solution (where epsilon is the differential privacy parameter, controlling the amount of information disclosure). We also present a simple lower bound arguing that an Omega(1/epsilon) factor dependence is natural and necessary.

Time permitting, we will survey several other approximation problems and algorithms, without going into the details of the analyses.

This work is joint with Anupam Gupta, Katrina Ligett, Aaron Roth (all at CMU) and Kunal Talwar (at MSR-SVC).

Stuck in Traffic: The Mathematics of Traffic Flow on Freeways
Reinhard Illner
Thursday, Dec. 4, 2:30-3:30pm, DSB 103
Math Dept. Social to follow 3:30-5:00pm (Everyone is welcome).

Everybody has experienced the agony and frustration of being stuck in a traffic jam. Such jams and (closely related) stop-and-go waves are not only a major nuisance, they are also the cause of much time and energy waste. It is therefore little wonder that scientists have studied the problem of traffic flow and control ever since heavy car traffic has been a reality, beginning with studies by General Motors in the 1950s. This talk will be an introduction into the field as well as a research presentation from the point of view of a mathematical physicist with expertise in kinetic partial differential equations. We will begin with traditional microscopic follow-the-leader models, introduce and discuss the concept of a fundamental diagram and progress via kinetic models to systems of partial differential equations, including the nonlocalities and reaction time issues characteristic for traffic. Conceptual causes for the structure of fundamental diagrams and the instabilities leading to stop-and-go waves will be presented.

Hamilton Paths in Vertex-transitive Graphs
Brian Alspach
School of Mathematical and Physical Sciences
University of Newcastle
Friday Dec. 5, 2:30pm, Room DSB C 128

A graph is Hamilton-connected if for any two vertices u and v there is a Hamilton path whose terminal vertices are u and v. Similarly, a bipartite graph is Hamilton-laceable if for any two vertices u and v from distinct parts there is a Hamilton path with terminal vertices u and v. We present a survey of what is known about Hamilton-connected and Hamilton-laceable vertex-transitive graphs.

CAG Schedule of Talks: Fall 2008 / maintained by Wendy Myrvold / / revised Nov. 24, 2008