TY - JOUR A1 - Braun, Gábor A1 - Brown-Cohen, Jonah A1 - Huq, Arefin A1 - Pokutta, Sebastian A1 - Raghavendra, Prasad A1 - Weitz, Benjamin A1 - Zink, Daniel T1 - The matching problem has no small symmetric SDP JF - Mathematical Programming A Y1 - 2017 N1 - Additional Note: DOI 10.1007/s10107-016-1098-z N1 - URL of the PDF: http://dx.doi.org/10.1007/s10107-016-1098-z VL - 165 IS - 2 SP - 643 EP - 662 ER - TY - JOUR A1 - Braun, Gábor A1 - Roy, Aurko A1 - Pokutta, Sebastian T1 - Stronger Reductions for Extended Formulations JF - to appear in Mathematical Programming B Y1 - 2018 N1 - Additional Note: available at \url{http://arxiv.org/abs/1512.04932} ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Zink, Daniel T1 - Affine Reductions for LPs and SDPs JF - Mathematical Programming A Y1 - 2019 N1 - URL of the PDF: http://rdcu.be/EPf9 VL - 173 IS - 1 SP - 281 EP - 312 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Zink, Daniel T1 - Lazifying Conditional Gradient Algorithms JF - Journal of Machine Learning Research (JMLR) Y1 - 2019 N1 - URL of the PDF: http://jmlr.org/papers/v20/18-114.html N1 - URL of the Slides: https://app.box.com/s/zsp0hixjz2ha23u1vuyosijjkjdh8kj7 VL - 20 IS - 71 SP - 1 EP - 42 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - Common information and unique disjointness JF - Algorithmica Y1 - 2016 UR - http://eccc.hpi-web.de/report/2013/056 N1 - URL of the PDF: https://rdcu.be/6b9u VL - 76 IS - 3 SP - 597 EP - 629 ER - TY - JOUR A1 - Braun, Gábor A1 - Guzmán, C. A1 - Pokutta, Sebastian T1 - Unifying Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization JF - IEEE Transactions of Information Theory Y1 - 2017 N1 - Additional Note: doi:10.1109/TIT.2017.2701343 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7919238 N1 - URL of the PDF: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7919238 VL - 63 IS - 7 SP - 4709 EP - 4724 ER - TY - JOUR A1 - Braun, Gábor A1 - Jain, R. A1 - Lee, T. A1 - Pokutta, Sebastian T1 - Information-theoretic approximations of the nonnegative rank JF - Computational Complexity Y1 - 2017 UR - http://eccc.hpi-web.de/report/2013/158 VL - 26 IS - 1 SP - 147 EP - 197 ER - TY - CHAP A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Zink, Daniel T1 - Lazifying Conditional Gradient Algorithms T2 - Proceedings of the International Conference on Machine Learning (ICML) Y1 - 2017 N1 - URL of the PDF: http://proceedings.mlr.press/v70/braun17a N1 - URL of the Poster: https://app.box.com/s/lysscdg17ytpz7mqr0tu2djffyqvkl6a N1 - URL of the Slides: https://app.box.com/s/zsp0hixjz2ha23u1vuyosijjkjdh8kj7 ER - TY - CHAP A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Tu, Dan A1 - Wright, Stephen T1 - Blended Conditional Gradients: the unconditioning of conditional gradients T2 - Proceedings of ICML Y1 - 2019 N1 - Additional Note: https://arxiv.org/abs/1805.07311 N1 - URL of the Code: https://github.com/pokutta/bcg N1 - URL of the PDF: http://proceedings.mlr.press/v97/braun19a/braun19a.pdf N1 - URL of the Poster: https://app.box.com/s/nmmm671jd72i397nysa8emfnzh1hn6hf N1 - URL of the Slides: https://app.box.com/s/xbx3z7ws6dxvl3rzgj4jp6forigycooe N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2019/02/18/bcg-abstract.html ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - Rigid abelian groups and the probabilistic method JF - Contemporary Mathematics Y1 - 2012 N1 - Additional Note: doi:/10.1090/conm/576 N1 - URL of the PDF: http://dx.doi.org/10.1090/conm/576 VL - 576 SP - 17 EP - 30 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set JF - Operations Research Letters Y1 - 2014 N1 - Additional Note: 10.1016/j.orl.2014.05.004 VL - 42 SP - 307 EP - 310 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - Random half-integral polytopes JF - Operations Research Letters Y1 - 2011 UR - http://www.optimization-online.org/DB_HTML/2010/11/2813.html N1 - Additional Note: doi:10.1016/j.orl.2011.03.003 VL - 39 IS - 3 SP - 204 EP - 207 ER - TY - JOUR A1 - Braun, Gábor A1 - Fiorini, Samuel A1 - Pokutta, Sebastian A1 - Steurer, D. T1 - Approximation Limits of Linear Programs (Beyond Hierarchies) JF - Mathematics of Operations Research Y1 - 2015 VL - 40 IS - 3 SP - 179 EP - 199 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - The matching polytope does not admit fully-polynomial size relaxation schemes JF - IEEE Transactions on Information Theory Y1 - 2015 N1 - Additional Note: doi:10.1109/TIT.2015.2465864 N1 - URL of the PDF: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7182355 VL - 61 IS - 10 SP - 1 EP - 11 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Xie, Y. T1 - Info-Greedy Sequential Adaptive Compressed Sensing JF - IEEE Journal of Selected Topics in Signal Processing Y1 - 2015 VL - 9 IS - 4 SP - 601 EP - 611 ER - TY - JOUR A1 - Braun, Gábor A1 - Fiorini, Samuel A1 - Pokutta, Sebastian T1 - Average case polyhedral complexity of the maximum stable set problem JF - Mathematical Programming A Y1 - 2016 N1 - Additional Note: http://www.dagstuhl.de/dagpub/978-3-939897-74-3 N1 - URL of the PDF: https://rdcu.be/7uOy VL - 160 IS - 1 SP - 407 EP - 431 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - A polyhedral characterization of Border Bases JF - SIAM Journal on Discrete Mathematics Y1 - 2016 VL - 30 IS - 1 SP - 239 EP - 265 ER - TY - CHAP A1 - Braun, Gábor A1 - Fiorini, Samuel A1 - Pokutta, Sebastian A1 - Steurer, D. T1 - Approximation Limits of Linear Programs (Beyond Hierarchies) T2 - Proceedings of FOCS Y1 - 2012 ER - TY - CHAP A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - An algebraic view on symmetric extended formulations T2 - Proceedings of ISCO, Lecture Notes in Computer Science Y1 - 2012 VL - 7422 IS - 141--152 ER - TY - CHAP A1 - Braun, Gabor A1 - Pokutta, Sebastian T1 - Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium T2 - Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium Y1 - 2013 UR - http://eccc.hpi-web.de/report/2013/056 SP - 688 EP - 697 ER - TY - CHAP A1 - Braun, Gábor A1 - Fiorini, Samuel A1 - Pokutta, Sebastian T1 - Average case polyhedral complexity of the maximum stable set problem T2 - Proceedings of RANDOM Y1 - 2014 N1 - Additional Note: http://www.dagstuhl.de/dagpub/978-3-939897-74-3 N1 - URL of the PDF: http://www.dagstuhl.de/dagpub/978-3-939897-74-3 ER - TY - CHAP A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Xie, Y. T1 - Info-Greedy Sequential Adaptive Compressed Sensing T2 - Proceedings of 52nd Annual Allerton Conference on Communication, Control, and Computing Y1 - 2014 ER -