shadow_tr

Colloquia

Spring 2015 Colloquia

Check back soon for more information on the computer science seminar series. Unless otherwise noted, the seminars now meet on Mondays at 3pm in Stanley Thomas 302. If you would like to receive notices about upcoming seminars, you can subscribe to the announcement listserv.

January 13

What AI Can Do for Multi-Item Sentiment Analysis

Joint Work with Andrea Loreggia, Umberto Grandi, Vijay A. Saraswat

Francesca Rossi University of Padova, Italy


This event will be held on Tuesday, 1/13/2015, at 3:30 p.m. in Stanley Thomas, Room 302. Please note the special weekday and time for this event.

Abstract: Sentiment analysis assigns a positive, negative or neutral polarity to an item or entity, extracting and aggregating individual opinions from their textual expressions by means of natural language processing tools. It then aggregates the individuals' opinions into a collective sentiment about the item under consideration.

Current sentiment analysis techniques are satisfactory in case there is a single entity under consideration, but can lead to inaccurate or wrong results when dealing with a set of possibly correlated items. This can be useful, for example, when a company wants to know the collective preference order over a set of products. Or also when we want to predict the outcome of an election over a collection of candidates.

We argue that, in order to deal with this more general setting, we should exploit AI techniques such as those used in preference reasoning, multi-agent systems, and computational social choice. Preference modelling and reasoning tools provide the useful ingredients to model individual's preferences in the most faithful way, while computational social choice techniques give methods to aggregate such preferences which satisfy certain desired properties.

Other AI techniques can be very useful as well, such as machine learning or recommender system tools to cope with incompleteness in the information provided by each individual.

We describe a social choice aggregation rule which combines individuals' sentiment and preference information. We show that this rule satisfies a number of properties which have a natural interpretation in the sentiment analysis domain, and we evaluate its behavior when faced with highly incomplete domains.


About the Speaker: Francesca Rossi is a professor of computer science at the University of Padova, Italy. Currently she is on sabbatical at Harvard with a Radcliffe fellowship. Her research interests include constraint reasoning, preferences, multi-agent systems, computational social choice, and artificial intelligence. She has been president of the international association for constraint programming (ACP) and she is now the president of IJCAI. She has been program chair of CP 2003 and of IJCAI 2013. She is in the editorial board of Constraints, Artificial Intelligence, AMAI, and KAIS. She will be Editor in Chief of JAIR starting January 2015. She has published over 160 articles in international journals, in proceedings of international conferences or workshops, and as book chapters. She has co-authored a book. She has edited 16 volumes, between conference proceedings, collections of contributions, and special issue of international journals. She has co-edited the Handbook of Constraint Programming (Elsevier, 2006). Her h-index is 27. Her most cited papers have more than 560 citations. She has more than 100 co-authors.
January 23

A Public-Key Cryptosystem Based on an Undecidable Problem

Neal R. Wagner UNIVERSITY OF TEXAS AT SAN ANTONIO (RETIRED)


This event will be held on Friday, 1/23/2015, at 4:00 p.m. in Stanley Thomas, Room 302. Please note the special weekday and time for this event.

Abstract: First I will introduce public-key cryptosystems (PKCs). A famous example is the early Merkle-Hellman proposal to use the NP-complete problem Subset Sum (SS) as the basis for a PKC. To encrypt, one forms the sum of a subset of given numbers, but decryption requires solving SS and finding the numbers that made up the sum. For a PKC one creates an instance of SS with a "trapdoor" -- a secret design that allows an instance to be decrypted efficiently. This was the first serious proposal for a PKC. Eventually it was broken in its full generality.

Then I will talk briefly about the cryptosystem of Rivest, Shamir, and Adleman (RSA), which is based on the problem of factoring a product of primes (FACTOR). FACTOR is in NP but conjectured not to be NP-complete. Nevertheless, it is intractable right now (until we get quantum computers). I was the first person to propose using an undecidable problem as the basis for a PKC. The problem I used is the undecidable word problem for finitely presented groups (WPG). First I'll discuss the general Word Problem (WP), fairly easily shown to be undecidable. Then I will introduce extra structure to make WP into a group. This last consists of finitely many symbols called generators (each with an inverse), a collection of strings of these generators, and a collection of relators, each of which is a string of generators (and inverses) which is equal in the group to the empty string (the identity element).

WPG asks if a given string of generators and inverses can be transformed to the empty string. The talk will give a number of definitions needed to precisely define these groups. They are very complex entities.

Then I show how to encrypt a single bit with this PKC. This is a randomized PKC, with infinitely many cyphertexts corresponding to each plaintext bit. In general, decryption would be undecidable, but I will show a way to add extra secret relators to this group to make a new group in which decryption is efficient.

The talk requires no prior special knowledge.

About the Speaker: Neal Wagner retired as Associate Professor from the University of Texas at San Antonio. He received a Ph.D. in mathematics from the University of Illinois at Urbana-Champaign in 1970, specializing in topology. He also taught at the University of Texas at El Paso, the University of Houston, and Drexel University. In 1973 he was seduced by the dark side and started looking at computer science. During 1974-76 he worked as a programmer and programming supervisor on real-time simulation of the Space Shuttle at Johnson Space Center. Later, he specialized in cryptography and database security.

February 2

Rigorous OS Design: An Idea Whose Time Has Come

Leonid Ryzhyk Carnegie Mellon University

Abstract: Modern operating systems consist of millions of lines of low-level code, which is hard to understand, maintain, and validate. In this talk I will advocate the rigorous approach to OS design as a way to overcome the problem. I argue that the time has come to re-think the OS design based on a solid mathematical foundation. This long-sought vision is finally becoming feasible due to recent advances in programming languages, model checking, and interactive theorem proving. I will outline a high-level methodology for rigorous OS design, consisting of three components: (1) a theoretical foundation for formal reasoning about OS behaviour at a level of abstraction much higher than C code, (2) a software ecosystem, consisting of domain-specific languages and tools that provide a programmer-friendly interface to the theory, (3) OS implementation, built and verified on top of this ecosystem.

As a concrete instantiation of this methodology, I will present the Termite project, which has developed the first tool for automatic synthesis of correct-by-construction device drivers. In Termite, the driver behavior is formalized in terms of the discrete control theory and is automatically synthesized using controller synthesis techniques. I will show how the connection to the control theory enables efficient formal reasoning about complex low-level software. The talk will conclude with a brief demo of Termite.


About the Speaker: Leonid Ryzhyk is a postdoctoral researcher in the Carnegie Mellon University School of Computer Science. Leonid's research focuses on operating systems and in particular using formal methods to build better operating systems. He received his PhD from the University of New South Wales in 2010. Prior to joining CMU, Leonid worked as a researcher at NICTA and a postdoctoral fellow at the University of Toronto.
February 9

Distinguishing Cylinders from Moebius Bands: Projections, Intersections, and Inflections

Thomas Banchoff Emeritus Professor at Brown University and Visiting Professor at Sewanee, The University of the South

This speaker is co-hosted by Tulane's Dept.of Mathematics and the Dept. of Computer Science.

Abstract:On a smooth or polyhedral surface a strip neighborhood of a closed curve is either and orientable cylinder or a non-orientable Moebius band. How can we distinguish which form it has by observing singular fold chains for projections to planes or self-intersection curves of immersions (and non-immersions) into three-space or a new phenomenon, inflection faces? This talk gives an introduction to the geometry of characteristic classes and it features computer graphics images and animations that will make it accessible to novice and expert alike.

About the Speaker: Thomas Banchoff received his PhD under Prof. Shiing-Shen Chern at UC Berkeley in 1964 and he has been teaching ever since, mainly at Brown University. He has received a number of local and national teaching awards and he was president of the MAA in 1999-2000. He is the author of four books and eighty articles on geometry and topology and computer graphics. He gave an invited address at the International Congress of Mathematicians in Helsinki in 1978 on "Computer Animation and the Geometry of Surfaces in Three- and Four-Space" and he was named a fellow of the American Mathematical Society in 2012.

February 23

Topic

Speaker Institution

Abstract:TBA

March 2

Topic

Speaker Institution

Abstract:TBA

March 5

Topic

Shantenu Jha Rutgers University


This event will be held on Thursday, 3/5/2014, at 3:30 p.m. in Stanley Thomas, Room 302. Please note the special weekday and time for this event.

Abstract:TBA

March 9

Topic

Speaker Institution

Abstract:TBA

March 16

Topic

Speaker Institution

Abstract:TBA

March 23

Topic

Speaker Institution

Abstract:TBA

April 13

Topic

Speaker Institution

Abstract:TBA

April 20

Topic

Speaker Institution

Abstract:TBA

April 27

Topic

Speaker Institution

Abstract:TBA

School of Science and Engineering, 201 Lindy Boggs Center, New Orleans, LA 70118 504-865-5764 sse@tulane.edu