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.
Francesca Rossi University of Padova, Italy
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.
Neal R. Wagner UNIVERSITY OF TEXAS AT SAN ANTONIO (RETIRED)
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.
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.
Thomas Banchoff Emeritus Professor at Brown University and Visiting Professor at Sewanee, The University of the South
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.
Shantenu Jha Rutgers University
School of Science and Engineering, 201 Lindy Boggs Center, New Orleans, LA 70118 504-865-5764 firstname.lastname@example.org