Sebastian Pokutta

Sebastian Pokutta

Auto-generated profile, based on publicly available information

Sebastian Pokutta

Zuse Institute Berlin, Berlin, Germany

Research Focus & Metrics

Academic Career Length

16Years (2011-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 October 2024 in Nature Reviews Physics
Verified
Journal Article
Closed access
PDF file
AAAmira Abbas
Amira Abbas
AAAndris Ambainis
Andris Ambainis
BABrandon Augustino
Brandon Augustino
ABAndreas Bärtschi
Andreas Bärtschi
HBHarry Buhrman
Harry Buhrman
CZChrista Zoufal
Christa Zoufal

18 October 2023 in Physical Review Research
Verified
Journal Article
Open access
PDF file
SDSébastien Designolle
Sébastien Designolle
GIGabriele Iommazzo
Gabriele Iommazzo
MBMathieu Besançon
Mathieu Besançon
SKSebastian Knebel
Sebastian Knebel
PGPatrick Gelß
Patrick Gelß
SPSebastian Pokutta
Sebastian Pokutta
In Bell scenarios with two outcomes per party, we algorithmically consider the two sides of the membership problem for the local polytope: Constructing local models and deriving separating hyperplanes, that is, Bell inequalities. We take advantage of the recent developments in so-called Frank-Wolfe algorithms to significantly increase the convergence rate of existing methods. First, we study the threshold value for the nonlocality of two-qubit Werner states under projective measurements. Here, we improve on both the upper and lower bounds present in the literature. Importantly, our bounds are entirely analytical; moreover, they yield refined bounds on the value of the Grothendieck constant of order three: 1.4367⩽KG(3)⩽1.4546. Second, we demonstrate the efficiency of our approach in multipartite Bell scenarios, and present local models for all projective measurements with visibilities noticeably higher than the entanglement threshold. We make our entire code accessible as a julia library called BellPolytopes.jl.

13 December 2023 in Jahresbericht der Deutschen Mathematiker-Vereinigung
Verified
Journal Article
Open access
PDF file
SPSebastian Pokutta
Sebastian Pokutta
In this paper we provide an introduction to the Frank-Wolfe algorithm, a method for smooth convex optimization in the presence of (relatively) complicated constraints. We will present the algorithm, introduce key concepts, and establish important baseline results, such as e.g., primal and dual convergence. We will also discuss some of its properties, present a new adaptive step-size strategy as well as applications.

6 February 2015 in IEEE Journal of Selected Topics in Signal Processing
Verified
Journal Article
Open access
GBGabor Braun
Gabor Braun
SPSebastian Pokutta
Sebastian Pokutta
YXYao Xie
Yao Xie
We present an information-theoretic framework for sequential adaptive compressed sensing, Info-Greedy Sensing, where measurements are chosen to maximize the extracted information conditioned on the previous measurements. We show that the widely used bisection approach is Info-Greedy for a family of $k$ -sparse signals by connecting compressed sensing and blackbox complexity of sequential query algorithms, and present Info-Greedy algorithms for Gaussian and Gaussian mixture model (GMM) signals, as well as ways to design sparse Info-Greedy measurements. Numerical examples demonstrate the good performance of the proposed algorithms using simulated and real data: Info-Greedy Sensing shows significant improvement over random projection for signals with sparse and low-rank covariance matrices, and adaptivity brings robustness when there is a mismatch between the assumed and the true distributions.

22 December 2014
Verified
Conference Paper
Open access
GBGábor Braun
Gábor Braun
SPSebastian Pokutta
Sebastian Pokutta
The groundbreaking work of Rothvo{\ss} [arxiv:1311.2369] established that every linear program expressing the matching polytope has an exponential number of inequalities (formally, the matching polytope has exponential extension complexity). We generalize this result by deriving strong bounds on the polyhedral inapproximability of the matching polytope: for fixed $0 < \varepsilon < 1$, every polyhedral $(1 + \varepsilon / n)$-approximation requires an exponential number of inequalities, where $n$ is the number of vertices. This is sharp given the well-known $\rho$-approximation of size $O(\binom{n}{\rho/(\rho-1)})$ provided by the odd-sets of size up to $\rho/(\rho-1)$. Thus matching is the first problem in $P$, whose natural linear encoding does not admit a fully polynomial-size relaxation scheme (the polyhedral equivalent of an FPTAS), which provides a sharp separation from the polynomial-size relaxation scheme obtained e.g., via constant-sized odd-sets mentioned above. Our approach reuses ideas from Rothvo{\ss} [arxiv:1311.2369], however the main lower bounding technique is different. While the original proof is based on the hyperplane separation bound (also called the rectangle corruption bound), we employ the information-theoretic notion of common information as introduced in Braun and Pokutta [http://eccc.hpi-web.de/report/2013/056/], which allows to analyze perturbations of slack matrices. It turns out that the high extension complexity for the matching polytope stem from the same source of hardness as for the correlation polytope: a direct sum structure.Comment: 21 pages, 3 figure

8 May 2014 in Mathematical Programming
Verified
Journal Article
Closed access
PDF file
JBJop Briët
Jop Briët
DDDaniel Dadush
Daniel Dadush
SPSebastian Pokutta
Sebastian Pokutta