Research Seminar

Faster algorithms for optimization problems are among the main potential applications for future quantum computers. There has been interesting progress in this area in recent years, for instance improved quantum algorithms for gradient descent and for solving linear and semidefinite programs. In this talk I will survey what we know about quantum speed-ups both for discrete and for continuous optimization, with a bit more detail about two speed-ups I worked on recently: for regularized linear regression and for Principal Component Analysis. I’ll also discuss some issues with this line of work, in particular that quadratic or subquadratic quantum speed-ups will only kick in for very large instance sizes and that many of these algorithms require some kind of quantum RAM.

This talk will begin with a brief introduction to classical Ramsey theory (whose main idea is that complete disorder is impossible) and a discussion of a few well-known results. No specialized background knowledge in combinatorics is required for this talk. Then joint work with Will Smith from University of South Carolina (formerly Davidson) on a Ramsey theory problem based on the integer grid will be presented. Specifically, the L-theorem (an easy corollary of the Gallai-Witt theorem) states that for any integer k, there exists some n such that a k-colored n by n grid must contain a monochromatic "L" (a series of points of the form (i, j), (i, j+t), and (i+t, j+t) for some positive integer t. In this talk, we will investigate the upper bound for the smallest integer n such that a 3-colored n by n integer grid is guaranteed to contain a monochromatic L. We use various methods, such as counting intervals on the main diagonal, to improve the upper bound from 2593 to 493. For the lower bound, we match the lower bound of 21 generated by Canacki et al. (2023) and discuss possible improvements.

Many recent advances in the field of AI, including tools such as ChatGPT, rely on the training of foundation models. Foundation models are fine-tuned to avoid unsafe or otherwise problematic behavior, so that, for example, they refuse to comply with requests for help with committing crimes, or with producing racist text. One approach to fine-tuning, called reinforcement learning from human feedback, learns from humans’ expressed preferences over multiple outputs. Another approach is constitutional AI, in which the input from humans is a list of high-level principles. But which humans get to provide the feedback or principles? And how is their potentially diverging input aggregated into consistent data about “collective” preferences or otherwise used to make collective choices about model behavior? In this talk, I argue that the field of social choice is well positioned to address these questions, and discuss ways forward for this agenda, drawing on discussions in a recent workshop on Social Choice for AI Ethics and Safety held in Berkeley, CA, USA in December 2023.

The simplex method is a very efficient algorithm. In this talk we see a few of the state-of-the-art theories for explaining this observation. We will discuss what it takes for a mathematical model to explain an algorithm’s qualities, and whether existing theories meet this bar. Following this, we will question what the simplex method is and if the theoretician’s simplex method is the same algorithm as the practitioner’s simplex method.

In light of the ongoing developments in the climate crisis, it is necessary to consider factors beyond the sole economic perspective in energy supply network planning. This gives rise to a classical multiobjective optimization problem involving conflicting objective functions. The presence of choices in the model, coupled with the consideration of stationary flow equations, results in an opti mization problem with a mixed-integer nonlinear structure. Following a short introduction of some model-specific details and arising challenges, we present a novel method for computing an enclosure of the nondominated set of such prob lems. We prove finite convergence and demonstrate its effectiveness through numerical experiments. We conclude by offering a preview of ongoing extensions of this work.

Sparsity of matrices can be exploited, in particular, to speed up algorithms in various applications, e.g., in linear system solvers or second-order optimization schemes. This motivates to consider the matrix sparsification problem, in which we seek an equivalent (column-space preserving) representation of a given matrix with as few nonzero entries as possible. We derive sequential solution approaches based on bilinear and linear mixed-integer programs, respectively, and point out connections to certain machine learning tasks. One particular problem appears as a subproblem or special case in both these approaches: Finding a sparsest nonzero vector in the nullspace of a matrix. We will outline how a dedicated branch-and-cut method for this problem can be utilized in the envisioned matrix sparsification algorithms, and touch upon some open questions and challenges of our ongoing work