@article{BraunBrownCohenHuqetal.2017, author = {Braun, G{\´a}bor and Brown-Cohen, Jonah and Huq, Arefin and Pokutta, Sebastian and Raghavendra, Prasad and Weitz, Benjamin and Zink, Daniel}, title = {The matching problem has no small symmetric SDP}, volume = {165}, journal = {Mathematical Programming A}, number = {2}, arxiv = {http://arxiv.org/abs/1504.00703}, pages = {643 -- 662}, year = {2017}, language = {en} } @article{BraunRoyPokutta2018, author = {Braun, G{\´a}bor and Roy, Aurko and Pokutta, Sebastian}, title = {Stronger Reductions for Extended Formulations}, journal = {to appear in Mathematical Programming B}, arxiv = {http://arxiv.org/abs/1512.04932}, year = {2018}, language = {en} } @article{BraunPokuttaZink2019, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Affine Reductions for LPs and SDPs}, volume = {173}, journal = {Mathematical Programming A}, number = {1}, arxiv = {http://arxiv.org/abs/1410.8816}, pages = {281 -- 312}, year = {2019}, language = {en} } @article{BraunPokuttaZink2019, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Lazifying Conditional Gradient Algorithms}, volume = {20}, journal = {Journal of Machine Learning Research (JMLR)}, number = {71}, arxiv = {http://arxiv.org/abs/1610.05120}, pages = {1 -- 42}, year = {2019}, language = {en} } @article{BraunPokutta2016, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Common information and unique disjointness}, volume = {76}, journal = {Algorithmica}, number = {3}, pages = {597 -- 629}, year = {2016}, language = {en} } @article{BraunGuzmanPokutta2017, author = {Braun, G{\´a}bor and Guzm{\´a}n, C. and Pokutta, Sebastian}, title = {Unifying Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization}, volume = {63}, journal = {IEEE Transactions of Information Theory}, number = {7}, arxiv = {http://arxiv.org/abs/1407.5144}, pages = {4709 -- 4724}, year = {2017}, language = {en} } @article{BraunJainLeeetal.2017, author = {Braun, G{\´a}bor and Jain, R. and Lee, T. and Pokutta, Sebastian}, title = {Information-theoretic approximations of the nonnegative rank}, volume = {26}, journal = {Computational Complexity}, number = {1}, pages = {147 -- 197}, year = {2017}, language = {en} } @inproceedings{BraunPokuttaZink2017, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Lazifying Conditional Gradient Algorithms}, booktitle = {Proceedings of the International Conference on Machine Learning (ICML)}, arxiv = {http://arxiv.org/abs/1610.05120}, year = {2017}, language = {en} } @inproceedings{BraunPokuttaTuetal.2019, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Tu, Dan and Wright, Stephen}, title = {Blended Conditional Gradients: the unconditioning of conditional gradients}, booktitle = {Proceedings of ICML}, arxiv = {http://arxiv.org/abs/1805.07311}, year = {2019}, language = {en} } @article{BraunPokutta2012, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Rigid abelian groups and the probabilistic method}, volume = {576}, journal = {Contemporary Mathematics}, arxiv = {http://arxiv.org/abs/1107.2325}, pages = {17 -- 30}, year = {2012}, language = {en} } @article{BraunPokutta2014, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {A short proof for the polyhedrality of the Chv{\´a}tal-Gomory closure of a compact convex set}, volume = {42}, journal = {Operations Research Letters}, arxiv = {http://arxiv.org/abs/1207.4884}, pages = {307 -- 310}, year = {2014}, language = {en} } @article{BraunPokutta2011, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Random half-integral polytopes}, volume = {39}, journal = {Operations Research Letters}, number = {3}, pages = {204 -- 207}, year = {2011}, language = {en} } @article{BraunFioriniPokuttaetal.2015, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian and Steurer, D.}, title = {Approximation Limits of Linear Programs (Beyond Hierarchies)}, volume = {40}, journal = {Mathematics of Operations Research}, number = {3}, arxiv = {http://arxiv.org/abs/1204.0957}, pages = {179 -- 199}, year = {2015}, language = {en} } @article{BraunPokutta2015, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {The matching polytope does not admit fully-polynomial size relaxation schemes}, volume = {61}, journal = {IEEE Transactions on Information Theory}, number = {10}, arxiv = {http://arxiv.org/abs/1403.6710}, pages = {1 -- 11}, year = {2015}, language = {en} } @article{BraunPokuttaXie2015, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Xie, Y.}, title = {Info-Greedy Sequential Adaptive Compressed Sensing}, volume = {9}, journal = {IEEE Journal of Selected Topics in Signal Processing}, number = {4}, arxiv = {http://arxiv.org/abs/1407.0731}, pages = {601 -- 611}, year = {2015}, language = {en} } @article{BraunFioriniPokutta2016, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian}, title = {Average case polyhedral complexity of the maximum stable set problem}, volume = {160}, journal = {Mathematical Programming A}, number = {1}, arxiv = {http://arxiv.org/abs/1311.4001}, pages = {407 -- 431}, year = {2016}, language = {en} } @article{BraunPokutta2016, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {A polyhedral characterization of Border Bases}, volume = {30}, journal = {SIAM Journal on Discrete Mathematics}, number = {1}, arxiv = {http://arxiv.org/abs/0912.1502}, pages = {239 -- 265}, year = {2016}, language = {en} } @inproceedings{BraunFioriniPokuttaetal.2012, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian and Steurer, D.}, title = {Approximation Limits of Linear Programs (Beyond Hierarchies)}, booktitle = {Proceedings of FOCS}, arxiv = {http://arxiv.org/abs/1204.0957}, year = {2012}, language = {en} } @inproceedings{BraunPokutta2012, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {An algebraic view on symmetric extended formulations}, volume = {7422}, booktitle = {Proceedings of ISCO, Lecture Notes in Computer Science}, number = {141--152}, arxiv = {http://arxiv.org/abs/1206.6318}, year = {2012}, language = {en} } @inproceedings{BraunPokutta2013, author = {Braun, Gabor and Pokutta, Sebastian}, title = {Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium}, booktitle = {Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium}, pages = {688 -- 697}, year = {2013}, language = {en} } @inproceedings{BraunFioriniPokutta2014, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian}, title = {Average case polyhedral complexity of the maximum stable set problem}, booktitle = {Proceedings of RANDOM}, arxiv = {http://arxiv.org/abs/1311.4001}, year = {2014}, language = {en} } @inproceedings{BraunPokuttaXie2014, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Xie, Y.}, title = {Info-Greedy Sequential Adaptive Compressed Sensing}, booktitle = {Proceedings of 52nd Annual Allerton Conference on Communication, Control, and Computing}, arxiv = {http://arxiv.org/abs/1407.0731}, year = {2014}, language = {en} } @inproceedings{BraunPokutta2010, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Rank of random half-integral polytopes}, volume = {36}, booktitle = {Electronic Notes in Discrete Mathematics}, pages = {415 -- 422}, year = {2010}, language = {en} } @inproceedings{BraunPokutta2015, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {The matching polytope does not admit fully-polynomial size relaxation schemes}, booktitle = {Proceeedings of SODA}, arxiv = {http://arxiv.org/abs/1403.6710}, year = {2015}, language = {en} } @inproceedings{BraunPokuttaZink2015, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Inapproximability of combinatorial problems via small LPs and SDPs}, booktitle = {Proceeedings of STOC}, arxiv = {http://arxiv.org/abs/1410.8816}, year = {2015}, language = {en} } @inproceedings{BraunRoyPokutta2016, author = {Braun, G{\´a}bor and Roy, Aurko and Pokutta, Sebastian}, title = {Stronger Reductions for Extended Formulations}, booktitle = {Proceedings of IPCO}, arxiv = {http://arxiv.org/abs/1512.04932}, year = {2016}, language = {en} } @inproceedings{BraunBrownCohenHuqetal.2016, author = {Braun, G{\´a}bor and Brown-Cohen, Jonah and Huq, Arefin and Pokutta, Sebastian and Raghavendra, Prasad and Weitz, Benjamin and Zink, Daniel}, title = {The matching problem has no small symmetric SDP}, booktitle = {Proceddings of SODA 2016}, arxiv = {http://arxiv.org/abs/1504.00703}, year = {2016}, language = {en} } @article{BraunGuzmanPokutta2024, author = {Braun, G{\´a}bor and Guzm{\´a}n, Crist{\´o}bal and Pokutta, Sebastian}, title = {Corrections to "Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory"}, volume = {70}, journal = {IEEE Transactions on Information Theory}, number = {7}, doi = {10.1109/TIT.2024.3357200}, pages = {5408 -- 5409}, year = {2024}, abstract = {This note closes a gap in the proof of Theorem VI.3 from the article "Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory" (2017).}, language = {en} }