UVM Applied Combinatorics Seminars

 

 

Overview Schedule and Abstracts Participating Directions and Parking

UVM        IBM

 

UVM Applied Combinatorics Seminar, Spring 2001

Tuesdays, 8:30 to 9:20 am.

Overview

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.

 

Participating

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.

Schedule and Abstracts

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.

Here are links to the Math/Stats and CS departments at UVM.  Individual websites, which often include research interests, can be accessed from the main sites.

 

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:

Sambasivan Narayan:

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.

Dalibor Froncek:

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.

 Peter Osler:

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

 

 

 

Directions and Parking

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.

IBM--Williston Site

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.

 

UVM CS Dept.

UVM Math Dept. UVM Home Jo E-M Home