Professor Romit Roy Choudhury, University of Illinois, Urbana Champaign
Professor Kobbi Nissim, Georgetown University
Professor Lance Fortnow, Illinois Institute of Technology

Contact Person
Dr SHOKRI, Reza, NUS Presidential Young Professor, School of Computing

  06 Jan 2020 Monday, 10:00 AM to 05:00 PM

 SR1, COM1-02-06

This is a distinguished talk as part of the NUS Computer Science Research Week 2020

10:00 – 11:30 Could Earphones be The Next Computing Platform after Smartphones? – Romit Roy Choudhury
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 smart phones. 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.

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

13:00 – 14:30 TBA – Kobbi Nissim

15:30 – 17:00 The Early Days of Interactive Proofs – Lance Fortnow
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.

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.