[1]   Miklós Ajtai, János Komlós, and Endre Szemerédi: Sorting in clog n parallel steps. Combinatorica, 3(1):1–19, 1983. [doi:10.1007/BF02579338]

[2]   Hyung-Chan An, Mohit Singh, and Ola Svensson: LP-based algorithms for Capacitated Facility Location. SIAM J. Comput., 46(1):272–306, 2017. Conference version in FOCS’14. [doi:10.1137/151002320]

[3]   Egon Balas: Facets of the knapsack polytope. Mathematical Programming, 8(1):146–164, 1975. [doi:10.1007/BF01580440]

[4]   Nikhil Bansal, Niv Buchbinder, and Joseph (Seffi) Naor: Randomized competitive algorithms for generalized caching. SIAM J. Comput., 41(2):391–414, 2012. Conference version in STOC’08. [doi:10.1137/090779000]

[5]   Nikhil Bansal, Anupam Gupta, and Ravishankar Krishnaswamy: A constant factor approximation algorithm for generalized min-sum set cover. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’10), pp. 1539–1545, 2010. [doi:10.1137/1.9781611973075.125]

[6]   Nikhil Bansal and Kirk Pruhs: The geometry of scheduling. SIAM J. Comput., 43(5):1684–1698, 2014. Conference version in FOCS’10. [doi:10.1137/130911317, arXiv:1008.4889]

[7]   Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson: Small extended formulation for knapsack cover inequalities from monotone circuits. In Proc. 28th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’17), pp. 2326–2341, 2000. ACM DL.

[8]   Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, and Ola Svensson: No small linear program approximates Vertex Cover within a factor of 2 - ε. Math. Oper. Res., 2018. Conference version in FOCS’15. [doi:10.1287/moor.2017.0918, arXiv:1503.00753]

[9]   Amos Beimel and Enav Weinreb: Monotone circuits for weighted threshold functions. In Proc. 20th IEEE Conf. on Computational Complexity (CCC’05), pp. 67–75. IEEE, 2005. [doi:10.1109/CCC.2005.12]

[10]   Amos Beimel and Enav Weinreb: Monotone circuits for monotone weighted threshold functions. Inform. Process. Lett., 97(1):12–18, 2006. Conference version in CCC’05. [doi:10.1016/j.ipl.2005.09.008]

[11]   Daniel Bienstock: Approximate formulations for 0-1 knapsack sets. Oper. Res. Lett., 36(3):317–320, 2008. [doi:10.1016/j.orl.2007.09.003]

[12]   Daniel Bienstock and Benjamin McClosky: Tightening simple mixed-integer sets with guaranteed bounds. Math. Program., 133(1-2):337–363, 2012. [doi:10.1007/s10107-010-0435-x]

[13]   Gábor Braun, Samuel Fiorini, Sebastian Pokutta, and David Steurer: Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res., 40(3):513–796, 2015. Conference version in FOCS’12. [doi:10.1287/moor.2014.0694, arXiv:1204.0957]

[14]   Tim Carnes and David B. Shmoys: Primal-dual schema for capacitated covering problems. Math. Program., 153(2):289–308, 2015. Conference version in IPCO’08. [doi:10.1007/s10107-014-0803-z]

[15]   Robert D. Carr, Lisa K. Fleischer, Vitus J. Leung, and Cynthia A. Phillips: Strengthening integrality gaps for capacitated network design and covering problems. In Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’00), pp. 106–115, 2000. ACM DL.

[16]   Deeparnab Chakrabarty, Elyot Grant, and Jochen Könemann: On column restricted and priority integer covering programs. In Proc. 14th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO ’10), 2010. [doi:10.1007/978-3-642-13036-6_27, arXiv:1003.1507]

[17]   Siu On Chan, James Lee, Prasad Raghavendra, and David Steurer: Approximate constraint satisfaction requires large LP relaxations. J. ACM, 63(4):34:1–34:22, 2016. Conference version in FOCS’13. [doi:10.1145/2811255]

[18]   Xi Chen, Igor Carboni Oliveira, and Rocco A. Servedio: Addition is exponentially harder than counting for shallow monotone circuits. In Proc. 49th STOC, pp. 1232–1245, 2017. [doi:10.1145/3055399.3055425, arXiv:1508.03061]

[19]   Maurice Cheung, Julián Mestre, David B. Shmoys, and José Verschae: A primal-dual approximation algorithm for min-sum single-machine scheduling problems. SIAM J. Discrete Math., 31(2):825–838, 2017. [doi:10.1137/16M1086819, arXiv:1612.03339]

[20]   Maurice Cheung and David B. Shmoys: A primal-dual approximation algorithm for min-sum single-machine scheduling problems. In APPROX’11, pp. 135–146, 2011. [doi:10.1007/978-3-642-22935-0_12]

[21]   Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli: Extended formulations in combinatorial optimization. 4OR, 8(1):1–48, 2010. [doi:10.1007/s10288-010-0122-z]

[22]   Hossein Efsandiari, Mohammad Taghi Hajiaghayi, Jochen Könemann, Hamid Mahini, David L. Malec, and Laura Sanità: Approximate deadline-scheduling with precedence constraints. In Proc. 23rd Ann. European Symp. on Algorithms (ESA’15), pp. 483–495. Springer, 2015. [doi:10.1007/978-3-662-48350-3_41, arXiv:1507.00748]

[23]   Yuri Faenza, Samuel Fiorini, Roland Grappe, and Hans Raj Tiwary: Extended formulations, non-negative factorizations and randomized communication protocols. Math. Program., 153(1):75–94, 2015. Conference version in ISCO’12. [doi:10.1007/s10107-014-0755-3, arXiv:1105.4127]

[24]   Samuel Fiorini, Tony Huynh, and Stefan Weltge: Strengthening convex relaxations of 0/1-sets using Boolean formulas. 2017. [arXiv:1711.01358]

[25]   Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM, 62(2):17:1–17:23, 2015. Conference version in STOC’12. [doi:10.1145/2716307]

[26]   Mika Göös, Rahul Jain, and Thomas Watson: Extension complexity of independent set polytopes. SIAM J. Comput., 47(1):241–269, 2018. Conference version in FOCS’16. [doi:10.1137/16M109884X, arXiv:1604.07062]

[27]   Peter L. Hammer, Ellis L. Johnson, and Uri N. Peled: Facet of regular 0-1 polytopes. Math. Program., 8(1):179–206, 1975. [doi:10.1007/BF01580442]

[28]   Pavel Hrubeš: On the nonnegative rank of distance matrices. Inform. Process. Lett., 112(11):457–461, 2012. [doi:10.1016/j.ipl.2012.02.009]

[29]   Mauricio Karchmer and Avi Wigderson: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math., 3(2):255–265, 1990. Conference version in STOC’88. [doi:10.1137/0403021]

[30]   Richard M. Karp: Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pp. 85–103. Plenum Press, New York, 1972. PDF. [doi:10.1007/978-1-4684-2001-2_9]

[31]   Eugene L. Lawler: Fast approximation algorithms for knapsack problems. Math. Oper. Res., 4(2):339–356, 1979. Conference version in FOCS’77. [doi:10.1287/moor.4.4.339]

[32]   James R. Lee, Prasad Raghavendra, and David Steurer: Lower bounds on the size of semidefinite programming relaxations. In Proc. 47th STOC, pp. 567–576, 2015. [doi:10.1145/2746539.2746599]

[33]   Retsef Levi, Andrea Lodi, and Maxim Sviridenko: Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities. Math. Oper. Res., 33(2):461–474, 2008. Conference version in IPCO’07. [doi:10.1287/moor.1070.0305]

[34]   Julián Mestre and José Verschae: A 4-approximation for scheduling on a single machine with general cost function. CoRR, 2014. [arXiv:1403.0298]

[35]    Saburo Muroga: Threshold Logic and Its Applications. Wiley-Interscience, 1971.

[36]   Saburo Muroga, Iwao Toda, and Satoru Takasu: Theory of majority decision elements. J. Franklin Institute, 271(5):376–418, 1961. [doi:10.1016/0016-0032(61)90702-5]

[37]   Manfred W. Padberg, Tony J. Van Roy, and Laurence A. Wolsey: Valid inequalities for fixed charge problems. Operations Research, 33(4):842–861, 1985. [doi:10.1287/opre.33.4.842]

[38]   Sebastian Pokutta and Mathieu Van Vyve: A note on the extension complexity of the knapsack polytope. Oper. Res. Lett., 41(4):347–350, 2013. [doi:10.1016/j.orl.2013.03.010]

[39]   Thomas Rothvoß: The matching polytope has exponential extension complexity. J. ACM, 64(6):41:1–41:19, 2017. Conference version in STOC’14. [doi:10.1145/3127497, arXiv:1311.2369]

[40]   Laurence A. Wolsey: Faces for a linear inequality in 0-1 variables. Math. Program., 8(1):165–178, 1975. [doi:10.1007/BF01580441]

[41]   Mihalis Yannakakis: Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci., 43(3):441–466, 1991. Conference version in STOC’88. [doi:10.1016/0022-0000(91)90024-Y]