COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2008

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.]

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

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.

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.

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.

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.

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.

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.

The classical Direct-Product Theorem for circuits says that if a Boolean function f: {0,1}ⁿ to {0,1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function f^k(x₁,...,x_k)=(f(x₁),...,f(x_k)) (where each x_i is in {0,1}ⁿ) 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.

Suppose G is an undirected graph on n vertices and m edges. A G-decomposition of K_v is a set {H₁, H₂, ..., H_t} of subgraphs of the complete graph K_v such that every edge belongs to exactly one H_i and each subgraph H_i 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 sum_{i=1 to n} (t_i * d_i) = v-1, such that sum_{i=1 to n} t_i = r, the common number of blocks through any vertex. We will show that given a graph G, K_v can be equireplicately G-decomposed for all sufficiently large integers v satisfying the necessary conditions.

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.]

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.

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).

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.

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.