Computer Science Seminar Archive

March 05, 2008

Unsupervised Language Learning

Speaker: Tom Armstrong, University of Maryland Graduate School, Baltimore
Abstract: The ease with which children learn to discover boundaries in their environments while building high-level structures belies the complexity and computational challenges of the task. Children are facile at discovering lexical items in speech, generalizing over patterns in utterances to form grammars, and handling noisy environments. In spite of developmental learning results showing interplay between these high- and low-level structures, lexical acquisition and grammar learning are largely treated as distinct tasks. Many results for both learning problems take a pipelined approach, cannot recover from errors, and ignore problems with noise. Most grammar induction results require a known alphabet with perfectly parsed input data. Most lexical acquisition results ignore how the lexical items are used. In this talk, we present a bootstrap architecture for lexical and grammatical learning. Our approach allows for a relaxation of the perfectly parsed input data assumption and exploits information on how lexical items are used. We demonstrate the utility of the bootstrap in two domains. First, we consider learning regular grammars and lexicons from phonetic transcriptions of natural language data. We present an algorithm that simultaneously learns an alphabet and an automaton while allowing errors and driving error recovery. Second, we investigate the interplay between meaning and structure. We present a pair of algorithms for learning context-free grammars from lexical semantics and learning lexical semantics from learned grammars. We conclude with applications of this research and future directions.

January 29, 2008

Two algorithms in search of a type system

Speaker: Norman Danner

Abstract: Implicit computational complexity is the study of (elegant) machine-independent characterizations of traditional complexity classes such as the polynomial-time computable functions. A sometimes-stated hope is that such results could yield programming languages with the pleasant properties that (1) any compilable program lies in the characterized complexity class, and (2) there is a program for any function in the complexity class. The reality, though, is that while a complexity class may be captured, many natural *algorithms* are not. For example, many characterizations of polynomial-time exclude precisely the kinds of recursive definitions used in insertion- and selection-sort. In this talk I will discuss current work with James Royer of Syracuse University on a functional language which captures exactly the type-2 polynomial-time computable functionals and at the same time allows for fairly natural programming. This talk will be longer on motivation and examples and shorter on proofs.

December 05, 2007

Reasons and Methods for Compile-time Metaprogramming

Speaker: Rona Garcia, Indiana University, Bloomington
Place: Room 339SC*
Ron Garcia is a candidate for a Computer Science Mellon Postdoc under the auspices of the 3 college Mellon Grant. He will be giving the following talk at Wesleyan

Abstract: Software libraries make it much easier for developers to build applications, but the abstractions they provide often come with a price; slow run-time performance and some usage errors overlooked by the type checker at compile-time. In this talk, I discuss how C++ template metaprogeramming has been used to implement software libraries that provide high-level interfaces without sacrificing funtime performance and check domain-specific properties at compile-time. I discuss the benefits and shortcomings of template techniques. Based on my analysis of the essential capabilities of C++ templates for template metaprogramming, I present a language design that directly and intentionally captures those capabilities.

*Videoconferencing facility

December 04, 2007

Models for normalizations(s)

Speaker: Olivier Hermant, Complutense University of Madrid
Abstract: The formalisation of mathematical proofs often requires the help of a computer to be processed. For instance, the 4 color theorem or the Kepler conjecture could not have been proved without the help of programs.

Surprisingly, the logical formalisms applied in Computer Science do not take this into account. The focus is more on deduction and forgets the computation, although it is a central concept in mathematics. Deduction Modulo is a logical framework introduced by Dowek, Hardin and Kirchner, that tries to reconcile these two approaches.

We first give a general overview of deduction modulo, and give hints on its expressiveness, introducing also the semantics for it.

We then focus on a central point of every logical formalism: the cut elimination theorem. First, we stress the links between normalization methods, based on the Curry-Howard correspondence, and model theory.

Then, we show how to transform this sort of model into a Heyting algebra, used to prove normalization by evaluation, in a way surprisingly similar to semantic cut elimination works in higher-order logic of Andrews, Prawitz, Takahashi, Lipton and Okada.

We then point out the gaps between normalization, normalization by evaluation and semantic cut admissibility.

October 30, 2007

Key-Compromise Impersonation Attacks on TLS Fixed Key Diffie-Hellman Key Exchange

Speaker: Matthew Campagna, Director of Research, Certicom Corp.

Abstract: Key-compromise impersonation security protects an entity against an adversary impersonating another when the adversary has learned the entity's long-term secret key. The popular Transport Layer Security (TLS) protocol, widely used to secure browser based applications, implements a fixed-key Diffie-Hellman (DH) key exchange to establish a mutually authenticated secure channel. It is shown that this key exchange and authentication method does not provide the desirable security property of key-compromise impersonation. General recommendations are made to mitigate this loss of security, and time permitting the Menezes-Qu-Vanstone (MQV) protocol will be presented as one such solution.

October 23, 2007

Social Robots and Human Social Development

Speaker: Brian Scassellati, Department of Computer Science, Yale University

Abstract: Social robots recognize and respond to human social cues with appropriate behaviors. These robots are unique tools in the study of human social development, and have the potential to play a critical role in the diagnosis and treatment of social disorders such as autism.

In the first part of this talk, I present four vignettes on what the practicality of constructing social robots has taught us about human social development. These vignettes cover topics of perceptual development (vocal prosody), sensorimotor development (declarative and imperative pointing), linguistic development (learning pronouns), and cognitive development (self-other discrimination).

The second half will focus on the application of social robots to the diagnosis and therapy of autism. Autism is a pervasive developmental disorder that is characterized by social and communicative impairments. Based on three years of integration and immersion with a clinical research group which performs more than 130 diagnostic evaluations of children for autism per year, I will discuss how social robots will impact the ways in which we diagnose, treat, and understand autism.

April 19, 2007

Analysis of a Two-Dimensional Barcode Communication System

Speaker: Robert Cordery, Pitney-Bowes

A modern postage meter generates a digital signature of certain postal information as evidence for postage paid for a mail piece. The signature and postal information are communicated to the Postal Service via a two-dimensional barcode printed in the postage indicium on the upper right corner mail piece. There are several components of this indicium barcode communication channel: an encoding system adds error correction code and converts the data to a barcode image; a printing system with a print engine and ink produces a printed image of the barcode on the mail piece; a camera and a decoder captures and processes an image of the barcode and extracts the data.