Abstract: Quantum algorithms are useful for a variety of problems in search and
optimization. This line of work started with Grover's quantum search algorithm
which achieved a quadratic speedup over naive exhaustive search but has now
developed far beyond it.

In this talk, we describe three recent results in this area:

1. We show that, for any classical algorithm that uses a random walk to find an
object with some property (by walking until the random walker reaches such an
object), there is an almost quadratically faster quantum algorithm
(https://arxiv.org/abs/1903.07493).

2. We show that the best known exponential time algorithms for solving several
NP-complete problems (such as Travelling Salesman Problem or TSP) can be
improved quantumly (https://arxiv.org/abs/1807.05209). For example, for the
TSP, the best known classical algorithm needs time O(2^n) but our quantum
algorithm solves the problem in time O(1.728...^n).

3. We show a almost quadratic quantum speedup for a number of geometric problems
such as finding three points that are on the same line
(https://arxiv.org/abs/2004.08949).

Location https://zoom.us/j/94577321297?pwd=N3l5K1ZtZ3E1aytnWlBkL1FUazNXZz09
Meeting ID 945 7732 1297
Passcode 205903

Information about the series and recordings of previous talks can be found at
https://www.mpi-inf.mpg.de/departments/algorithms-complexity/quantum-lecture-series

Hosts: Ignacio Ciraq (MPIQ) and Kurt Mehlhorn (MPI-INF).

https://explainable-intelligent.systems/lectures/

Abstract
As machine learning (ML) is increasingly used for decision making in scenarios that impact humans, there is a growing awareness of its potential for unfairness. A large body of recent work has focused on proposing formal notions of fairness in ML, as well as approaches to mitigate unfairness. However, there is a disconnect between the ML fairness literature and the needs to operationalize fairness in practice.

This dissertation brings ML fairness closer to real-world applications by developing new models and methods that address key challenges in operationalizing fairness in practice.

*First, we tackle a key assumption in the group fairness literature that sensitive demographic attributes such as race and gender are known upfront, and can be readily used in model training to mitigate unfairness. In practice, factors like privacy and regulation often prohibit ML models from collecting or using protected attributes in decision making. To address this challenge we introduce the novel notion of computationally-identifiable errors and propose Adversarially Reweighted Learning (ARL), an optimization method that seeks to improve the worst-case performance over unobserved groups, without requiring access to the protected attributes in the dataset.

*Second, we argue that while group fairness notions are a desirable fairness criterion, they are fundamentally limited as they reduce fairness to an average statistic over pre-identified protected groups. In practice, automated decisions are made at an individual level, and can adversely impact individual people irrespective of the group statistic. We advance the paradigm of individual fairness by proposing iFair (individually fair representations), an optimization approach for learning a low dimensional latent representation of the data with two goals: to encode the data as well as possible, while removing any information about protected attributes in the transformed representation.

*Third, we advance the individual fairness paradigm, which requires that similar individuals receive similar outcomes. However, similarity metrics computed over observed feature space can be brittle, and inherently limited in their ability to accurately capture similarity between individuals. To address this, we introduce a novel notion of fairness graphs to capture nuanced expert knowledge on which individuals should be treated similarly with respect to the ML objective. We cast the problem of individual fairness into graph embedding, and propose PFR (pairwise fair representations), a method to learn a unified pairwise fair representation of the data.

*Fourth, we tackle the challenge that production data after model deployment is constantly evolving. As a consequence, in spite of the best efforts in training a fair model, ML systems can be prone to failure risks due to a variety of unforeseen failure risks. We propose Risk Advisor, a model-agnostic meta-learner to predict potential failure risks and to give guidance on the sources of uncertainty inducing the risks, by leveraging information theoretic notions of aleatoric and epistemic uncertainty.

Extensive experiments on a variety of real-world and synthetic datasets show that our proposed methods are viable in practice.

http://domino.mpi-inf.mpg.de/internet/events.nsf/0/E739258AF6B96B47C125883F004D4670

https://www.uni-saarland.de/page/tdot.html

or via Zoom: https://zoom.us/j/99457028566?pwd=bGllck5vS05iYnhtMGVCUzFGS1JqUT09
Meeting ID: 994 5702 8566
Passcode: 780865

Abstract:

Mistrust over traditional financial institutions is motivating the development of decentralized financial infrastructures based on blockchains. In particular, Consortium blockchains (such as the Linux Foundation Hyperledger and Facebook’s diem) are emerging as the approach preferred by businesses. These systems allow only a well-known set of mutually distrustful parties to add blocks to the blockchain; in this way, they aim to retain the benefits of decentralization without embracing the cyberpunk philosophy that informed Nakamoto’s disruptive vision. At the core of consortium blockchains is State Machine Replication, a classic technique borrowed from fault tolerant distributed computing; to ensure the robustness of their infrastructure, consortium blockchains actually borrow the Byzantine-tolerant version of this technique, which guarantees that the blockchain will operate correctly even if as many as about a third of the contributing parties are bent on cheating.

But, sometimes, “a borrowing is a sorrowing”.

I will discuss why Byzantine-tolerant state machine replication is fundamentally incapable of recognizing, never mind preventing, an ever present scourge of financial exchanges: the fraudulent manipulation of the order in which transactions are processed — and how its specification needs to be expanded to give it a fighting chance.

But is it possible to completely eliminate the ability of Byzantine parties to engage in order manipulation? What meaningful ordering guarantees can be enforced? And at what cost?

Bio:

Lorenzo Alvisi is the Tisch University Professor of Computer Science at Cornell University. Prior to joining Cornell, he held an endowed professorship at UT Austin, where he is now a Distinguished Professor Emeritus. Lorenzo received his Ph.D. in 1996 from Cornell, after earning a Laurea cum Laude in Physics from the University of Bologna. His research interests span theory and practice of distributed computing, with a focus on scaling strong consistency and dependability guarantees. He is a Fellow of the ACM and IEEE , an Alfred P. Sloan Foundation Fellow, and the recipient of a Humboldt Research Award, an NSF Career Award, and several teaching awards. He serves on the editorial boards of ACM TOCS and Springer’s Distributed Computing, and on the steering committee of Eurosys and SOSP . Besides distributed computing, he is passionate about classical music and red Italian motorcycles.

Either at MPI-SWS Saarbrücken, E1 5, room 002

or videocast to MPI-SWS Kaiserslautern, G26, room 111

or via Zoom: https://zoom.us/j/99457028566?pwd=bGllck5vS05iYnhtMGVCUzFGS1JqUT09
Meeting ID: 994 5702 8566
Passcode: 780865

Abstract:

The Skolem Problem asks how to determine algorithmically whether a given linear recurrence sequence (such as the Fibonacci numbers) has a zero. It is a central question in dynamical systems and number theory, and has many connections to other branches of mathematics and computer science. Unfortunately, its decidability has been open for nearly a century! In this talk, I will present a brief survey of what is known on the Skolem Problem and related questions, including recent and ongoing developments.

Bio:

Joël Ouaknine is a Scientific Director at the Max Planck Institute for Software Systems in Saarbruecken, Germany. His research interests straddle theoretical computer science and mathematics, and lie mainly at the intersection of dynamical systems and computation, making use of tools from number theory, Diophantine geometry, algebraic geometry, and mathematical logic. Joel studied mathematics at McGill University, and received a PhD in Computer Science from Oxford in 2001. He
subsequently held postdoc positions at Tulane University and Carnegie Mellon University, and became Full Professor of Computer Science at Oxford in 2010. He received the Roger Needham Award in 2010, an ERC grant in 2015, and was elected member of Academia Europaea in 2020; the same year he also received the Arto Salomaa Prize (jointly with James Worrell), for "outstanding contributions to Theoretical Computer Science, in particular to the theory of timed automata and to the analysis of dynamical systems". He was elected Fellow of the ACM in 2021 for "contributions to algorithmic analysis of dynamical systems".

https://www.hannovermesse.de/en/

https://www.hannovermesse.de/en/