TY - CHAP A1 - Bazzi, Abbas A1 - Fiorini, Samuel A1 - Pokutta, Sebastian A1 - Svensson, Ola T1 - Small linear programs cannot approximate Vertex Cover within a factor of 2 - epsilon T2 - Proceedings of FOCS Y1 - 2015 N1 - URL of the Slides: https://app.box.com/s/00aqupo722bbpmdcyzwt8xmfqzyu14iy 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 - CHAP A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - The matching polytope does not admit fully-polynomial size relaxation schemes T2 - Proceeedings of SODA Y1 - 2015 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 - CHAP A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Zink, Daniel T1 - Inapproximability of combinatorial problems via small LPs and SDPs T2 - Proceeedings of STOC Y1 - 2015 ER - TY - JOUR A1 - Briët, Jop A1 - Dadush, Daniel A1 - Pokutta, Sebastian T1 - On the existence of 0/1 polytopes with high semidefinite extension complexity JF - Mathematical Programming B Y1 - 2015 VL - 153 IS - 1 SP - 179 EP - 199 ER - TY - JOUR A1 - Fiorini, Samuel A1 - Massar, S. A1 - Pokutta, Sebastian A1 - Tiwary, H.R. A1 - de Wolf, R. T1 - Exponential Lower Bounds for Polytopes in Combinatorial Optimization JF - Journal of the ACM Y1 - 2015 N1 - URL of the PDF: https://doi.org/10.1145/2716307 VL - 62 IS - 2 SP - 1 EP - 17 ER - TY - CHAP A1 - Pokutta, Sebastian T1 - Information Theory and Polyhedral Combinatorics T2 - Proceedings of 53rd Annual Allerton Conference on Communication, Control, and Computing Y1 - 2015 N1 - Additional Note: http://ieeexplore.ieee.org/abstract/document/7447134/ N1 - URL of the PDF: http://ieeexplore.ieee.org/abstract/document/7447134/ ER - TY - CHAP A1 - Song, R. A1 - Xie, Y. A1 - Pokutta, Sebastian T1 - Sequential Sensing with Model Mismatch T2 - Proceedings of ISIT Y1 - 2015 ER - TY - CHAP A1 - Xie, Y. A1 - Li, Q. A1 - Pokutta, Sebastian T1 - Supervised Online Subspace Tracking T2 - Proceedings of Asilomar Conference on Signals, Systems, and Computers Y1 - 2015 ER -