Research Institutes

Join Zoom Meeting
https://zoom.us/j/99715655535?pwd=ZnVlTXdrcUgwREo2S1NVcG5wcmY4QT09

Meeting ID: 997 1565 5535
Passcode: jls-21

We kindly ask participants to please switch off their
microphone and camera and to only activate them if
they wish to ask any questions.

---------------------------------------------------------------

Abstract:

An ever-increasing amount of data to be analyzed
raises novel challenges for the theory of computation.
How can we prove computational difficulty of a
seemingly simple task when facing enormous data sets?
Developing such methods is essential for determining
which problems can or cannot be solved at a large scale.

Fine-grained complexity theory in P provides
corresponding methods by establishing tight connections
between fundamental algorithmic problems. In particular,
we show that many natural sequence comparison problems
cannot be solved in truly subquadratic time, assuming
a stronger version of the famous P ≠ NP conjecture.
These results give rigorous insights into the challenges
encountered, e.g., in the context of genome comparison,
and even aid in developing novel efficient algorithms.

Despite such early successes, this young theory is
still in its infancy: In particular, most of the
current results establish connections between isolated
algorithmic problems, rather than between classes of
problems. Can we establish a more encompassing theory
and turn the current problem-centric state of the art
to a full-fledged structural complexity theory for
large data sets? Towards this end, we discuss a quest
for completeness and classification theorems
(inspired by a finite-model-theoretic approach and
the Dichotomy Theorem for constraint satisfaction
problems), and present promising initial results.

Presenter:

Marvin Künnemann: https://people.mpi-inf.mpg.de/~marvin/

Via Zoom: https://zoom.us/j/93495833728?pwd=Z1Vjb0JtR3d4VUU4emI5Znpac2dwZz09

Abstract
To reduce capital and operational costs, many enterprises are outsourcing their networks to third-party providers. Two popular outsourcing models exist today: the first is to outsource network functions (e.g., a firewall) to run on third-party infrastructure such as public clouds; the other is to use in-house infrastructure and only outsource network services (e.g., troubleshooting) to managed service providers. Unfortunately, existing tools for both outsourcing models provide enterprises an “all-or-nothing” solution, where they must have to relinquish control over outsourced components and tasks. While this is convenient in many cases, its lack of transparency and accountability has raised security concerns.

In this talk, I will present my research on designing practical network tasks outsourcing systems with correctness guarantees. First, I will present AuditBox, the first system to audit virtualized network functions. I will show how AuditBox achieves runtime correctness and offline auditability, promoting the outsourcing of network functions for security-sensitive enterprises. Then, I will present Heimdall, a system to enable a fine-grained least-privilege for managed network services, ensuring that untrusted providers comply with an enterprise’s policy goals.

Bio
Guyue (Grace) Liu (http://grace-liu.github.io/) is a postdoctoral researcher at Carnegie Mellon University. Before joining CMU, She received her Ph.D. in Computer Science at the George Washington University and B.S. from Beijing University of Posts and Telecommunications. Her research has appeared in top networking (e.g., SIGCOMM, NSDI) and systems (e.g, ATC, Middleware) venues, and has gained wide community recognition, including the 2019 EECS Rising Stars, HP Helion OpenStack Scholarship, and RTAS’18 Best Student Paper awards. She
was selected as one of the ten N2Women rising stars in networking and communications in 2019.

Paper link
http://grace-liu.github.io/static/papers/21-NSDI-auditbox.pdf

Zoom Meeting Instructions:

Join Zoom Meeting
https://zoom.us/j/93495833728?pwd=Z1Vjb0JtR3d4VUU4emI5Znpac2dwZz09

Meeting ID: 934 9583 3728
Passcode: 011184
One tap mobile
+493056795800,,93495833728# Germany
+496938079883,,93495833728# Germany

Join Zoom Meeting

https://zoom.us/j/99457028566?pwd=bGllck5vS05iYnhtMGVCUzFGS1JqUT09

Meeting ID: 994 5702 8566
Passcode: 780865

Abstract:
Cyber-physical systems (CPSs) combine cyber capabilities, such as computation or communication, with physical capabilities, such as motion or other physical processes. Cars, aircraft, and robots are prime examples, because they move physically in space in a way that is determined by discrete computerized control algorithms. Designing these algorithms is challenging due to their tight coupling with physical behavior, while it is vital that these algorithms be correct because we rely on them for safety-critical tasks.

This talk highlights some of the most fascinating aspects of the logical foundations for developing cyber-physical systems with the mathematical rigor that their safety-critical nature demands. The underlying logic, differential dynamic logic, provides an integrated specification and verification language for dynamical systems, such as hybrid systems that combine discrete transitions and continuous evolution along differential equations.

In addition to providing a strong theoretical foundation for CPS, differential dynamic logics have been instrumental in verifying many applications, including the Airborne Collision Avoidance System ACAS X, the European Train Control System ETCS, automotive systems, mobile robot navigation, and a surgical robotic system for skull-base surgery. Logic is the foundation to provably transfer safety guarantees about models to CPS implementations. This technology is also the key ingredient behind Safe AI for CPS.

Speaker Bio.:
André Platzer is a Professor of Computer Science at Carnegie Mellon University. He develops the logical foundations of cyber-physical systems to characterize their fundamental principles and to answer the question how we can trust a computer to control physical processes. Dr. Platzer has a Ph.D. from the University of Oldenburg, Germany, received an ACM Doctoral Dissertation Honorable Mention and NSF CAREER Award, and was named one of the Brilliant 10 Young Scientists by the Popular Science magazine and one of the AI's 10 to Watch by the IEEE Intelligent Systems Magazine.

Please contact the host directly (viktor@mpi-sws.org) if you would like to meet with André Platzer.