Meeting Agenda

Wednesday, July 23^rd, 1997

Location:

DC 1304

Time:

13:30

Chair:

Erik Demaine

1. Adoption of the Agenda - additions or deletions

2. Coffee Hour

Coffee hour this week:

???

Coffee hour next week:

???

3. Next meeting

Date:

July 30^th, 1997

Location:

DC 1304

Time:

13:30

Chair:

Itai Danan

Technical presentation:

Itai Danan

4. Forthcoming

Chairs:

1. Ed Dengler (8/06)
2. Petra Englemann (8/13)
3. Dave Evans (8/20)

Tech Presenters:

1. Bill Cowan (8/06)
2. Ed Dengler (8/13)
3. Petra Englemann (8/20)

5. Technical Presentation

Presenter:

Erik Demaine

Title:

Origami Mathematics and Animation

Abstract:

This talk begins with some history of origami (paper folding). I will then discuss a couple of problems that I have been working on recently. The first problem is to find a general (mathematical) definition of a fold. The second problem is the ``folding-and-cutting'' problem, used for a magic trick by Houdini before he became a famous escape-artist. Take a sheet of paper, fold it arbitrarily, make one complete straight cut, and unfold the pieces. What are the possible shapes of the pieces? Can you cut out a given polygon? We claim that you can make any shape. I will show the solution for a triangle. My animation program implements the solution for convex polygons, and I will show you some snapshots. Finally, at the end of the talk, there will be a big surprise. Don't miss it!

6. General Discussion Items

• New equipment in the lab (Steve Mann)
• Physeter signup sheet (Mark Riddell):
  Physeter seems to be quite busy these days, so it would be a good idea to start using the signup sheet again. At least until the new Octanes come in (and are up and running...).
• Action list (AL) files (Erik Demaine):
  AL_active and AL_done seem out of date (e.g., Ivan Sutherland Visit is still active). Should we trash them? If not, reminder to keep them up-to-date.

7. Action List

• Japanese Visitors
• Alias Visit

8. Director's Meeting

9. Seminars

• Tomorrow (July 24): Cheap food seminar (AKA Faculty, Staff, and Student BBQ Social)

  Time: 11:00 a.m.-1:30 p.m.
  Place: DC courtyard

  Join the celebration of the Math faculty's 30th birthday! 1967 prices: 30 cents for a burger, hotdog, or pop. I hear the dean and/or associate dean will cook.

• Today (July 23): Master's thesis presentation

  Marcello Lioy, graduate student, Dept. Comp. Sci., Univ. Waterloo, will speak on ``Providing TCP-level Services to Mobile Computers in Wireless Networking Environments''.

  Time: 2:30-3:30 p.m.
  Room: DC 1304

  Abstract:

  It is well known that unmodified TCP behaves poorly in mobile and wireless environments, principally because of its assumption that packet loss is due to congestion. While this assumption is valid in wireline settings with stationary hosts, significant sources of packet loss in mobile and wireless environments are data corruption and handoffs.

  Much work has been done to try and improve TCP performance in these settings. This has ranged from entirely new protocols which can interoperate with TCP, to modifications, both major and minor, to the protocol itself. Most of these modifications have the significant disadvantage that they require either changes to the base protocol across the entire network, or changes to applications that rely on TCP. In some cases, TCP end-to-end semantics are violated. The ideal solution is to improve TCP behaviour without changing its semantics or requiring any changes except at the base station and perhaps the mobile. It is important that the modifications not require any external support in order to function.

  This thesis explores how a base station can provide transport-level services to the mobile computers that it is routing for. Services include TCP-level handoffs, TCP connection maintenance to support link disconnection, and the ability to prioritize TCP streams.

  The Base Station Service Protocol has been developed to support these services. The protocol is used by mobiles to request services, as well as to support handoff. Two services have been implemented: connection maintenance and stream prioritization. Both of these services are provided using the existing capabilities of TCP with no modifications to the protocol or its end-to-end semantics.

  Experimental results validating the connection maintenance and stream prioritization services are given and explained, as are results of experiments exploring the usefulness of said services. The results demonstrate that the services not only work, but are worthwhile and improve TCP behaviour in mobile and wireless environments.

• Today (July 23): CSC talk (with tea and doughnaughts)

  Robin Powell will speak on "Privacy and Anonymity in E-Mail."

  Time: 5:00 p.m.
  Room: MC 4042

  Abstract

  Most people who use e-mail have at least heard that it is possible to encrypt messages such the no-one but the intended recipient can read them. Most people agree that this can be a useful feature, when you need it. The problem is that using such systems are, in general, unwieldy at best.

  In this talk I will dicuss how to set oneself up to use the power of public key cryptography to send secure e-mail, as well as anonymous e-mail that can be replied to if you wish.

  I will briefly discuss setting up a PGP public key, and then move on to some solutions for integrating encryption into various e-mail programs, and end up with a discussion of encrypted anonymous remailers.

  Note: The material in this talk is recommended background for next week's talk on SSL and Web Security.

• Tomorrow (July 24): E&CE Ma.Sc. seminar

  J. Zhu will spead on "Pitch-Synchronous Wavelet Representation of Speech Signals."

  Time: 11:30 p.m.
  Room: DC 2564

  Abstract:

  The pitch-synchronous vector representation of signals illustrates the pitch fluctuations and total aperiodicity characteristics of signals containing pseudo-period information such as speech signals. An intermediate pitch-synchronous wavelet transform (PSWT), is discussed in this presentation. By means of these new bases, the pseudo-periodic segments of the signal are analyzed in terms of regular asymptotically periodic trend and a number of fluctuations at several scales in order to reduce the data-rate in communication systems or upgrade pitch and time-scale modification of speech techniques. The PSWT is particularly suitable to the analysis, rate-reduction coding and synthesis of speech signals. Feature extraction such as separation of voice from noise in voiced consonants is easily performed by means of partial wavelet expansions.

• Tomorrow (July 24): Optimization seminar

  Tamon Stephen, Dept. Comb. Opt., Univ. Waterloo, will speak "On a representation of the matching polytope via semidefinite liftings."

  Time: 2:30 p.m.
  Room: MC 5136

  Abstract:

  In this talk, I will describe a technique of Lovasz and Schrijver for solving 0-1 integer programs (IP). This technique lifts successive relaxations of the IP into semi-definite programs in a larger space, and then projects them back to original space. I will then show how an elementary approach can be used to analyze this technique on the matching polytope.

  Joint work with Levent Tuncel.

• Friday (July 25): Tutte seminar

  Andrei Kotlov, Dept. Comp. Opt., Univ. Waterloo, will speak on "A new minor-monotone algebraic invariant of graphs."

  Time: 3:30 p.m.
  Room: MC 5158

  Abstract:

  We introduce a spectral invariant, l(G), of a graph G. It appears to be new, though similar in spirit and properties to the Colin de Verdiere invariant mu(G). In particular, l(G) is minor monotone and topological, i.e. invariant under edge subdivision. A graph G is a forest if and only if l(G) is at most 1.

  We start with the definition of l(G), consider examples, and work out equivalent characterizations of l(G). One of them is through faithful orthogonal representations, so that a relationship between l and the Lovasz theta number can be immediately observed. Finally, advancing at a comfortable pace, we survey properties of l and compare them with those of Clin de Verdiere's mu.

• Monday (July 28): CSC talk (with tea and doughnaughts)

  Ian Clysdale will speak on "SSL And Web Security."

  Time: 3:30 p.m.
  Room: MC 4058

  Web Security, Internet Commerce, and DigiCash have all become buzzwords in the last year or two. But what exactly do they mean? How does the web security model work?

  This talk will look at the SSL protocol and its applications. It will review public key cryptography, although a basic understanding of the concepts is highly recommended. A technical description of the protocol will be quickly given, but the talk will focus more on applications and ways that SSL is used in commercial and freely available software.

  Also explored will be the concept of trust relationships. Hierarchical methods of certification such as VeriSign's signing services will be discussed, as well as non-hierarchical methods where organizations act as their own certification authorities, with some analysis of both situations.

  It will conclude with discussion of the risks and benefits presented by commercial transactions over the Internet.

10. Lab Cleanup (until 14:30 or 5 minutes)