Sebastian Pokutta
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Sebastian Pokutta has a total of 215 co-authors. Here are the top co-authors by number of shared publications:
- Gábor Braun
ISyE Georgia Institute of Technology Atlanta GA
14 shared publications - Mathieu Besançon
Université Grenoble Alpes, Inria, LIG, Saint-Martin-d’Hères, France
10 shared publications - Elias Wirth
Institute of Mathematics, Berlin Institute of Technology, Berlin, Germany
9 shared publications - Sébastien Designolle
Zuse Institute Berlin
8 shared publications - Christoph Spiegel
Department for AI in Society, Science, and Technology Zuse Institute Berlin Germany
7 shared publications - Max Zimmer
Department for AI in Society, Science, and Technology Zuse Institute Berlin Germany
7 shared publications
Latest Publications
- 2 November 2026
- Published by American Physical Society (APS) in Physical Review A
- Vol. 114 (5)
Unified toolbox for multipartite entanglement certification
- 2 November 2026
- Published by American Physical Society (APS) in Physical Review A
- Vol. 114 (5)
Unified toolbox for multipartite entanglement certification
- Open Access
- 27 October 2026
- Published by American Physical Society (APS) in Physical Review Research
- Vol. 8 (4) , 049001
Erratum: Improved local models and new Bell inequalities via Frank-Wolfe algorithms [Phys. Rev. Research 5 , 043059 (2023)]
Phys. Rev. Research 8, 049001 (2026)
- 27 October 2026
- Published by American Physical Society (APS) in Physical Review Research
- Vol. 8 (4) , 049001
Open AccessErratum: Improved local models and new Bell inequalities via Frank-Wolfe algorithms [Phys. Rev. Research 5 , 043059 (2023)]
Phys. Rev. Research 8, 049001 (2026)
- Open Access
- 3 September 2026
- Published by Springer Nature in Mathematical Programming Computation
- p. 1-25
A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
We propose a primal heuristic for quadratic mixed-integer problems. Our method extends the Boscia framework – originally a mixed-integer convex solver leveraging a Frank-Wolfe-based branch-and-bound approach – to address nonconvex quadratic objective functions and constraints. We reformulate nonlinear constraints, introduce preprocessing steps, and a suite of heuristics including rounding strategies, gradient-guided selection, and large neighborhood search techniques that exploit integer-feasible vertices generated during the Frank-Wolfe iterations. Computational results demonstrate the effectiveness of our method in solving challenging MIQCQPs, achieving improvements on QPLIB instances within minutes and winning first place in the Land-Doig MIP Computational Competition 2025.
- 3 September 2026
- Published by Springer Nature in Mathematical Programming Computation
- p. 1-25
Open AccessA Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
We propose a primal heuristic for quadratic mixed-integer problems. Our method extends the Boscia framework – originally a mixed-integer convex solver leveraging a Frank-Wolfe-based branch-and-bound approach – to address nonconvex quadratic objective functions and constraints. We reformulate nonlinear constraints, introduce preprocessing steps, and a suite of heuristics including rounding strategies, gradient-guided selection, and large neighborhood search techniques that exploit integer-feasible vertices generated during the Frank-Wolfe iterations. Computational results demonstrate the effectiveness of our method in solving challenging MIQCQPs, achieving improvements on QPLIB instances within minutes and winning first place in the Land-Doig MIP Computational Competition 2025.
- Open Access
- 11 August 2026
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 95 (2) , 679-698
Adaptive open-loop step-sizes for accelerated convergence rates of the Frank–Wolfe algorithm
Recent work has shown that, in several growth settings, the Frank–Wolfe algorithm () with fixed-parameter open-loop step-sizes $$\eta _t = \frac{\ell }{t+\ell }$$ for $$\ell \in \mathbb {N}_{\ge 2}$$ can converge faster than the classical $${\mathcal {O}}(t^{-1})$$ rate. In the strong-growth regime, increasing $$\ell $$ improves the asymptotic rate, so no single fixed choice of $$\ell $$ is uniformly preferable. We study the broader family of adaptive open-loop step-sizes $$\eta _t = \frac{g(t)}{t+g(t)}$$ and extend the affine-invariant analysis from the fixed-parameter case to non-decreasing functions g for which the resulting step-size sequence is non-increasing. For the log-adaptive choice $$g(t)=2+\log (t+1)$$ , this yields a schedule that matches the asymptotic rates of fixed-parameter rules up to polylogarithmic factors in the weak-growth settings considered here, while improving the asymptotic sublinear rate in strong-growth settings. We also report numerical experiments demonstrating the efficacy of the new proposed step-size rule.- 11 August 2026
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 95 (2) , 679-698
Open AccessAdaptive open-loop step-sizes for accelerated convergence rates of the Frank–Wolfe algorithm
Recent work has shown that, in several growth settings, the Frank–Wolfe algorithm () with fixed-parameter open-loop step-sizes $$\eta _t = \frac{\ell }{t+\ell }$$ for $$\ell \in \mathbb {N}_{\ge 2}$$ can converge faster than the classical $${\mathcal {O}}(t^{-1})$$ rate. In the strong-growth regime, increasing $$\ell $$ improves the asymptotic rate, so no single fixed choice of $$\ell $$ is uniformly preferable. We study the broader family of adaptive open-loop step-sizes $$\eta _t = \frac{g(t)}{t+g(t)}$$ and extend the affine-invariant analysis from the fixed-parameter case to non-decreasing functions g for which the resulting step-size sequence is non-increasing. For the log-adaptive choice $$g(t)=2+\log (t+1)$$ , this yields a schedule that matches the asymptotic rates of fixed-parameter rules up to polylogarithmic factors in the weak-growth settings considered here, while improving the asymptotic sublinear rate in strong-growth settings. We also report numerical experiments demonstrating the efficacy of the new proposed step-size rule. - Open Access
- 12 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 227-236
Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search
We give explicit low-rank bilinear non-commutative schemes for multiplying structured n × n matrices with 2 ≤ n ≤ 5, which serve as building blocks for recursive algorithms with improved multiplicative factors in asymptotic complexity. Our schemes are discovered over \(\mathbb {F}_2\) or \(\mathbb {F}_3\) and lifted to \(\mathbb {Z}\) or \(\mathbb {Q}\) . Using a flip graph search over tensor decompositions, we derive schemes for general, upper-triangular, lower-triangular, symmetric, and skew-symmetric inputs, as well as products of a structured matrix with its transpose. These schemes improve asymptotic constants for 13 of 15 structured formats. In particular, we obtain 4 × 4 rank-34 schemes for both multiplying a general matrix by its transpose and an upper-triangular matrix by a general matrix, improving the asymptotic factor from 26/41 (0.634) to 22/37 (0.595). Additionally, using \(\mathbb {F}_3\) flip graphs, we discover schemes over \(\mathbb {Q}\) that fundamentally require the inverse of 2, including a 2 × 2 symmetric-symmetric multiplication of rank 5 and a 3 × 3 skew-symmetric-general multiplication of rank 14 (improving upon AlphaTensor’s 15).- 12 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 227-236
Open AccessFaster Algorithms for Structured Matrix Multiplication via Flip Graph Search
We give explicit low-rank bilinear non-commutative schemes for multiplying structured n × n matrices with 2 ≤ n ≤ 5, which serve as building blocks for recursive algorithms with improved multiplicative factors in asymptotic complexity. Our schemes are discovered over \(\mathbb {F}_2\) or \(\mathbb {F}_3\) and lifted to \(\mathbb {Z}\) or \(\mathbb {Q}\) . Using a flip graph search over tensor decompositions, we derive schemes for general, upper-triangular, lower-triangular, symmetric, and skew-symmetric inputs, as well as products of a structured matrix with its transpose. These schemes improve asymptotic constants for 13 of 15 structured formats. In particular, we obtain 4 × 4 rank-34 schemes for both multiplying a general matrix by its transpose and an upper-triangular matrix by a general matrix, improving the asymptotic factor from 26/41 (0.634) to 22/37 (0.595). Additionally, using \(\mathbb {F}_3\) flip graphs, we discover schemes over \(\mathbb {Q}\) that fundamentally require the inverse of 2, including a 2 × 2 symmetric-symmetric multiplication of rank 5 and a 3 × 3 skew-symmetric-general multiplication of rank 14 (improving upon AlphaTensor’s 15). - Open Access
- 19 June 2026
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 10
Measurement incompatibility and quantum steering via linear programming
The problem of deciding whether a set of quantum measurements is jointly measurable is known to be equivalent to determining whether a quantum assemblage is unsteerable. This problem can be formulated as a semidefinite program (SDP). However, the number of variables and constraints in such a formulation grows exponentially with the number of measurements, rendering it intractable for large measurement sets. In this work, we circumvent this problem by transforming the SDP into a hierarchy of linear programs that compute upper and lower bounds on the incompatibility robustness with a complexity that grows polynomially in the number of measurements. The hierarchy is guaranteed to converge and it can be applied to arbitrary measurements – including non-projective POVMs (Positive Operator-Valued Measures) – in arbitrary dimensions. While convergence becomes impractical in high dimensions, in the case of qubits our method reliably provides accurate upper and lower bounds for the incompatibility robustness of sets with several hundred measurements in a short time using a standard laptop. We also apply our methods to qutrits, obtaining non-trivial upper and lower bounds in scenarios that are otherwise intractable using the standard SDP approach, although such bounds are significantly looser than the ones obtained in the qubit case. Finally, we show how our methods can be used to construct local hidden state models for states (i.e., to prove that a state cannot lead to steering under any possible local measurements), or conversely, to certify that a given state exhibits steering; for two-qubit quantum states, our approach is comparable to, and in some cases outperforms, the current best methods.
- 19 June 2026
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 10
Open AccessMeasurement incompatibility and quantum steering via linear programming
The problem of deciding whether a set of quantum measurements is jointly measurable is known to be equivalent to determining whether a quantum assemblage is unsteerable. This problem can be formulated as a semidefinite program (SDP). However, the number of variables and constraints in such a formulation grows exponentially with the number of measurements, rendering it intractable for large measurement sets. In this work, we circumvent this problem by transforming the SDP into a hierarchy of linear programs that compute upper and lower bounds on the incompatibility robustness with a complexity that grows polynomially in the number of measurements. The hierarchy is guaranteed to converge and it can be applied to arbitrary measurements – including non-projective POVMs (Positive Operator-Valued Measures) – in arbitrary dimensions. While convergence becomes impractical in high dimensions, in the case of qubits our method reliably provides accurate upper and lower bounds for the incompatibility robustness of sets with several hundred measurements in a short time using a standard laptop. We also apply our methods to qutrits, obtaining non-trivial upper and lower bounds in scenarios that are otherwise intractable using the standard SDP approach, although such bounds are significantly looser than the ones obtained in the qubit case. Finally, we show how our methods can be used to construct local hidden state models for states (i.e., to prove that a state cannot lead to steering under any possible local measurements), or conversely, to certify that a given state exhibits steering; for two-qubit quantum states, our approach is comparable to, and in some cases outperforms, the current best methods.
- Open Access
- 12 June 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Sustainable Computing
- Vol. PP (4) , 1-14
Sustainability via Large Language Model Right-sizing
Large language models (LLMs) are increasingly embedded in organizational workflows, raising concerns about energy use, costs, and data sovereignty. While benchmarks often celebrate cutting-edge models, real-world deployment requires a broader question: when is a smaller, locally deployable model “good enough”? This study evaluates eleven proprietary and open-weight LLMs on ten everyday occupational tasks, including summarizing, scheduling, and drafting emails and proposals. Using a dual-LLM evaluation framework, we automated task execution and standardized assessment across ten criteria of quality, accuracy, and ethical responsibility. Results show GPT-4o delivers top performance but with significantly higher costs and environmental impact. Smaller models such as Gemma-3 and Phi-4 performed strongly on most tasks, supporting their viability where cost-efficiency, local use, or privacy matter. A cluster analysis identified three groups-High, Balanced, and Baseline Performance Models-highlighting trade-offs between quality, control, and sustainability. Task type shaped effectiveness: conceptual tasks were most challenging, while aggregation and transformation tasks yielded better outcomes. We argue for shifting from performance-maximizing benchmarks to task- and context-aware sufficiency assessments that reflect organizational priorities. Our approach offers a replicable method to evaluate AI models from a sustainability perspective and provides practical recommendations for responsible LLM deployment.
- 12 June 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Sustainable Computing
- Vol. PP (4) , 1-14
Open AccessSustainability via Large Language Model Right-sizing
Large language models (LLMs) are increasingly embedded in organizational workflows, raising concerns about energy use, costs, and data sovereignty. While benchmarks often celebrate cutting-edge models, real-world deployment requires a broader question: when is a smaller, locally deployable model “good enough”? This study evaluates eleven proprietary and open-weight LLMs on ten everyday occupational tasks, including summarizing, scheduling, and drafting emails and proposals. Using a dual-LLM evaluation framework, we automated task execution and standardized assessment across ten criteria of quality, accuracy, and ethical responsibility. Results show GPT-4o delivers top performance but with significantly higher costs and environmental impact. Smaller models such as Gemma-3 and Phi-4 performed strongly on most tasks, supporting their viability where cost-efficiency, local use, or privacy matter. A cluster analysis identified three groups-High, Balanced, and Baseline Performance Models-highlighting trade-offs between quality, control, and sustainability. Task type shaped effectiveness: conceptual tasks were most challenging, while aggregation and transformation tasks yielded better outcomes. We argue for shifting from performance-maximizing benchmarks to task- and context-aware sufficiency assessments that reflect organizational priorities. Our approach offers a replicable method to evaluate AI models from a sustainability perspective and provides practical recommendations for responsible LLM deployment.
- 1 June 2026
- Published by Springer Nature
- p. 614-630
Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods
- 1 June 2026
- Published by Springer Nature
- p. 614-630
Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods
- 1 May 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 51 (2) , 1463-1485
Fast Convergence of Frank-Wolfe Algorithms on Polytopes
We provide a template to derive affine-invariant convergence rates for the following popular versions of the Frank-Wolfe algorithm on polytopes: vanilla Frank-Wolfe, Frank-Wolfe with away steps, Frank-Wolfe with blended pairwise steps, and Frank-Wolfe with in-face directions. Our template shows how the convergence rates follow from two affine-invariant properties of the problem, namely, error bound and extended curvature. These properties depend solely on the polytope and objective function but not on any affine-dependent object like norms. For each one of the above algorithms, we derive rates of convergence ranging from sublinear to linear depending on the degree of the error bound. Funding: Research reported in this paper was partially supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy—The Berlin Mathematics Research Center MATH (EXC-2046/1, project ID 390685689, BMS Stipend). Research reported in this paper was also partially supported by the Bajaj Family Chair at the Tepper School of Business, Carnegie Mellon University.
- 1 May 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 51 (2) , 1463-1485
Fast Convergence of Frank-Wolfe Algorithms on Polytopes
We provide a template to derive affine-invariant convergence rates for the following popular versions of the Frank-Wolfe algorithm on polytopes: vanilla Frank-Wolfe, Frank-Wolfe with away steps, Frank-Wolfe with blended pairwise steps, and Frank-Wolfe with in-face directions. Our template shows how the convergence rates follow from two affine-invariant properties of the problem, namely, error bound and extended curvature. These properties depend solely on the polytope and objective function but not on any affine-dependent object like norms. For each one of the above algorithms, we derive rates of convergence ranging from sublinear to linear depending on the degree of the error bound. Funding: Research reported in this paper was partially supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy—The Berlin Mathematics Research Center MATH (EXC-2046/1, project ID 390685689, BMS Stipend). Research reported in this paper was also partially supported by the Bajaj Family Chair at the Tepper School of Business, Carnegie Mellon University.
- Open Access
- 13 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 1-5
It’s Not Just the Prompt: Model Choice Dominates LLM Creative Output
- 13 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 1-5
Open AccessIt’s Not Just the Prompt: Model Choice Dominates LLM Creative Output