@article{BazziFioriniPokuttaetal.2017, author = {Bazzi, Abbas and Fiorini, Samuel and Pokutta, Sebastian and Svensson, Ola}, title = {Small linear programs cannot approximate Vertex Cover within a factor of 2 - epsilon}, journal = {to appear in Mathematics of Operations Research}, arxiv = {http://arxiv.org/abs/1503.00753}, year = {2017}, 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{FioriniMassarPokuttaetal.2015, author = {Fiorini, Samuel and Massar, S. and Pokutta, Sebastian and Tiwary, H.R. and de Wolf, R.}, title = {Exponential Lower Bounds for Polytopes in Combinatorial Optimization}, volume = {62}, journal = {Journal of the ACM}, number = {2}, arxiv = {http://arxiv.org/abs/1111.0837}, pages = {1 -- 17}, 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} } @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{FioriniMassarPokuttaetal.2012, author = {Fiorini, Samuel and Massar, S. and Pokutta, Sebastian and Tiwary, H.R. and de Wolf, R.}, title = {Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds}, booktitle = {Proceedings of STOC}, arxiv = {http://arxiv.org/abs/1111.0837}, year = {2012}, 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{BazziFioriniPokuttaetal.2015, author = {Bazzi, Abbas and Fiorini, Samuel and Pokutta, Sebastian and Svensson, Ola}, title = {Small linear programs cannot approximate Vertex Cover within a factor of 2 - epsilon}, booktitle = {Proceedings of FOCS}, arxiv = {http://arxiv.org/abs/1503.00753}, year = {2015}, language = {en} }