×

zbMATH — the first resource for mathematics

Pokutta, Sebastian

Compute Distance To:
Author ID: pokutta.sebastian Recent zbMATH articles by "Pokutta, Sebastian"
Published as: Pokutta, Sebastian
Homepage: http://www.pokutta.com/
External Links: MGP · ORCID · dblp · GND
Documents Indexed: 53 Publications since 2005, including 1 Book
Reviewing Activity: 4 Reviews

Publications by Year

Citations contained in zbMATH

40 Publications have been cited 302 times in 188 Documents Cited by Year
Linear vs. semidefinite extended formulations, exponential separation and strong lower bounds. Zbl 1286.90125
Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald
66
2012
Exponential lower bounds for polytopes in combinatorial optimization. Zbl 1333.90107
Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald
33
2015
Approximation limits of linear programs (beyond hierarchies). Zbl 1343.68308
Braun, Gábor; Fiorini, Samuel; Pokutta, Sebastian; Steurer, David
29
2015
A note on the extension complexity of the knapsack polytope. Zbl 1286.90168
Pokutta, Sebastian; Van Vyve, Mathieu
18
2013
Approximate computation of zero-dimensional polynomial ideals. Zbl 1176.13003
Heldt, Daniel; Kreuzer, Martin; Pokutta, Sebastian; Poulisse, Hennie
17
2009
Common information and unique disjointness. Zbl 1353.68072
Braun, Gábor; Pokutta, Sebastian
13
2016
The matching polytope does not admit fully-polynomial size relaxation schemes. Zbl 1372.68251
Braun, Gábor; Pokutta, Sebastian
9
2015
Inapproximability of combinatorial problems via small LPs and SDPs. Zbl 1321.90098
Braun, Gábor; Pokutta, Sebastian; Zink, Daniel
9
2015
On the rank of cutting-plane proof systems. Zbl 1284.03260
Pokutta, Sebastian; Schulz, Andreas S.
9
2010
Strict linear prices in non-convex European day-ahead electricity markets. Zbl 1282.90110
Martin, Alexander; Müller, Johannes C.; Pokutta, Sebastian
7
2014
Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube. Zbl 1219.90106
Pokutta, Sebastian; Stauffer, Gautier
7
2011
Information-theoretic approximations of the nonnegative rank. Zbl 1381.94044
Braun, Gábor; Jain, Rahul; Lee, Troy; Pokutta, Sebastian
6
2017
A polyhedral characterization of border bases. Zbl 1332.13021
Braun, Gábor; Pokutta, Sebastian
6
2016
On the existence of 0/1 polytopes with high semidefinite extension complexity. Zbl 1395.90241
Briët, Jop; Dadush, Daniel; Pokutta, Sebastian
6
2013
Approximation and online algorithms for multidimensional bin packing: a survey. Zbl 1398.68007
Christensen, Henrik I.; Khan, Arindam; Pokutta, Sebastian; Tetali, Prasad
5
2017
On the existence of 0/1 polytopes with high semidefinite extension complexity. Zbl 1325.90066
Briët, Jop; Dadush, Daniel; Pokutta, Sebastian
5
2015
Cutting-planes for weakly-coupled \(0/1\) second order cone programs. Zbl 1237.90160
Drewes, Sarah; Pokutta, Sebastian
5
2010
Lazifying conditional gradient algorithms. Zbl 07064051
Braun, Gábor; Pokutta, Sebastian; Zink, Daniel
4
2019
Strong reductions for extended formulations. Zbl 1419.90062
Braun, Gábor; Pokutta, Sebastian; Roy, Aurko
4
2016
Average case polyhedral complexity of the maximum stable set problem. Zbl 1359.68118
Braun, Gábor; Fiorini, Samuel; Pokutta, Sebastian
4
2014
Absolute graphs with prescribed endomorphism monoid. Zbl 1143.05040
Droste, Manfred; Göbel, Rüdiger; Pokutta, Sebastian
4
2008
Aggregation-based cutting-planes for packing and covering integer programs. Zbl 1405.90080
Bodur, Merve; Del Pia, Alberto; Dey, Santanu S.; Molinaro, Marco; Pokutta, Sebastian
3
2018
Hierarchical clustering via spreading metrics. Zbl 1441.62173
Roy, Aurko; Pokutta, Sebastian
3
2017
Lower bounds in the oracle complexity of nonsmooth convex optimization via information theory. Zbl 1370.94383
Braun, Gábor; Guzmán, Cristóbal; Pokutta, Sebastian
3
2017
Average case polyhedral complexity of the maximum stable set problem. Zbl 1350.05152
Braun, Gábor; Fiorini, Samuel; Pokutta, Sebastian
3
2016
Solving MIPs via scaling-based augmentation. Zbl 06920195
Le Bodic, Pierre; Pavelka, Jeffrey W.; Pfetsch, Marc E.; Pokutta, Sebastian
2
2018
Polyhedral approximation of ellipsoidal uncertainty sets via extended formulations: a computational case study. Zbl 1427.90272
Bärmann, Andreas; Heidt, Andreas; Martin, Alexander; Pokutta, Sebastian; Thurner, Christoph
2
2016
The matching problem has no small symmetric SDP. Zbl 1423.90209
Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
2
2016
The matching problem has no fully polynomial size linear programming relaxation schemes. Zbl 1359.68300
Braun, Gábor; Pokutta, Sebastian
2
2015
Design and verify: a new scheme for generating cutting-planes. Zbl 1300.90019
Dey, Santanu S.; Pokutta, Sebastian
2
2014
An algebraic approach to symmetric extended formulations. Zbl 1370.90292
Braun, Gábor; Pokutta, Sebastian
2
2012
Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank. Zbl 1235.90097
Pokutta, Sebastian; Schulz, Andreas S.
2
2011
On the membership problem for the \({0, 1/2}\)-closure. Zbl 1235.90094
Letchford, Adam N.; Pokutta, Sebastian; Schulz, Andreas S.
2
2011
Design and verify: A new scheme for generating cutting-planes. Zbl 1339.90239
Dey, Santanu S.; Pokutta, Sebastian
2
2011
No small linear program approximates vertex cover within a factor \(2 -\varepsilon\). Zbl 1435.68110
Bazzi, Abbas; Fiorini, Samuel; Pokutta, Sebastian; Svensson, Ola
1
2019
Affine reductions for LPs and SDPs. Zbl 1410.90147
Braun, Gábor; Pokutta, Sebastian; Zink, Daniel
1
2019
The matching problem has no small symmetric SDP. Zbl 1373.90094
Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
1
2017
A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set. Zbl 1408.90325
Braun, Gábor; Pokutta, Sebastian
1
2014
Symmetry-exploiting cuts for a class of mixed-\(0/1\) second-order cone programs. Zbl 1308.90109
Drewes, Sarah; Pokutta, Sebastian
1
2014
Absolutely rigid fields and Shelah’s absolutely rigid trees. Zbl 1266.13008
Göbel, Rüdiger; Pokutta, Sebastian
1
2012
Lazifying conditional gradient algorithms. Zbl 07064051
Braun, Gábor; Pokutta, Sebastian; Zink, Daniel
4
2019
No small linear program approximates vertex cover within a factor \(2 -\varepsilon\). Zbl 1435.68110
Bazzi, Abbas; Fiorini, Samuel; Pokutta, Sebastian; Svensson, Ola
1
2019
Affine reductions for LPs and SDPs. Zbl 1410.90147
Braun, Gábor; Pokutta, Sebastian; Zink, Daniel
1
2019
Aggregation-based cutting-planes for packing and covering integer programs. Zbl 1405.90080
Bodur, Merve; Del Pia, Alberto; Dey, Santanu S.; Molinaro, Marco; Pokutta, Sebastian
3
2018
Solving MIPs via scaling-based augmentation. Zbl 06920195
Le Bodic, Pierre; Pavelka, Jeffrey W.; Pfetsch, Marc E.; Pokutta, Sebastian
2
2018
Information-theoretic approximations of the nonnegative rank. Zbl 1381.94044
Braun, Gábor; Jain, Rahul; Lee, Troy; Pokutta, Sebastian
6
2017
Approximation and online algorithms for multidimensional bin packing: a survey. Zbl 1398.68007
Christensen, Henrik I.; Khan, Arindam; Pokutta, Sebastian; Tetali, Prasad
5
2017
Hierarchical clustering via spreading metrics. Zbl 1441.62173
Roy, Aurko; Pokutta, Sebastian
3
2017
Lower bounds in the oracle complexity of nonsmooth convex optimization via information theory. Zbl 1370.94383
Braun, Gábor; Guzmán, Cristóbal; Pokutta, Sebastian
3
2017
The matching problem has no small symmetric SDP. Zbl 1373.90094
Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
1
2017
Common information and unique disjointness. Zbl 1353.68072
Braun, Gábor; Pokutta, Sebastian
13
2016
A polyhedral characterization of border bases. Zbl 1332.13021
Braun, Gábor; Pokutta, Sebastian
6
2016
Strong reductions for extended formulations. Zbl 1419.90062
Braun, Gábor; Pokutta, Sebastian; Roy, Aurko
4
2016
Average case polyhedral complexity of the maximum stable set problem. Zbl 1350.05152
Braun, Gábor; Fiorini, Samuel; Pokutta, Sebastian
3
2016
Polyhedral approximation of ellipsoidal uncertainty sets via extended formulations: a computational case study. Zbl 1427.90272
Bärmann, Andreas; Heidt, Andreas; Martin, Alexander; Pokutta, Sebastian; Thurner, Christoph
2
2016
The matching problem has no small symmetric SDP. Zbl 1423.90209
Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
2
2016
Exponential lower bounds for polytopes in combinatorial optimization. Zbl 1333.90107
Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald
33
2015
Approximation limits of linear programs (beyond hierarchies). Zbl 1343.68308
Braun, Gábor; Fiorini, Samuel; Pokutta, Sebastian; Steurer, David
29
2015
The matching polytope does not admit fully-polynomial size relaxation schemes. Zbl 1372.68251
Braun, Gábor; Pokutta, Sebastian
9
2015
Inapproximability of combinatorial problems via small LPs and SDPs. Zbl 1321.90098
Braun, Gábor; Pokutta, Sebastian; Zink, Daniel
9
2015
On the existence of 0/1 polytopes with high semidefinite extension complexity. Zbl 1325.90066
Briët, Jop; Dadush, Daniel; Pokutta, Sebastian
5
2015
The matching problem has no fully polynomial size linear programming relaxation schemes. Zbl 1359.68300
Braun, Gábor; Pokutta, Sebastian
2
2015
Strict linear prices in non-convex European day-ahead electricity markets. Zbl 1282.90110
Martin, Alexander; Müller, Johannes C.; Pokutta, Sebastian
7
2014
Average case polyhedral complexity of the maximum stable set problem. Zbl 1359.68118
Braun, Gábor; Fiorini, Samuel; Pokutta, Sebastian
4
2014
Design and verify: a new scheme for generating cutting-planes. Zbl 1300.90019
Dey, Santanu S.; Pokutta, Sebastian
2
2014
A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set. Zbl 1408.90325
Braun, Gábor; Pokutta, Sebastian
1
2014
Symmetry-exploiting cuts for a class of mixed-\(0/1\) second-order cone programs. Zbl 1308.90109
Drewes, Sarah; Pokutta, Sebastian
1
2014
A note on the extension complexity of the knapsack polytope. Zbl 1286.90168
Pokutta, Sebastian; Van Vyve, Mathieu
18
2013
On the existence of 0/1 polytopes with high semidefinite extension complexity. Zbl 1395.90241
Briët, Jop; Dadush, Daniel; Pokutta, Sebastian
6
2013
Linear vs. semidefinite extended formulations, exponential separation and strong lower bounds. Zbl 1286.90125
Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald
66
2012
An algebraic approach to symmetric extended formulations. Zbl 1370.90292
Braun, Gábor; Pokutta, Sebastian
2
2012
Absolutely rigid fields and Shelah’s absolutely rigid trees. Zbl 1266.13008
Göbel, Rüdiger; Pokutta, Sebastian
1
2012
Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube. Zbl 1219.90106
Pokutta, Sebastian; Stauffer, Gautier
7
2011
Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank. Zbl 1235.90097
Pokutta, Sebastian; Schulz, Andreas S.
2
2011
On the membership problem for the \({0, 1/2}\)-closure. Zbl 1235.90094
Letchford, Adam N.; Pokutta, Sebastian; Schulz, Andreas S.
2
2011
Design and verify: A new scheme for generating cutting-planes. Zbl 1339.90239
Dey, Santanu S.; Pokutta, Sebastian
2
2011
On the rank of cutting-plane proof systems. Zbl 1284.03260
Pokutta, Sebastian; Schulz, Andreas S.
9
2010
Cutting-planes for weakly-coupled \(0/1\) second order cone programs. Zbl 1237.90160
Drewes, Sarah; Pokutta, Sebastian
5
2010
Approximate computation of zero-dimensional polynomial ideals. Zbl 1176.13003
Heldt, Daniel; Kreuzer, Martin; Pokutta, Sebastian; Poulisse, Hennie
17
2009
Absolute graphs with prescribed endomorphism monoid. Zbl 1143.05040
Droste, Manfred; Göbel, Rüdiger; Pokutta, Sebastian
4
2008
all top 5

Cited by 278 Authors

25 Pokutta, Sebastian
13 Braun, Gábor
10 Tiwary, Hans Raj
8 Dey, Santanu S.
8 Gouveia, Joao
7 Fiorini, Samuel
7 Shitov, Yaroslav Nikolaevich
6 Kaibel, Volker
6 Robinson, Richard Z.
6 Thomas, Rekha R.
5 Faenza, Yuri
5 Parrilo, Pablo A.
5 Weltge, Stefan
4 Avis, David M.
4 Cornuéjols, Gérard P.
4 Fassino, Claudia
4 Fawzi, Hamza
4 Göbel, Rüdiger
4 Kreuzer, Martin
4 Maksimenko, Aleksandr Nikolaevich
3 Bodur, Merve
3 Conforti, Michele
3 de Wolf, Ronald Michiel
3 Del Pia, Alberto
3 Gillis, Nicolas
3 Glineur, François
3 Grappe, Roland
3 Jain, Rahul
3 Kılınç Karzan, Fatma
3 Lagoutte, Aurélie
3 Laurent, Monique
3 Lee, Troy
3 Mastrolilli, Monaldo
3 Molinaro, Marco
3 Pfetsch, Marc E.
3 Roy, Aurko
3 Tunçel, Levent
3 Van Vyve, Mathieu
3 Vandaele, Arnaud
3 Walter, Matthias
3 Wei, Zhaohui
3 Zink, Daniel
2 Au, Yu-Hin
2 Barbato, Michele
2 Batselier, Kim
2 Bousquet, Nicolas
2 Briskorn, Dirk
2 Buchanan, Austin
2 Di Summa, Marco
2 Gally, Tristan M.
2 Hashemi, Amir
2 Herden, Daniel
2 Hojny, Christopher
2 Hrubeš, Pavel
2 Jansen, Klaus
2 Jörnsten, Kurt O.
2 Kijima, Shuji
2 Kurpisz, Adam
2 Lacroix, Mathieu
2 Lancia, Giuseppe G.
2 Lee, Dabeen
2 Leppänen, Samuli
2 Letchford, Adam N.
2 Madani, Mehdi
2 Mahajan, Meena
2 Martin, Alexander
2 Nishiyama, Hiroshi
2 Pourkhajouei, Samira
2 Sanyal, Raman
2 Sauer, Tomas
2 Saurabh, Nitin
2 Serafini, Paolo
2 Shelah, Saharon
2 Theis, Dirk Oliver
2 Torrente, Maria-Laura
2 Wolfler Calvo, Roberto
2 Wong, Ngai-Ying
2 Yamashita, Masafumi
2 Yamauchi, Yukiko
2 Yıldız, Sercan
1 Abbas Khan, S.
1 Abbott, John A.
1 Aboulker, Pierre
1 Ahmed, Shabbir
1 Ananth, Prabhanjan Vijendra
1 Angulo, Gustavo
1 Aprile, Manuel
1 Averkov, Gennadiy
1 Balas, Egon
1 Bärmann, Andreas
1 Bazzi, Abbas
1 Berndt, Sebastian
1 Bertsimas, Dimitris John
1 Bhardwaj, Avinash
1 Bienstock, Daniel
1 Blado, Daniel
1 Bödi, Richard
1 Borges-Quintana, Mijail
1 Borges Trenard, Miguel Ángel
1 Braverman, Mark
...and 178 more Authors
all top 5

Cited in 72 Serials

35 Mathematical Programming. Series A. Series B
15 Operations Research Letters
12 SIAM Journal on Optimization
5 SIAM Journal on Discrete Mathematics
4 Mathematics of Operations Research
4 Discrete & Computational Geometry
4 Computational Optimization and Applications
3 Discrete Applied Mathematics
3 Discrete Mathematics
3 SIAM Journal on Computing
3 Theoretical Computer Science
3 Annals of Operations Research
3 European Journal of Operational Research
3 Computational Complexity
3 Theory of Computing Systems
3 Discrete Optimization
2 Communications in Mathematical Physics
2 Information Processing Letters
2 Journal of Mathematical Physics
2 Journal of Combinatorial Theory. Series A
2 Journal of Computational and Applied Mathematics
2 Journal of Pure and Applied Algebra
2 European Journal of Combinatorics
2 Journal of Symbolic Computation
2 Algorithmica
2 Linear Algebra and its Applications
2 SIAM Review
2 Journal of Mathematical Sciences (New York)
2 Journal of Difference Equations and Applications
2 Optimization and Engineering
2 Journal of Machine Learning Research (JMLR)
2 4OR
2 Mathematics in Computer Science
1 Linear and Multilinear Algebra
1 Reports on Mathematical Physics
1 Zhurnal Vychislitel’noĭ Matematiki i Matematicheskoĭ Fiziki
1 Mathematics of Computation
1 Beiträge zur Algebra und Geometrie
1 Advances in Mathematics
1 Automatica
1 BIT
1 Collectanea Mathematica
1 Journal of Optimization Theory and Applications
1 Networks
1 Numerische Mathematik
1 Proceedings of the American Mathematical Society
1 Semigroup Forum
1 Applied Numerical Mathematics
1 Graphs and Combinatorics
1 Computers & Operations Research
1 Journal of Global Optimization
1 Numerical Algorithms
1 Computational Mathematics and Mathematical Physics
1 Combinatorics, Probability and Computing
1 Statistical Papers
1 Nonlinear Dynamics
1 Optimization Methods & Software
1 Mathematical Methods of Operations Research
1 Journal of Combinatorial Optimization
1 Journal of the ACM
1 Discrete Mathematics and Theoretical Computer Science. DMTCS
1 RAIRO. Operations Research
1 Foundations of Computational Mathematics
1 Journal of Systems Science and Complexity
1 OR Spectrum
1 Journal of Algebra and its Applications
1 Computational Management Science
1 Journal of Statistical Mechanics: Theory and Experiment
1 Sibirskie Èlektronnye Matematicheskie Izvestiya
1 Optimization Letters
1 Mathematical Programming Computation
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ

Citations by Year