October 1, 2002, Tuesday, 5:00 PM, Green Street Coffee House
Informal meeting with Prof. Vijay Vazirani

Prof. Vijay Vazirani (Professor, College of Computing, Georgia Tech) will be visiting the CS department as part of the Distinguished Lecturer series. We have scheduled an informal meeting with him. Please feel free to come by and chat.

Prof. Vazirani's research interests include: design of efficient exact and approximation algorithms, algorithmic game theory, computational complexity theory, cryptography, algorithmic problems in coding theory. He is the author of the recent book "Approximation Algorithms" published by Springer-Verlag.

For an announcement of his talk in the Computer Science department, please visit the CS calendar.

December 6, 2000, Wednesday, 4:00 PM, Green Street coffee house
Thyagarajan Nandagopal (Thyaga) (thyagu@timely.crhc.uiuc.edu).

Scheduling in multi-hop wireless networks

A multi-hop wireless network can be represented by a planar graph, in which a mobile host is represented by a node. Two nodes within range of each other can communicate, and such a communication between a pair of nodes is called a flow.

At any given instant, multiple flows can be present in this graph. Thus, the throughput (or the amount of information successfully transmitted) per flow can depend on the topology of the graph. An additional constraint can be imposed on this graph by assuming that the topology of the graph will change due to the movement of the nodes. (We can assume initially that any ongoing transmissions, or flows, will not be disturbed as a result).

With this changing topology, there could be no lower bound on the throughput that a node can attain. We want to devise a distributed algorithm that will determine how a node tries to transmit, and thus, impose a lower bound on the throughput of every node in this graph.

The initial cut will be to look at the problem without assuming node mobility, and try to characterize the bounds on throughput as a function of the topological parameters. The next step will be to devise a scheduler (which determines when a node should transmit), that acts locally, which gives desirable bounds on the throughput.

I will give examples to describe this problem more clearly. I will also describe existing results in this subject, that are relevant to the discussion.

September 28, 2000, Thursday, 5:30 PM, Green Street coffee house
Hemanshu Kaul (hkaul@math.uiuc.edu).

Queue number of planar graphs:

Let G be an undirected, simple graph. A k-queue layout of G consists of a total order on its vertex set V, along with an assignment of each edge in its edge set E to one of the queues q₁, q₂, ..., q_k. Each queue operates as follows:

The vertices are scanned in ascending order (according to order on V). When a vertex v is encoutered, any edges assigned to the queue that have v as their right endpoint must be at the front of that queue so that they can be removed. Any edges assigned to the queue that have v as their left endpoint are placed at the back of that queue in ascending order of their right vertices.

The queue number of a graph is the smallest k such that G has k-queue layout. The freedom to choose a total order on V and an assignment of edges to minimum number of queues is the essence of the queue layout problem.

The stack number of a graph can be similarly defined. This is equivalent to the problem of book embeddings of graphs and so the stack number is the same as the page number of a graph.

The stack number of planar graphs was shown be bounded above by 4 by Yannakakis in 1986. But the corresponding question for the queue number of planar graphs is still open. Is there an upper bound or is it unbounded?

I will give examples to clarify the definitions and describe a few basic relevant results. And also give some motivation from VLSI design.

September 6, 2000, Wednesday, 5:30 PM, Green Street coffee house
Radhika Ramamurthi (ramamurt@math.uiuc.edu).

Problems arising from end-to-end communication in memoryless networks:

Micah Adler and Faith Fich have a recent paper on the complexity of end-to-end communication in an unreliable network (edges may fail). The measure of performance considered is the size of the header on a packet and the paper gives lower and upper bounds on this for two problems: the problem of sending one message from a sender to a reciever and the problem of sending a sequence of messages from a sender to a receiver.

I will focus more on the graph theoretic questions that arise in the paper. In particular, for the second, harder problem, the paper gives lower bounds in terms of an interesting graph theoretic parameter, defined as follows. Let G be an undirected graph with distinguished nodes S and R. Let \pi be a total ordering of the edges. A path from S to R is said to be \pi-consistent if the edges along this path are consistent with their order in \pi. Let \rho(G) be the maximum over all possible total orderings, \pi of the number of \pi-consistent paths.

The authors give some constructions for lower bounds on \rho for specific classes of graphs and have several interesting conjectures that will be presented. I believe that there are several interesting questions that are open and just need some new ideas, which will hopefully come out of our discussion.

March 1, 2000, Wednesday, 5:00 PM, Green Street coffee house
Tibor Szabo (tszabo@math.uiuc.edu).

Let L be a set of s positive integers. For i=1,...,m, let A_i and B_i be subsets of {1,...,n} with properties:

1. A_i is disjoint from B_i for every i
2. For any distinct i and j the cardinality of the intersection of A_i and B_j is in L.

Conjecture (Snevily): m is at most (n choose s).

If true, the conjecture is tight. It is known to be true for s=1. There are known related results, like the theorems of Ray-Chaudhuri and Wilson, Frankl and Wilson, or Bollobas. (You can read about these in the (not yet published) book of Babai and Frankl: Linear algebra methods in combinatorics.) If you need some further info, contact me. (tszabo@math.uiuc.edu)

February 2, 2000, Wednesday, 5:00 PM, Green Street coffee house
Mitch Harris (maharri@uiuc.edu), Shripad Thite (thite@uiuc.edu)

We will talk about the problem of distinct configurations of a set of points.

We will present our definition of what we consider intuitively to be distinct configurations. We will try to define the notion of a "signature" for each configuration. We expect that a group discussion will help to either substantiate or not our opinion that this definition indeed distinguishes between what we would consider as distinct configurations.

Among the issues that arise are the problem of counting the number of such configurations, and the complexity of computing the signature of a given embedding of the points. We will consider generalizations of this concept but the intent is to give a characterization for configurations in the Euclidean plane (which we expect will be give us enough to talk about).

We were motivated to think about this problem because similar issues are/could be involved in analyzing the average-case complexity of computational geometry algorithms, and in computational learning theory.

November 30, 1999, Tuesday, 5:30 PM, Green Street coffee house
Tanya Berger-Wolf (tanyabw@uiuc.edu)

I would like to discuss the following graph problem:
Given a graph and m < |V|, which induced subgraphs of order m have the
smallest bandwidth/bandwidth sum. Specifically, when G is a Hamming graph
or a grid graph.

Some definitions:

* Hamming Graph is the cartesian product of two or more cliques.
* Grid Graph is the cartesian product of two or more paths.
* Vertex labeling of a graph G(V,E) is a one-to-one function
        f:V(G)->{1,...,|V(G)|}.
* Bandwidth} B(G) of a graph G(V,E) is the minimum over all labelings f of the maximum label difference over an edge:
        min_{f}\max_{(u,v)\in E(G)}|f(u)-f(v)|.
* Wirelength, or Bandwidth Sum,  L(G) of a graph G(V,E) is the minimum over all labelings f of the sum of the label differences over edges:
        min_{f}\sum_{(u,v)\in E(G)}{|f(u)-f(v)|}.

This problem is wide open and virtually nothing has been done in this are. It arises in the context of multichannel communication, specifically, channel coding. However, no knowledge of that area is needed.

The problem can be viewed as another discrete version of the Isoperimetric problem. The original Isoperimetric Problem, known already to the ancient Greeks, is the following:
        given all shapes with the same perimeter (isoperimetric), find
        the one with the largest area
The answer, of course, is circle. There are many variations of the problem in mathematical physics, and since the mid 60's the problem has creeped into the graph theory.

For information on graphs in general see
        West, D.B., Introduction to Graph Theory, Prentice Hall, 1996.
For a survey of graph bandwidth see
        Chinn,P.Z., J.Chvatalova, A.K.Dewdney, and N.E.Gibbs,
        ``The bandwidth problem for graphs and matrices - a survey'',
        Journal of Graph Theory, 6 (1982), 223--254.
For information on continuos Isoperimetric Problem see
        Polya,G. and G.Szego, Isoperimetric Inequalities in
        Mathematical Physics. Annals of Mathematical Studies,
        27, Princeton University Press, 1951.
For a survey of one of the graph isoperimetric problems see
        Bezrukov,S.L., ``Edge isoperimetric problem on graphs'',
        Graph Theory and Combinatorial Biology, Bolyai Society
        Mathematical Studies 7, L.Lovasz, A. Gyarfas, G.O.H. Katona, A.
        Recski, L. Szekely eds., Budapest 1999, 157--197.

November 16, 1999, Tuesday, 5:30 PM, Green Street coffee house
Organizational meeting.

Summary of discussion:
We agreed that for the meetings to be interesting, we should focus on presenting and discussing open problems. For each meeting we hope to have a volunteer who will have a/some interesting problems they wish to discuss. Since we have a diverse group of people, we decided at, at least initially, the volunteer will send out a brief email about the problem(s) to be discussed, as well as a short reference list so that people are aware of the area that the problem is coming from. To spare people the necessity of maintaing a mailing list, the messages will be posted to the newsgroup uiuc.cs.theory. We ask that volunteers initially email their ideas to ramamurt@math.uiuc.edu and thite@uiuc.edu.

• Radhika Ramamurthi (ramamurt@uiuc.edu)
• Shripad Thite (thite@uiuc.edu)

• CS Theory Seminar
• Graph Theory and Combinatorics Seminar

Webmaster: Shripad Thite (thite@uiuc.edu)
Last modified: Sun Sep 8 18:28:02 CDT 2002