@inproceedings{BazziFioriniPokuttaetal., 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}, series = {Proceedings of FOCS}, booktitle = {Proceedings of FOCS}, language = {en} } @article{BraunFioriniPokuttaetal., author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian and Steurer, D.}, title = {Approximation Limits of Linear Programs (Beyond Hierarchies)}, series = {Mathematics of Operations Research}, volume = {40}, journal = {Mathematics of Operations Research}, number = {3}, pages = {179 -- 199}, language = {en} } @inproceedings{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {The matching polytope does not admit fully-polynomial size relaxation schemes}, series = {Proceeedings of SODA}, booktitle = {Proceeedings of SODA}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {The matching polytope does not admit fully-polynomial size relaxation schemes}, series = {IEEE Transactions on Information Theory}, volume = {61}, journal = {IEEE Transactions on Information Theory}, number = {10}, pages = {1 -- 11}, language = {en} } @article{BraunPokuttaXie, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Xie, Y.}, title = {Info-Greedy Sequential Adaptive Compressed Sensing}, series = {IEEE Journal of Selected Topics in Signal Processing}, volume = {9}, journal = {IEEE Journal of Selected Topics in Signal Processing}, number = {4}, pages = {601 -- 611}, language = {en} } @inproceedings{BraunPokuttaZink, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Inapproximability of combinatorial problems via small LPs and SDPs}, series = {Proceeedings of STOC}, booktitle = {Proceeedings of STOC}, language = {en} } @article{BrietDadushPokutta, author = {Bri{\"e}t, Jop and Dadush, Daniel and Pokutta, Sebastian}, title = {On the existence of 0/1 polytopes with high semidefinite extension complexity}, series = {Mathematical Programming B}, volume = {153}, journal = {Mathematical Programming B}, number = {1}, pages = {179 -- 199}, language = {en} } @article{FioriniMassarPokuttaetal., 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}, series = {Journal of the ACM}, volume = {62}, journal = {Journal of the ACM}, number = {2}, pages = {1 -- 17}, language = {en} } @inproceedings{Pokutta, author = {Pokutta, Sebastian}, title = {Information Theory and Polyhedral Combinatorics}, series = {Proceedings of 53rd Annual Allerton Conference on Communication, Control, and Computing}, booktitle = {Proceedings of 53rd Annual Allerton Conference on Communication, Control, and Computing}, language = {en} } @inproceedings{SongXiePokutta, author = {Song, R. and Xie, Y. and Pokutta, Sebastian}, title = {Sequential Sensing with Model Mismatch}, series = {Proceedings of ISIT}, booktitle = {Proceedings of ISIT}, language = {en} }