|
UVM Applied Combinatorics Seminars |
UVM
Applied Combinatorics Seminar, Spring 2001
Tuesdays, 8:30 to 9:20 am.
For
many years the Math and CS departments at UVM have conducted weekly discrete
math/combinatorics/computer science seminars.
This spring, the focus of the seminars will be on applications of
combinatorics. Our goal is to bring
together academic and industry researchers for a productive exchange of the
theory and applications of combinatorics.
Examples
of areas of application in computer science include data mining, storage in disk
arrays, the design of parallel algorithms, software testing, database
formatting, file organization, the analysis of algorithms, the design of
networks, and interconnection strategies for networks.
Applications in information theory include wireless networking (the
design of radio and satellite networks), internet communication protocols,
signal processing, timing analysis and multiaccess communications. Combinatorial
techniques are also used to address problems involving scheduling, packing, data
compression, and book-width and fault-tolerant processing.
In molecular biology/biotechnology, applications include mapping genomes,
forming the clone libraries, and designing chips for DNA probes.
In the past year and a half, new applications have even come out of Wall
Street; (t,m,s)-nets are being used in numerical integration problems in
financial mathematics.
A wide range of combinatorial techniques and theory is available for such applications. In recent years a great deal of work has been done on developing new constructions, and a powerful theory of combinatorial constructions is emerging. These applications come at a time when the power of combinatorial constructions combined with computational methods is beginning to be fully realized. The problems appearing in these applications are providing us with new and challenging existence questions as well as surprising applications of familiar and long studied combinatorial techniques.
These seminars are open to the public. No registration or fees are required to attend.
Both industry and academic users of combinatorial techniques are invited to share their own particular interests by conducting one of the seminars. If you have an industry problem or other application that you are working with, this is an opportunity to present it to group of people who may be able to offer some approaches to it using newly developed techniques. If you are a mathematician or computer scientist, this is a chance to hear about interesting problems and to share your techniques with people who might have a real need for them.
The
format of the seminars may be presentations, workshops, background followed by
discussion, or even brain-storming sessions, at the discretion of the individual
speakers. If you are interested in
conducting a session, please contact the organizers at joellis@emba.uvm.edu
with a brief description of what you would like to talk about.
The seminars generally meet in the conference room of the UVM Math Department at 16 Colchester Avenue, Burlington, VT. Check specific abstracts for any possible location/time changes.
Time: 8:30 to 9:20 am on the following Tuesdays (click on the date to go to that day's abstract):
Links to on-line slides and other resources from the various talks (if available) are provided at the end of each abstract.
1/23, 1/30, 2/6, 2/13, 2/20, 3/13, 3/27, 4/3, 4/10, 4/17, 4/24, 5/1.
Date: January 23, 2001
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Applications of Combinatorial Designs in Communications and Networking
Speaker: Charles J. Colbourn. Computer Science, University of Vermont
Abstract:
Some problems arising in resource allocation and multiple access for
communications networks are described. They share the feature that
a major part of their solution involves combinatorial designs.
We describe basic properties of the designs used. Then we outline the
applications problems, and describe how designs arise in their
solution. We emphasize the problem features that lead to the
involvement of combinatorial designs.
Click here for slides and even a video of Charlie's talk as presented at the Mathematical Sciences Research Institute
Date: January 30, 2001
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Scheduling Tournaments and Leagues
Speaker: Jeff Dinitz. Mathematics, University of Vermont
Abstract:
The talk will survey some of the problems that come up when you have
to schedule a tournament or a league. Although there are standard
solutions that go by the name ``combinatorial designs,'' the real
world (e.g., your mother's golf tournament) often presents additional
considerations and constraints that lead to interesting problems.
The speaker has recently been involved in constructing a schedule for
a major professional sports league and will describe some of the
issues that arose in working on this problem for that league. The
talk will also include a discussion of the mathematics underlying
certain league schedules. The speaker promises that this talk will be
as X-treme as a math talk gets.
Click here for slides and even a video of Jeff's talk as presented at the Mathematical Sciences Research Institute
Here is the link to Michael Trick's sports scheduling resource page (including software packages) that Jeff mentioned in his talk: http://mat.gsia.cmu.edu/sports/
And here is a link to the NY Times article on the scheduling of the XFL (you have to register, but it is free)
http://www.nytimes.com/2001/02/03/arts/03MATH.html?ex=982302885&ei=1&en=a102bd97
Date: February 6, 2001
Location: Conference Room, Math department, 16 Colchester Ave
Title: Balanced Schedules of Round Robin Tournaments
Speaker: Dalibor Froncek, UVM
Abstract:
One-factorizations
of complete graphs are often used for scheduling round robin tournaments. There
are several measures of “fairness” of a schedule. Two of them, that are
considered to be very important by most of European soccer associations, will be
discussed. Namely, the balance of the home and away games and the carry-over
effect. It
is said that a team I receives a carry-over effect due to a team J if there is a game J–L
in the round (k–1) and a game I–L
in the round k. It can make a
significant difference to receive the carry-over effect 2n–3 times due either to the best team of the league or to a weak
one.
Some
examples of new schedules will be shown. In particular, schedules constructed by
the author and Mariusz Meszka for the Czech National Hockey League and
the Czech National Basketball League.
Here is a link to the NY Times article on the scheduling of the XFL (you have to register, but it is free)
http://www.nytimes.com/2001/02/03/arts/03MATH.html?ex=982302885&ei=1&en=a102bd97
Date: February 13, 2001
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Design-Specific Circuit Element Selection
Speakers: David Hathaway, John Cohn, Arun Venkataraman, IBM
Abstract:
A typical digital design is composed of a set of logic
elements i.e., gates. The specific gates used in a design are
typically constrained by area and performance targets and by a target
library of gates. The library of gates comprises of a set of basic
logic elements with each element having many versions, or power
levels, these versions being distinguished by their unique electrical
characteristics like input capacitance, drive capability, power
consumption, and required silicon area. Generally a larger version
will consume more power and will be faster, but will also have a
higher input capacitance, causing the circuits driving it to be
slower. Current design synthesis methodologies require that all
versions of the elements that make up a design to be "qualified"
through extensive simulations, an expensive process. The library of
elements is pre-qualified and turn-around-times of designs are
therefore improved if only library elements are used to realize the
design.
In optimizing a design, we wish to reduce its area and power
consumption while at the same time minimizing the delay along its
slowest path. The selection of the proper circuit element version to
use to implement any given gate in the design depends on the timing
requirements of paths passing through it and the effect its input
capacitance load has on other circuits. When a predefined library of
discrete elements is used, a variety of local heuristics are typically
used to iteratively adjust the power level of various gates.
Experience has showed this to be overconstraining as the versions in
the library are small in number and do not reflect the optimum
electrical characteristics required by a particular critical path
element. The result invariably is the generation of suboptimal results
(often violating constraints like low power and minimum area) which
might not satisfy the original design specs.
A newer approach instead treats the circuit element size as
one or more continuous variables and focuses on determining the
optimal size for each gate in the design in order to meet performance
targets while satisfying other secondary constraints. This can be
done, for example, using a constrained non-linear optimization
package. A solution will specify a set of independent size
variables. A circuit is composed of a number of different transistors,
and if all of these transistors are scaled together, the "size" can be
a single scalar quantity. Better results can be achieved by
independently sizing each transistor in the circuit element. In
general, these optimization techniques will independently yield a
version for each gate in the design, Because the number of independent
parameters (e.g., transistor sizes) can be large, the space of
possible versions is also large, as is the number of unique versions
generated by such optimization techniques. Unfortunately, these
generated versions still require the very time consuming and expensive
process of qualification. To reduce this cost, there is considerable
interest in studying if some form of "re-grouping" of similar versions
into a single "equivalent" version will yield a smaller set of
elements requiring qualification. This is problem can be formally
stated as follows - Given a set of versions and a set of constraints
like delay slacks and a range of feasible sizes, find the minimum
number of new versions that cover all original versions. This is a
combinatorial optimization problem whose solution will in turn help
create the fewest required element versions that need to be qualified
without losing too much in terms of the optimality of the
solution. Complications include ensuring that the re-grouped set of
versions continuing to satisfy the problem constraints.
Here is a PDF file of the overheads: Library Clustering Overheads
On another topic-- There was some discussion after this talk about Binary Decision Diagrams, and David Hathaway provided the following link from a course he taught:
http://www.emba.uvm.edu/~davidh/ee295-sp00/
February lectures cover material related to Binary Decision Diagrams.
Date:
Tuesday, February 20
Time: 8:30-9:20 a.m.
Location: Conference Room, Math department, 16 Colchester Ave
Title: Inverter minimization in a logic network
Speaker: David Hathaway, IBM
Abstract:
Digital
logic networks are typically composed of interconnected gates, such
as
AND, OR, NAND, and NOR gates. Inverters may also be present in the
network,
but are in some sense "overhead", as they do not compute new
information,
but instead merely change the polarity of the signal carrying
the
information. Inverters at gate outputs may be removed by changing
between
NAND and AND gates or between NOR and OR gates, Similarly,
application
of DeMorgen's law allows removal of inverters at gate inputs by
changing
between AND and NOR gates or between NAND and OR gates. Signals
with
multiple fanouts, however, may yield situations in which inverters may
not
be removed. A graph can be derived
from the original logic network
graph
which can be used to find cases where inverters may not be removed.
The
inverter removal problem can also be cast as a covering problem on the
fundamental
cycles of this derived graph. The derived graph can be extended
to
the more general case where the network includes other elements such as
XOR
gates, adders, multiplexors, and in which AND, NAND, OR and NOR gates
do
not have equal cost. This complicates the covering problem. Suggestions
for
more efficient solution of the covering problem(s) will be welcome.
Here is a PDF file of the overheads: Inverter Removal Overheads
Date: Tuesday, March 13
Time: 8:00-9:30 or so. Note extended time
Location: IBM, Willison Site. Note change of location--Click here for directions
(Links to Department sites--click here)
Title: Making Connections—Initiating Collaborative Efforts Between Industry and Academia.
Speakers: A mix of people from both UVM and IBM
Abstract:
The goal for today’s seminar is to provide a forum where participants have the opportunity to make initial contact and explore the possibility of productive collaboration with one another.
Speakers from UVM will
briefly describe some of the academic resources available, such as personnel and
areas of expertise. They will also
mention some of the ways that the mathematics can be used to get optimal or
near-optimal solutions to industry problems, and describe some of the
collaboration and consulting that has been done in the past.
Speakers from IBM will describe their professional interests, past collaborative work with the academic community, and potential areas for further joint work.
These talks will be very brief and
to the point, serving as a springboards for further discussion.
There will be some time after the
presentations for informal socialization. You
may find someone who is very interested in your work because of the possible
connections to their own—the only way to find out is to come and try. Graduate students, faculty and engineers are especially
encouraged to attend, as this is potentially a source exciting projects.
People from other industries,
schools, and endeavors besides UVM and IBM are most welcome—the broader the
range of experience, the better the aggregate resources.
Math/Stats: http://www.emba.uvm.edu/EM/Math/index.html
Computer Science: http://www.cs.uvm.edu/
Date: Tuesday, March 27
Time: 8:00-9:30 or so. Note extended time
Location: IBM, Willison Site, LOBBY. Note change of location--Click here for directions
(Links to Department sites--click here)
Title: Making Connections—Initiating Collaborative Efforts Between Industry and Academia.
Speakers:
Sambasivan Narayan (IBM),
Dalibor Froncek (UVM), Peter
Osler (IBM) (click on name for individual abstracts)
Abstract: This will be a continuation of the introductory seminar of March 13th . There will be brief (10 minute) talks by three speakers to introduce some problems.
These will be followed by a
workshop where all participants can split into small groups to discuss details
and possible approaches to various problems.
This part of the seminar is open to everyone/every problem—not just
those presented in the talks.
Again the goal for today’s
seminar is to provide a forum where participants have the opportunity to make
initial contact and explore the possibility of productive collaboration with one
another.
The workshop will also provide a
venue for informal discussion and an opportunity to hear about new problems and
techniques. You may find someone
who is very interested in your work because of the possible connections to their
own—the only way to find out is to come and try.
Graduate students, faculty and engineers are especially encouraged to
attend, as this is potentially a source exciting projects.
People from other industries, schools, and endeavors besides UVM and IBM are most welcome—the broader the range of experience, the better the aggregate resources.
Individual abstracts:
Timing characterization of logic blocks
The design of digital circuits uses certain primitive blocks known as
"standard cells". These cells implement various logic functions like NOT
(inverting), OR (binary addition) and XOR for various number of inputs
ranging from one to eight or nine. These cells are in turn made up of
basic electrical elements known as "transistors". These transistors come
in different sizes and have highly non-linear functions governing their
behavior. In order to simplify the design of complex digital logic, these
cells are pre-characterized for various parameters. One such parameter is
the time it takes for a change at the input to reflect as a change at the
output of the cell, known as the "timing delay". This delay depends upon
the values of the inputs, the "topology" of the cell (the way the
constituent transistors are connected together) and the environment of the
cell, known as the "operating conditions". The operating conditions
include the temperature, strength of the power supply ... etc. Hence, we
settle on two measurements of this delay, known as the "early-mode" and
the "late-mode" timing delay. These are the shortest and longest time it
takes for a change at the input to change the output, at any operating
condition and for any set of input values. For a given operating condition
and set of inputs, the delay is calculated by running a simulator, but it
is impractical to run the simulator for every possible operating condition
and input. Our goal is to come up with a subset of the inputs and the
operating conditions that can then be simulated to determine the delays.
Graph Decomposition
I will give a brief introduction to graph decomposition.
A decomposition of a graph G into subgraphs is a separation of its edges
so that each edge of G is contained in exactly one of the subgraphs.
Typically, decompositions of special graphs (e.g. where there is an edge
between every pair of vertices) into identical subgraphs are of particular
interest. I will give some examples
of these decompositions.
DAG Heuristic Analysis
We
have a dag, with weighted edges. The
edges correspond
to connections in a circuit. The
nodes correspond to
the places where the connections in the circuit are attached
to circuit primitives. The edge weights correspond
to delays in the circuit. By
analyzing the DAG, we can
generate an ordered list of paths, from input to output, where
the list is ordered from longest to shortest.
Call this list
a 'slack report'.
Now, we can use the slack report to guide optimization heuristics.
The optimization heuristics modify the circuit, working on
the path(s) at the top of the list. Optimizations
to the circuit
are automatically and incrementally reflected in the dag.
The optimization heuristics can significantly change the weights
along the edges of the DAG, and can change the edges, but
never change the semantics of the circuit.
We have a large set of heuristics. The
heuristics
are applied to 'points' in the circuit (the nodes of the DAG).
Some heuristics provide the most value when applied early
in the optimization process, some when applied late.
Some heuristics make sense to be applied in combination
with others, some don't.
The heuristics are applied by something called a driver.
A driver takes parametrically a list of heuristics,
and a definition of the set of points to which the heuristics
are to be applied. The driver has a
built in mechanism
for applying the heuristics to the points.
There are three classes of drivers:
1. Next<blah> where
<blah> can be 'Net', 'Pin', or 'Box'
Only one heuristic
allowed in heuristic list. Apply
heuristic to all
objects of the specified type, order
of objects is
unspecified, heuristic is applied without
recourse.
2. Critical:
Arbitrary number of heuristics in heuristic list.
List of points can be
fairly complex: top 100 worst slack
points,
points in top 10 worst
paths, points in top 10 worst paths not
to exceed 100 points,
etc.
For each point
For each
heuristic
apply
heuristic to point
measure
cost/benefit
record
heuristic, cost/benefit, point
undo
heuristic
roF
roF
select most
advantageous cost/benefit from list
apply associated
heuristic to point
3. Quick:
Heuristic list and list of points same as 'Critical'.
For each point
For each
heuristic
apply
heuristic to point
measure
cost/benefit
record
heuristic, cost/benefit, point
undo
heuristic
roF
select most advantageous cost/benefit
from list
apply
associated heuristic to point
roF
Now, during 'Critical', an immense amount of time is spent filling in the
point X heuristic cross-product cost-benefit matrix.
We'd really
like to do this in a more efficient manner.
What does 'Critical' really do? Well,
name the state of the circuit/DAG
when 'Critical' is called 'the original state'.
Critical examines the
original state to determine the list of points.
Then, for each point,
each heuristic is applied in turn, and its cost/benefit is measured.
Then the original state is re-established before the application of
the next heuristic to the same point, or the execution of the entire
heuristic list to the next point, occurs.
Well, the fact that the original state of the circuit/DAG is restored
is important if the optimization of point N would affect the optimization
of point N+1. But what if the
optimization of point N doesn't affect the
optimization of point N+100? In
that situation, with no loss of
generality,
we could run critical in a fashion such that we generate two
point X heuristic cross-product cost-benefit matrices, one for all points
whose optimization affects point N (and conversely, those points who are
affected when point N gets optimized), and another for all points
whose optmization affects point N+100. Each
of these matrices can
independently be evaluated to choose the best cost-benefit heuristic/point,
and both solutions can be applied.
So the problem lies in determining, from the list of points and the DAG,
the number and composition of the sub-sets of the list of points whose
optimizations
don't interfere. In other words,
any heuristic applied to
any of the points in a given subset will not affect the timing of
any of the points in any other subset.
Date:
Tuesday, April 3
Time: 8:30-9:20 a.m.
Location: Conference Room, Math department, 16 Colchester Ave. NOTE THAT LOCATION HAS RETURNED TO UVM.
Title: Using Sidon Sets in Cryptography
Speaker:
John A. Trono, Associate Professor of Computer Science, Saint Michael's
College
Abstract:
This
talk is intended for anyone who is interested in the topic of securely
sending
(and receiving) information over the Internet. One popular strategy
for
encrypting messages is the RSA public key encryption algorithm, invented
by
Rivest, Shamir, and Adelman. The large amount of computation that is
necessary
for the RSA algorithm will be briefly discussed, and this will be
followed
by a more detailed discussion of a simpler strategy that is based
solely
on the properties of addition. Some of the specifics about how the
new
strategy could be implemented will involve some basic details concerning
bits
and bytes, but no other specific computer science knowledge is
necessary.
Date:
Tuesday, April 10, 2001
Time: 8:30-9:20 a.m.
Location: Conference Room, Math department, 16 Colchester Ave.
Title: Making Connections, Part III
Speaker: No formal speakers—today’s seminar will have a workshop format.
Abstract:
This will be a continuation of the
introductory seminars of March 13 & 27.
Participants will break into working groups to discuss problems in
greater depth. The problems will
include those previously mentioned at earlier seminars, but the workshop is open
to the possibility of introducing new problems. If you have a new problem, or were unable to attend the March
seminars, you are still more than welcome to participate in this
workshop—there will be plenty of room at the tables for you!
As before, the goal for today’s
seminar is to provide a forum where participants have the opportunity to make
initial/continuing contact and explore the possibility of productive
collaboration with one another.
The workshop will also provide a
venue for informal discussion and an opportunity to hear about new problems and
techniques. You may find someone
who is very interested in your work because of the possible connections to their
own—the only way to find out is to come and try.
Graduate students, faculty and engineers are especially encouraged to
attend, as this is potentially a source exciting projects.
People from other industries, schools, and endeavors besides UVM and IBM are most welcome—the broader the range of experience, the better the aggregate resources.
Date: Tuesday, April 17
Time: 8:30-9:20 a.m.
Location: Conference Room, Math department, 16 Colchester Ave.
Title: Class-Uniformly Resolvable Designs
Speaker: Peter Danziger, Ryerson Polytechnic University
Abstract:
A Class-Uniformly Resolvable Design is a resolvable pairwise balanced
design in which each of the resolution classes has the same number of
blocks of each size. Such designs represent a generalization of many types
of resolvable designs. We will investigate the necessary conditions which
lead to some interesting extremal bounds. We will present some existence
results for these families. If time permits we will also consider
Class-Uniformly Resolvable Group Divisible Designs, including
a novel construction for shrinking the index of a master design.
Date: April 24, 2001
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Quantum Computing for the Classically Minded
Speaker: Robert Snapp, Computer Science, University of Vermont
Abstract:
Theoretical
studies over the last decade suggest that computers
based
in the quantum mechanical domain have the potential to
dramatically
out perform more conventional (i.e., classical)
models
of computation. For example, Shor developed a quantum
algorithm
that factors an n-bit integer in polynomial time.
(The
best known classical algorithm requires O(exp(n^(1/3) (log n)^(2/3)))
operations.)
This talk will introduce some fundamental concepts
of
quantum computing, including qubits, quantum circuits, and maybe
even the quantum Fourier transform, a component of Shor's algorithm.
Here is a link to Robert's webpage for this talk. It has a lot of great links and references.
http://www.cs.uvm.edu/~snapp/teaching/qcomputing.html
Date: May 1, 2001
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title:
DNA Sequencing, Euler Circuits, and
the Interlace Polynomial
Speaker: Gregory
Sorkin, IBM T.J. Watson Research
Center
Abstract:
A
method of DNA sequencing, sequencing by hybridization, is liable to a
degree
of ambiguity. We compute the
probability that sequencing is
unambiguous,
has exactly 2-fold ambiguity, exactly 3-fold ambiguity, etc.
The
essence of the problem is to do with Euler circuits in "2-in 2-out
graphs"
-- directed graphs where every node has in-degree 2 and out-degree 2.
A
decomposition theorem for these graphs and their Euler circuits lies
at
the heart of the counting result, and the counting itself follows from some
"generatingfunctionology".
The
Euler circuits of a 2-in 2-out graph, which are counted by the BEST
theorem
and the matrix-tree theorem, can also be counted from an induced
undirected
graph, the "interlace" graph. This
motivates a new graph
polynomial, the interlace polynomial, with a number of fascinating properties.
(Joint work with Richard Arratia and Bela Bollobas.)
UVM
Picture: There is a picture of the Math Department building (Lord House, 16
Colchester Avenue) at http://www.emba.uvm.edu/math
.
The seminars are held
here in the conference room on the first floor.
Parking: The easiest place to park is probably the Visitor Lot at Waterman.
It is located on College Street, across the street from the Waterman
administration building. Parking is paid, 75 cents/hour, 7 a.m. to 5
p.m., Monday through Friday, and free after 5 p.m. and on weekends and holidays.
Directions to the Vistors' lot:
From I-89: Take Exit 14W into Burlington. This puts you heading west on Williston Road going up hill.
Turn right onto North Prospect Street. Take first left onto College Street. Take first left into
visitor parking lot.
Heading north from Route 7: Follow Shelburne Road/Route 7 into
Burlington. At rotary, bear right. Approximately 1/4 mile to first four-way stop, turn right onto Cliff Street. Head uphill to end of
Cliff; take left onto South Prospect Street. Cross Main Street/Route 2. Take first left onto College Street. Take first left into visitor
parking lot.
Maps: There are campus maps on the UVM website, and the direct URAL is: http://scripts.uvm.edu/www/map.php3.
Click on the map to zoom in, or use the "locate" button at the bottom to find specific buildings or
parking lots (the Math Department is 16 Colchester, the visitor lot is across College street from Waterman building).
A map of the whole campus with visitor parking colored green is at http://www.uvm.edu/~tpswww/images/oncampus.jpg,
but you need a LARGE monitor to read the labels.
From Interstate 89: Coming from the north or south, take exit 12. From the north, turn left off exit ramp; from the south, turn right onto Route 2A. Follow the road past three traffic lights, over a bridge and up a hill. Watch for (and turn into) IBM entrance signs on the right.
For the WILLISTON LOBBY: After turning into IBM, go straight. Pass the “Main Lobby” signs. Go around the S-curve and over bridge. Take third left-hand turn into the visitor parking lot.
Map: Here is a map of the area near IBM. The Williston site is the dark rectangle just to the south of the rectangle marked IBM.
