COMPUTER SCIENCE RESEARCH WEEK JANUARY 2020
Professor Kobbi Nissim, Georgetown University
Professor Lance Fortnow, Illinois Institute of Technology
COM1 Level 2
SR1, COM1-02-06
This is a distinguished talk as part of the NUS Computer Science Research Week 2020 https://researchweek.comp.nus.edu.sg/
10:00 - 11:30 Could Earphones be The Next Computing Platform after Smartphones? - Romit Roy Choudhury
Abstract:
This talk will argue that "earables" is the next significant mobile computing platform after smartphones. With numerous sensors, processors, and radios getting embedded into modern earphones, we envision these devices to create a new eco-system in the next 5 years. Earables will run voice assistants like Alexa; will sense human motion and gestures; will track health metrics through the ear; and will open new forms of interactions, such as acoustic AR/VR. The leap from today's ear-phones to "earables" will mimmic the transformation from basic-phones to smartphones. Today's smartphones are hardly a calling device anymore, much like how tomorrow's earables will hardly be a wireless speaker or microphone. This talk will attempt to foresee the road ahead, starting with a broader vision, and followed by concrete research questions that emerge from it.
Biodata:
Romit Roy Choudhury is a Jerry Sanders Scholar and Professor of ECE and CS at the University of Illinois at Urbana Champaign (UIUC). He joined UIUC from Fall 2013, prior to which he was an Associate Professor at Duke University. His research interests are in wireless networking, embedded sensing, and applied signal processing. Along with his students, he received a few research awards, including the ACM Sigmobile Rockstar Award, the UIUC Distinguished Alumni Award, the 2017 ACM MobiSys Best Paper Award, etc. He was elevated to IEEE Fellow in 2018. Visit Romit's Systems Networking Research Group (SyNRG) at http://synrg.csl.illinois.edu.
13:00 - 14:30 Legal Theorems of Privacy - Kobbi Nissim
Abstract:
There are significant gaps between legal and technical thinking around data privacy. Technical standards such as k-anonymity and differential privacy are described using mathematical language and strive for mathematical rigor whereas legal standards are not rigorous from a mathematical point of view and often resort to concepts such as de-identification and anonymization which they only partially define. As a result, arguments about the adequacy of technical privacy measures for satisfying legal privacy often lack rigor, and their conclusions are uncertain. The uncertainty is exacerbated by a litany of successful privacy attacks on privacy measures thought to meet legal expectations but then shown to fall short of doing so.
We ask whether it is possible to introduce mathematical rigor into such analyses so as to make formal claims and prove “legal theorems” that technical privacy measures meet legal expectations. For that, we explore some of the gaps between these two very different approaches, and present initial strategies towards bridging these gaps. In particular, we focus on the concept of singling out from the EU’s General Data Protection Regulation (GDPR). To capture this concept, we define a new type of privacy attack, predicate singling out, where an adversary finds a predicate matching exactly one row in a database with probability significantly better than a statistical baseline. We then argue that any data release mechanism that purports to “render anonymous” data under the GDPR should prevent predicate singling out. Hence, the concept has legal consequences as it can be used as a yardstick for arguing whether data release mechanisms meet the GDPR standard of data anonymization.
Biodata:
Professor Kobbi Nissim is a McDevitt Chair at the Department of Computer Science, Georgetown University and affiliated with Georgetown Law. Nissim’s work is focused on the mathematical formulation and understanding of privacy. His work from 2003 and 2004 with Dinur and Dwork initiated rigorous foundational research of privacy and in 2006 he introduced differential privacy with Dwork, McSherry and Smith. Nissim was awarded the Caspar Bowden Privacy for research in Privacy Enhancing Technology in 2019, the Gödel Prize in 2017, IACR TCC Test of Time Awards in 2016 and in 2018, and the ACM PODS Alberto O. Mendelzon Test-of-Time Award in 2013
15:30 - 17:00 The Early Days of Interactive Proofs - Lance Fortnow
Abstract:
Consider the clique problem, given a graph is there a collection of vertices of a given size that are all connected to each other. A powerful wizard could convince you that a large clique exists, just provide the set of vertices and you can check that all pairs are connected. This notion made formal the class NP, the basis of the famous P v NP problem.
What if the wizard wanted to convince you that no clique existed? You would seemingly need to check all large subsets. Thirty years ago, Lund, Fortnow, Karloff and Nisan showed that a wizard can convince a mere mortal if the mortal can ask random questions. Shamir shortly thereafter extended these results to everything computable in a reasonable amount of memory, the IP = PSPACE result.
This talk will go over the early history of interactive proofs, a series of exciting results in the late 80's and early 90's, from its roots in cryptography and group theory to its applications in approximation and beyond.
Biodata:
Lance Fortnow is Dean of the College of Science at the Illinois Institute of Technology. Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989 under the supervision of Michael Sipser. Before he joined Illinois Tech in 2019, Fortnow was the chair of the School of Computer Science at the Georgia Institute of Technology and previously was a professor at Northwestern University and the University of Chicago, a senior research scientist at the NEC Research Institute and a one-year visitor at CWI and the University of Amsterdam. From 2007 to 2018 Fortnow held an adjoint professorship at the Toyota Technological Institute at Chicago.
Fortnow's research spans computational complexity and its applications. His work on interactive proof systems and time-space lower bounds for satisfiability have led to his election as a 2007 ACM Fellow. In addition, he was an NSF Presidential Faculty Fellow from 1992-1998 and a Fulbright Scholar to the Netherlands in 1996-97.
Among his many activities, Fortnow served as the founding editor-in-chief of the ACM Transaction on Computation Theory, served as chair of ACM SIGACT and on the Computing Research Association board of directors. He served as chair of the IEEE Conference on Computational Complexity from 2000-2006. Fortnow originated and co-authors the Computational Complexity weblog since 2002, the first major theoretical computer science blog. He has thousands of followers on Twitter.
Fortnow's survey The Status of the P versus NP Problem is one of the CACM's most downloaded articles. Fortnow has written a popular science book The Golden Ticket: P, NP and the Search for the Impossible loosely based on that article.