Sebastian Pokutta

In preparation / articles pending review.

  1. Robust Submodular Maximization: Offline and Online Algorithms
    N. Anari, N. Haghtalab, S. Naor, S. Pokutta, M. Singh, A. Torrico
    preprint (2017)
    [arXiv]
  2. An information diffusion Fano inequality
    G. Braun, S. Pokutta
    preprint (2015)
    [arXiv]
  3. Sequential information guided sensing
    R. Song, Y. Xie, S. Pokutta
    submitted (2015)
  4. On the Rank of Cutting-Plane Proof Systems
    S. Pokutta, A.S. Schulz
    submitted (2013)
    [pdf/preview] [optimization-online]
  5. A network model for bank lending capacity
    S. Pokutta, C. Schmaltz
    submitted (2011)
    [pdf/preview] [SSRN]
  6. Measuring systemic risk and contagion in financial networks
    S. Pokutta, C. Schmaltz, S. Stiller
    submitted (2011)
    [pdf/preview] [SSRN]
  7. On the connection of the Sherali-Adams closure and border bases
    S. Pokutta, A.S. Schulz
    submitted (2010)
    [pdf/preview] [optimization-online]
  8. Stowage optimization for inland vessels
    S. Pokutta
    submitted (2009) [available upon request]

 

Refereed Conference Proceedings.

  1. Reinforcement Learning under Model Mismatch
    A. Roy, H. Xu, S. Pokutta
    to appear in Proceedings of NIPS (2017)
    [arXiv]
  2. Conditional Accelerated Lazy Stochastic Gradient Descent
    G. Lan, S. Pokutta, Y. Zhou, D. Zink
    Proceedings of ICML (2017)
    [Proceedings][arXiv]
  3. Lazifying Conditional Gradient Algorithms
    G. Braun, S. Pokutta, D. Zink
    Proceedings of ICML (2017)
    [Proceedings][arXiv]
  4. Emulating the Expert: Inverse Optimization through Online Learning
    A. Bärmann, S. Pokutta, O. Schneider
    Proceedings of ICML (2017)
    [Proceedings]
  5. Modulation Recognition Using Side Information and Hybrid Learning
    K. Arumugam, I. Kadampot, M. Tahmasbi, S. Shah, M. Bloch, S. Pokutta
    Proceedings of IEEE DySPAN (2017)
  6. Hierarchical Clustering via Spreading Metrics
    A. Roy, S. Pokutta
    Proceedings of NIPS (2016)
    [Proceedings] [arXiv]
    Accepted for full oral presentation (top 1.8% of submissions)
  7. Stronger Reductions for Extended Formulations
    G. Braun, S. Pokutta, A. Roy
    Proceedings of IPCO (2016)
    [arXiv]
  8. The matching problem has no small symmetric SDP
    G. Braun, J. Brown-Cohen, A. Huq, S. Pokutta, P. Raghavendra, A. Roy, B. Weitz, D. Zink
    Proceedings of SODA (2016)
    [arXiv]
  9. Information Theory and Polyhedral Combinatorics
    S. Pokutta
    Proceedings of 53rd Annual Allerton Conference on Communication, Control, and Computing (2015).
    [Proceedings]
  10. Small linear programs cannot approximate Vertex Cover within a factor of 2 - epsilon
    A. Bazzi, S. Fiorini, S. Pokutta, O. Svensson
    Proceedings of FOCS (2015)
    [arXiv]
  11. Supervised Online Subspace Tracking
    Y. Xie, Q. Li, S. Pokutta
    Proceedings of Asilomar Conference on Signals, Systems, and Computers (2015).
  12. Sequential Sensing with Model Mismatch
    R. Song, Y. Xie, S. Pokutta
    Proceedings of ISIT (2015)
    [arXiv]
  13. Inapproximability of combinatorial problems via small LPs and SDPs
    G. Braun, S. Pokutta, D. Zink
    Proceedings of STOC (2015)
    [arXiv]
  14. The matching polytope does not admit fully-polynomial size relaxation schemes
    G. Braun, S. Pokutta
    Proceedings of SODA (2015)
    [arXiv]
  15. Info-Greedy sequential adaptive compressed sensing
    G. Braun, S. Pokutta, Y. Xie
    Proceedings of 52nd Annual Allerton Conference on Communication, Control, and Computing (2014) [arXiv]
  16. Average case polyhedral complexity of the maximum stable set problem
    G. Braun, S. Fiorini, S. Pokutta
    Proceedings of RANDOM (2014)
    [arXiv] [Proceedings]
  17. Common information and unique disjointness
    G. Braun, S. Pokutta
    Proceedings of FOCS (2013)
    [pdf/preview] [ECCC]
  18. On the existence of 0/1 polytopes with high semidefinite extension complexity
    J. Briët, D. Dadush, S. Pokutta
    Proceedings of ESA (2013)
    [pdf/preview] [arXiv]
  19. How to make regulators and shareholders happy under Basel III
    C. Schmaltz, S. Pokutta, T. Heidorn, S. Andrae
    Proceedings of the 26th Australasian Finance and Banking Conference (2013)
    [SSRN]
  20. Approximation Limits of Linear Programs (Beyond Hierarchies)
    G. Braun, S. Fiorini, S. Pokutta, D. Steurer
    Proceedings of FOCS (2012)
    [pdf/preview] [arXiv]
  21. An algebraic view on symmetric extended formulations
    G. Braun, S. Pokutta
    Proceedings of ISCO (2012)
    [pdf/preview]
  22. Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds
    S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, R. de Wolf
    Proceedings of STOC (2012)
    [pdf/preview] [arxiv]
    STOC Best Paper Award
  23. Optimal mixed-mode runway scheduling
    H. Helmke, O. Gluchshenko, A. Martin, A. Peter, S. Pokutta, U. Siebert
    Proceedings of 30th Digital Avionics Systems Conference (DASC) (2011)
    [pdf/preview]
  24. A network model for bank lending capacity
    S. Pokutta, C. Schmaltz
    Proceedings of Systemic Risk, Basel III, Financial Stability and Regulation (2011)
    [pdf/preview] [SSRN]
  25. Optimal Planning under Basel III Regulations
    S. Pokutta, C. Schmaltz
    Proceedings of the 24th Australasian Finance and Banking Conference (2011)
    [pdf/preview] [SSRN]
  26. Design and verify:  a new scheme for generating cutting-planes
    S.S. Dey, S. Pokutta
    Proceedings of IPCO, Lecture Notes in Computer Science 6655 (2011), 143--155
    [doi:10.1007/978-3-642-20807-2_12] [pdf/preview]
  27. Geometric mean maximization in the presence of discrete decisions
    S. Drewes, S. Pokutta
    Proceedings of the 23rd Australasian Finance and Banking Conference (2010).
  28. On clearing coupled day-ahead electricity markets
    A. Martin, J. Müller, S. Pokutta
    Proceedings of the 23rd Australasian Finance and Banking Conference (2010)
    [pdf/preview] [SSRN]
    Energy Finance Best Paper Award
  29. On the rank of generic cutting-plane proof systems
    S. Pokutta, A.S. Schulz
    Proceedings of IPCO 2010, Lecture Notes in Computer Science 6080 (2010), 450--463
    [doi:10.1007/978-3-642-13036-6_34] [pdf/preview] [article]
  30. Cutting-planes for weakly-coupled 0/1 second order cone programs
    S. Drewes, S. Pokutta
    Electronic Notes in Discrete Mathematics 36 (2010), 735--742
    [doi:10.1016/j.endm.2010.05.093] [pdf/preview]
  31. Rank of random half-integral polytopes
    G. Braun, S. Pokutta
    Electronic Notes in Discrete Mathematics 36 (2010), 415--422
    [doi:10.1016/j.endm.2010.05.053] [pdf/preview]
  32. Optimal degree of centralization of liquidity management
    S. Pokutta, C. Schmaltz
    Proceedings of the 22nd Australasian Finance and Banking Conference (2009)
    [pdf/preview] [SSRN]

 

Refereed Journals.

  1. Aggregation-based cutting-planes for packing and covering integer programs
    M. Bodur, A. Del Pia, S.S. Dey, M. Molinaro, S. Pokutta
    to appear in Mathematical Programming A (2017)
    [arXiv] [doi:10.1007/s10107-017-1192-x]
  2. Small linear programs cannot approximate Vertex Cover within a factor of 2 - epsilon
    A. Bazzi, S. Fiorini, S. Pokutta, O. Svensson
    to appear in Mathematics of Operations Research (2017)
    [arXiv] (see above for conference version)
  3. Solving MIPs via Scaling-based Augmentation
    P. Le Bodic, J.W. Pavelka, M.E. Pfetsch, S. Pokutta
    to appear in Discrete Optimization (2017)
    [arXiv] [doi:10.1016/j.disopt.2017.08.004]
  4. Detecting Almost Symmetries in Graphs
    B. Knueven, J. Ostrowski, S.Pokutta
    to appear in Mathematical Programming C (2017)
    [optimization-online] [SpringerOnline]
  5. Hierarchical Clustering via Spreading Metrics
    A. Roy, S. Pokutta
    to appear in Journal of Machine Learning Research (2017)
    [arXiv] [journal] (see above for conference version)
  6. Multidimensional Bin Packing and Other Related Problems: A Survey
    H.I. Christensen, A. Khan, S. Pokutta, P. Tetali.
    to appear in Computer Science Review (2017)
  7. Convergence of Capital and Insurance Markets: Pricing Aspects of Index-Linked Catastrophic Loss Instruments
    N. Gatzert, S. Pokutta, N. Vogl
    to appear in Journal of Risk and Insurance (2016)
    [SSRN]
    Best Paper Award at EGRIE Annual Meeting
  8. Pricing and clearing combinatorial markets with singleton and swap orders
    A. Martin, J. Müller, S. Pape, A. Peter, S. Pokutta, T. Winter
    to appear in Mathematical Methods of Operations Research (2016)
    [arXiv]
  9. The matching problem has no small symmetric SDP
    G. Braun, J. Brown-Cohen, A. Huq, S. Pokutta, P. Raghavendra, A. Roy, B. Weitz, D. Zink
    to appear in Mathematical Programming A, 165(2) (2016), 643--662
    [arXiv] [doi:10.1007/s10107-016-1098-z] (see above for conference version)
  10. Unifying Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization
    G. Braun, C. Guzmán, S. Pokutta
    IEEE Transactions on Information Theory 63(7) (2017), 4709--4724
    [arXiv] [IEEE Xplore]
  11. Common information and unique disjointness
    G. Braun, S. Pokutta
    Algorithmica 76(3) (2016), 597--629
    [ECCC] [SpringerOnline] (see above for the conference version)
  12. Average case polyhedral complexity of the maximum stable set problem
    G. Braun, S. Fiorini, S. Pokutta
    Mathematical Programming A 160(1) (2016), 407--431
    [arXiv] (see above for the conference version)
  13. A polyhedral characterization of border bases
    G. Braun, S. Pokutta
    SIAM Journal of Discrete Mathematics 30(1) (2016), 239--265
    [arXiv]
  14. Polyhedral Approximation of Ellipsoidal Uncertainty Sets via Extended Formulations - a computational case study
    A. Bärmann, A. Heidt, A. Martin, S. Pokutta, C. Thurner
    Computational Management Science 13(2) (2016), 151--193
    [optimization-online] [SpringerOnline]
  15. Information-theoretic approximations of the nonnegative rank
    G. Braun, R. Jain, T. Lee, S. Pokutta
    to appear in Computational Complexity (2015)
    [ECCC]
  16. Info-Greedy sequential adaptive compressed sensing
    G. Braun, S. Pokutta, Y. Xie
    IEEE Journal of Selected Topics in Signal Processing 9(4) (2015), 601--611
    [arXiv]
  17. The matching polytope does not admit fully-polynomial size relaxation schemes
    G. Braun, S. Pokutta
    IEEE Transactions on Information Theory 61, No. 10 (2015), 1--11
    [doi:10.1109/TIT.2015.2465864] [arXiv] (see above for the conference version)
  18. Exponential Lower Bounds for Polytopes in Combinatorial Optimization
    S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, R. de Wolf
    Journal of the ACM  62, No. 2 (2015), 1--17
    [doi:10.1145/2716307] [arxiv] (see above for conference version)
  19. Approximation Limits of Linear Programs (Beyond Hierarchies)
    G. Braun, S. Fiorini, S. Pokutta, D. Steurer
    Mathematics of Operations Research 40, No. 3 (2015), 756--772
    [pdf/preview] [arXiv] (see above for the conference version)
  20. On the existence of 0/1 polytopes with high semidefinite extension complexity
    J. Briët, D. Dadush, S. Pokutta
    Mathematical Programming B 153, No. 1 (2015), 179--199
    [pdf/preview] [arXiv] (see above for the conference version)
  21. Computing discrete expected utility maximizing portfolios
    S. Drewes, S. Pokutta
    Journal of Investing 23, No. 4 (2014), 121--132
    [SSRN]
  22. A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set
    G. Braun, S. Pokutta
    Operations Research Letters 42 (2014), 307--310
    [pdf/preview] [arXiv]
  23. How to make regulators and shareholders happy under Basel III
    C. Schmaltz, S. Pokutta, T. Heidorn, S. Andrae
    Journal of Banking and Finance 46:C (2014), 311--325
    [doi:/10.1016/j.jbankfin.2014.05.031] [SSRN]
  24. Symmetry-exploiting cuts for a class of mixed-0/1 second order cone programs
    S. Drewes, S. Pokutta
    Discrete Optimization 13 (2014) 23--35
    [pdf/preview] [optimization-online]
  25. Strict linear prices in non-convex European day-ahead electricity markets
    A. Martin, J. Müller, S. Pokutta
    Optimization Methods and Software 29:1 (2014), 189--221
  26. Design and verify: a new scheme for generating cutting-planes
    Mathematical Programming A 145 (2014), 199--222
    [pdf/preview] [optimization-online]
  27. A Note on the Extension Complexity of the Knapsack Polytope
    S. Pokutta, M. Van Vyve
    Operations Research Letters 41 (2013), 347--350
    [pdf/preview] [optimization-online]
  28. Just a perfect day: Developing a happiness optimized day schedule
    C. Kroll, S. Pokutta
    Journal of Economic Psychology 34 (2013) 210--217
    [doi:/10.1016/j.joep.2012.09.015] [ScienceDirect]
  29. Optimal Planning under Basel III Regulations
    S. Pokutta, C. Schmaltz
    Cass-Capco Institute Paper Series on Risk (2012)
    [journal] (see above for the conference version)
  30. Rigid abelian groups and the probabilistic method
    G. Braun, S. Pokutta
    Contemporary Mathematics 576 (2012), 17--30
    [doi:/10.1090/conm/576] [pdf/preview] [arXiv]
  31. Absolutely rigid fields and Shelah's absolutely rigid trees
    R. Göbel, S. Pokutta
    Contemporary Mathematics 576 (2012), 105--128
    [doi:/10.1090/conm/576] [pdf/preview]
  32. Characterization of integer-free 0/1 polytopes with maximal rank
    S. Pokutta, A.S. Schulz
    Operations Research Letters 39(6) (2011), 457--460
    [doi:10.1016/j.orl.2011.09.004] [pdf/preview] [optimization-online]
  33. On the membership problem for the {0,1/2}-closure
    A.N. Letchford, S. Pokutta, A.S. Schulz
    Operations Research Letters 39(5) (2011), 301--304
    [doi:10.1016/j.orl.2011.07.003] [pdf/preview]
  34. Reconstructing biochemical cluster networks
    U.U. Haus, R. Hemmecke, S. Pokutta
    Journal of Mathematical Chemistry 49(10) (2011), 2441--2456
    [doi:10.1007/s10910-011-9892-6] [preview] [arXiv]
  35. Random half-integral polytopes
    G. Braun, S. Pokutta
    Operations Research Letters 39(3) (2011), 204--207
    [doi:10.1016/j.orl.2011.03.003] [pdf/preview] [optimization-online]
  36. Lower bounds for the Chvátal-Gomory rank in the 0/1 cube
    S. Pokutta, G. Stauffer
    Operations Research Letters 39(3) (2011), 200--203
    [doi:10.1016/j.orl.2011.03.001] [pdf/preview] [optimization-online]
  37. Managing liquidity: Optimal degree of centralization
    S. Pokutta, C. Schmaltz
    Journal of Banking and Finance 35 (2011), 627--638
    [doi:10.1016/j.jbankfin.2010.07.001] [pdf/preview]
  38. Approximate Computation of zero-dimensional polynomial ideals
    D. Heldt, M. Kreuzer, S. Pokutta, H. Poulisse
    Journal of Symbolic Computation 44 (2009), 1566--1591
    [doi:10.1016/j.jsc.2008.11.010] [preview] [pdf]
  39. France Telecom Workforce Scheduling Problem: a challenge
    S. Pokutta, G. Stauffer
    RAIRO-Operations Research 43 (2009), 375--386
  40. Construction of dual modules using Martin’s axiom
    R. Göbel, S. Pokutta
    Journal of Algebra 320 (2008), 2388--2404
    [doi:10.1016/j.jalgebra.2008.06.017] [preview] [pdf]
  41. Absolute graphs with prescribed endomorphism monoid
    M. Droste, R. Göbel, S. Pokutta
    Semigroup Forum 76 (2008), 256--267
    [doi:10.1007/s00233-007-9029-1] [preview] [pdf]
  42. The Chase radical and reduced products
    S. Pokutta, L. Strüngmann
    Journal of Pure and Applied Algebra 211 (2007), 532--540
    [doi:10.1016/j.jpaa.2007.02.007] [preview] [pdf]

 

Unpublished Manuscripts.

  1. An efficient high-probability algorithm for Linear Bandits
    G. Braun, S. Pokutta
    Manuscript (2016)
    [arXiv]
  2. An algebraic view on symmetric extended formulations
    G. Braun, S. Pokutta
    Manuscript (2012)
    [pdf/preview] [arXiv] (see above for the conference version)
  3. Lower bounds for Chvátal-Gomory style operators
    S. Pokutta
    Manuscript (2011)
    [pdf/preview] [optimization-online]
  4. The mechanics of the Gomory-Chvátal procedure
    S. Pokutta
    Manuscript (2009)

 

Other.

  1. Toward a Science of Autonomy for Physical Systems: Transportation
    D. Lee, S. Pokutta
    Computing Community Consortium White Paper (2015)
    [pdf]
  2. Algebraische Modellierung mit Methoden der approximativen Computer Algebra und Anwendungen in der Ölindustrie
    D. Heldt, M. Kreuzer, S. Pokutta, H. Poulisse
    OR News, 28 (2006), 15--18
  3. How logistics service providers can make use of the real options concept
    M. Alf, S. Pokutta
    Symposium Mathematik & Logistik, Bad Honnef 2005, Conference Proceedings, (2006)
  4. Fixpunktminimierung bei Binnenschiffen
    S. Pokutta, G. Törner
    OR News, 23 (2005), 13--17
  5. Products over countable domains
    S. Pokutta
    University of Duisburg-Essen, Ph.D. thesis (2005)
    [preview] [pdf]
  6. Generalizations of the Chase radical and direct products
    S. Pokutta
    University of Duisburg-Essen, Thesis, (2003)