Category: Lectures

Jack Edmonds,

–

Abstract:

NP and P have origins in “the marriage theorem”:

A matchmaker has as clients the parents of some boys and some girls where some boy-girl pairs love each other.

The matchmaker must find a marriage of all the girls to distinct boys they love or else prove to the parents that it is not possible. The input to this marriage problem is usually imagined as a bipartite graph G with boy nodes, girl nodes, and edges between them representing love.

A possible legal marriage of some of the girls to some of the boys is represented by a subset M of the edges of G, called a matching.

The matchmaker’s problem is to find a matching which hits all the girl nodes Or else prove to the parents that there is none…

Full announcement at https://thor.inesc-id.pt/jack.edmonds/

Bio

Jack Edmonds is one of the creators of combinatorial optimization. He attended George Washington University before pursuing graduate study at the University of Maryland. He received his master’s degree in 1959 and began work at the National Bureau of Standards (NBS). He moved to the University of Waterloo in 1969, where he supervised a dozen PhD students. Throughout his career, he has influenced and assisted numerous young researchers. In the 1960s, Jack Edmonds developed a theory of matroid partition and intersection that still stands as one of the most profound and thorough explorations in the field. He illustrated the deep interconnections between combinatorial minmax theorems, polyhedral structure, duality theory, and efficient algorithms. He published many influential papers on these topics, with the one published in 1972 on theoretical improvements in algorithmic efficiency for network flow problems with Richard Karp leading to one of the most well known algorithms among nowadays CS students. He was awarded the John von Neumann Theory Prize for his contributions as a researcher and educator in 1985. Jack Edmonds retired from teaching in 1999 and was elected into the inaugural Fellows class of the Institute for Operations Research and the Management Sciences.

Host

Alexandre Paulo Lourenço Francisco

Venue:

FA3 – Informatic Department – IST Alameda

Andrew Myers,

Cornell University, USA –

Abstract:

Programming concurrent, distributed systems that mutate shared, persistent, geo-replicated state is hard. To enable high availability and scalability, a new class of weakly consistent data stores has become popular. However, some data needs strong consistency. We introduce mixed-consistency transactions, embodied in a new embedded language, MixT. Programmers explicitly associate consistency models with remote storage sites; within each atomic, isolated transaction, data can be accessed with a mixture of different consistency models.
Compile-time information-flow checking, applied to consistency models, ensures that these models are mixed safely and enables the compiler to automatically partition transactions into a single sub-transaction per consistency model. New run-time mechanisms ensure that consistency models can also be mixed safely, even when the data used by a transaction resides on separate, mutually unaware stores. Performance measurements show that despite offering strong guarantees, mixed-consistency transactions can significantly outperform traditional serializable transactions.

Bio

Andrew Myers is a Professor in the Department of Computer Science at Cornell University in Ithaca, NY. He received his Ph.D. in Electrical Engineering and Computer Science from MIT in 1999, advised by Barbara Liskov.
His research interests include computer security, programming languages, and distributed and persistent programming systems. His work on computer security has focused on practical, sound, expressive languages and systems for enforcing information security. The Jif programming language makes it possible to write programs which the compiler ensures are secure, and the Fabric system extends this approach to distributed programming. The Polyglot extensible compiler framework has been widely used for programming language research.
Myers is an ACM Fellow. He has received awards for papers appearing in POPL’99, SOSP’01, SOSP’07, CIDR’13, PLDI’13, and PLDI’15.
Myers is the current Editor-in-Chief for ACM Transactions on Programming Languages and Systems (TOPLAS) and past co-EiC for the Journal of Computer Security. He has also served as program chair or co-chair for a few conferences: ACM POPL 2018, ACM CCS 2016, POST 2014, IEEE CSF 2010, and IEEE S&P 2009.

Host

Rodrigo Seromenho Miragaia Rodrigues

Venue:

Anfiteatro VA4 no piso-1 do Edificio de Civil – IST/Alameda