Computer Science Seminars
Ilya Volkovich, University of Michigan - March 3rd, 2020
Algebraic Problems: The Frontier of Efficient Randomized Computation
Randomness is a valuable resource in many computational tasks. Indeed, the security and/or the accuracy of many randomized algorithms and protocols rely on the random bits being truly random and independent. However, in practice such random bits are elusive, which may compromise the performance of the underlying systems. This motivates the following fundamental question:-
Can every computational task that requires randomness be carried out deterministically, paying, perhaps only a small overhead?
Meanwhile, the nature of many algebraic problems makes them amenable to randomized algorithms. For example: a random set of vectors is independent, a random assignment to a low-degree polynomial is non-zero etc. Thus, you can easily find a set of independent vectors and a non-zero assignment by picking them uniformly at random. Indeed, it is not surprising that the frontier of efficient randomized computation consists of algebraic problems. Among the frontier problems are Polynomial Identity Testing, Polynomial Factorization and others.
In this talk, I will discuss my research on the relationship between randomness, computation and algebra. Time permitting, I will also discuss the problems I have been working on and some recent connections to cryptography and machine learning.
Dr. Ilya Volkovich is a Senior Lecturer in the Department of Computer Science and Engineering at the University of Michigan, where he has taught courses in the theory of computation for several years. Previously, he was a Postdoctoral Research Associate in the Computer Science Department at Princeton University and held a visiting position at the Institute of Advanced Study. In 2012, he obtained his Ph.D. in Computer Science from Technion, Israel Institute of Technology, advised by Prof. Amir Shpilka. His research interests are in the broad area of theoretical computer science and discrete mathematics. More specifically, he is interested in aspects of algebraic complexity, randomness in computation, computational learning theory, and their applications to cryptography and machine learning.
Adam Poliak, Johns Hopkins University - February 18th, 2020
Exploring Reasoning Capabilities in Natural Language Processing Models
Natural Language Processing (NLP) is the field of building machines that humans can seamlessly interact with through spoken and written language. As these machines become more ubiquitous in our daily lives through technologies like Google Translate and Apple’s Siri, it is important to develop methods that provide insight into understanding the reasoning capabilities of these systems. Adam will discuss his work on developing diagnostic test-suites composed of fine-grained semantic phenomena. He will demonstrate how to use these tests to explore the reasoning capabilities of contemporary NLP systems. Additionally, he will also discuss biases in prior datasets that the research community has accepted as gold standards. He will discuss how these biases limit the previous datasets’ usefulness in testing how well NLP systems successfully understand natural language. With the remaining time, he will discuss how lessons from these studies can be applied to identifying emergency needs during disaster scenarios.
Adam Poliak is a final year Ph.D. Candidate in Computer Science at Johns Hopkins University advised by Dr. Benjamin Van Durme. Adam is an affiliate of the Center for Language & Speech Processing as his research focuses on Natural Language Processing and Computational Semantics. In particular, his research analyses NLP systems and datasets to provide insight into the failures of NLP systems as well as biases in textual data. His work has been published in top-tier NLP conferences and he won Best Paper Awards in 2018 and 2019 at The Joint Conference on Lexical and Computational Semantics. Adam was a 2017 GEM Fellow and he has performed research at Bloomberg L.P. and the MIT Lincoln Laboratory.
Sarah Ita Levin, Columbia University - February 11th, 2020
True or False? Automatic Detection of Deception and Trust in Spoken Dialogue
Spoken language processing (SLP) aims to teach computers to understand human speech. Automatic deception detection from speech is one of the few problems in AI where machines can potentially perform significantly better than humans, who can only detect lies about 50% of the time. In this talk, I will discuss my work on training computers to distinguish between deceptive and truthful speech using language features. My work combines machine learning with insights from psychology and linguistics to develop robust techniques to detect deceptive speech. I will also present ongoing research aimed at understanding the characteristics of trustworthy language. This work improves our scientific understanding of deception and trust, and has implications for security applications and for increasing trust in human-computer interaction.
Sarah Ita Levitan is a postdoctoral Research Scientist in the Department of Computer Science at Columbia University. Her research interests are in spoken language processing, and she is currently working on identifying acoustic-prosodic and linguistic indicators of trustworthy speech, as well as identifying linguistic characteristics of trustworthy news. She received her PhD in Computer Science at Columbia University, advised by Dr. Julia Hirschberg, and her dissertation addressed the problem of automatic deception detection from speech. Sarah Ita was a 2018 Knight News Innovation Fellow and a recipient of the NSF Graduate Research Fellowship and the NSF IGERT From Data to Solutions fellowship. She has interned at Google Research and at Interactions LLC.
Mark Santolucito, Yale University - January 24th, 2020
Program Synthesis for Software Systems
Program synthesis is the process of automatically generating code from specifications. This specification, describing the intended code behavior, can be either explicitly expressed as formulas, can be given in the form of illustrative examples, or it can be inferred from the context. There are decades of research into program synthesis, but only recently we have seen synthesis scale to industrial benchmarks. However, these applications have been limited to simple data transformations and automation tasks.
In this talk, I outline new directions in software synthesis targeted at increasing scalability and expressivity so that synthesis tools can assist in the development of real-world large software systems. With these advances, we have successfully synthesized systems such as mobile apps, self-driving car controllers, and embedded systems. We have also applied synthesis to novel domains, including configuration file analysis and digital signal processing. I conclude by describing future work on exploring usability of program synthesis and challenges we face when integrating synthesis into developer workflow.
Mark Santolucito is completing his PhD from Yale University under the supervision of Ruzica Piskac. Mark’s work has been focused on program synthesis and computer music. His research has been published at top conferences including, CAV, OOPSLA, CHI, and SIGCSE. His work has also been recognized by industry, including Amazon Web Services, where he interned and applied his work on configuration file analysis. He was invited to the Heidelberg Laureate Forum and has received the Advanced Graduate Leadership award from Yale. He helped found the computer science department at Geumgang University in South Korea, and has taught a Creative Embedded Systems course at Yale.