Document Search Results

Pitassi, Toniann; Shirley, Morgan; Shraibman, Adi

The strength of equality oracles in communication. (English) Zbl 07918410

Kalai, Yael Tauman (ed.), 14th innovations in theoretical computer science conference, ITCS 2023, January 10–13, 2023, MIT, Cambridge, Massachusetts, USA. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 251, Article 89, 19 p. (2023).

MSC: 68Qxx

Cite Review PDF

Full Text: DOI

Atserias, Albert; Dawar, Anuj; Ochremiak, Joanna

On the power of symmetric linear programs. (English) Zbl 1499.90121

J. ACM 68, No. 4, Article No. 26, 35 p. (2021).

MSC: 90C05 90C35

Cite Review PDF

Full Text: DOI arXiv

Chudnovsky, Maria; Seymour, Paul

Subdivided claws and the clique-stable set separation property. (English) Zbl 1484.05164

Wood, David R. (ed.) et al., 2019–20 MATRIX annals. Cham: Springer. MATRIX Book Ser. 4, 483-487 (2021).

MSC: 05C70 05C69 05C75 90C35

Cite Review PDF

Full Text: DOI arXiv

de Vries, Sven; Perscheid, Bernd

A smaller extended formulation for the odd cycle inequalities of the stable set polytope. (English) Zbl 1477.90082

Discrete Appl. Math. 303, 14-21 (2021).

MSC: 90C27

Cite Review PDF

Full Text: DOI

Aprile, Manuel; Faenza, Yuri

Extended formulations from communication protocols in output-efficient time. (English) Zbl 1458.94001

Math. Program. 183, No. 1-2 (B), 41-59 (2020).

MSC: 94A05 90C05 90C27 05C17 05C69 05C85 90C35

Cite Review PDF

Full Text: DOI arXiv

Shitov, Yaroslav

Matrices of bounded psd rank are easy to detect. (English) Zbl 1395.68155

SIAM J. Optim. 28, No. 3, 2067-2072 (2018).

MSC: 68Q25 15A23 15B48 90C22

Cite Review PDF

Full Text: DOI

Bousquet, Nicolas; Lagoutte, Aurélie; Maffray, Frédéric; Pastor, Lucas

Decomposition techniques applied to the clique-stable set separation problem. (English) Zbl 1383.05253

Discrete Math. 341, No. 5, 1492-1501 (2018).

MSC: 05C70

Cite Review PDF

Full Text: DOI arXiv

Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel

The matching problem has no small symmetric SDP. (English) Zbl 1373.90094

Math. Program. 165, No. 2 (A), 643-662 (2017).

MSC: 90C22 68Q17 05C70

Cite Review PDF

Full Text: DOI arXiv

Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel

The matching problem has no small symmetric SDP. (English) Zbl 1423.90209

Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1067-1078 (2016).

MSC: 90C27 90C22

Cite Review PDF

Full Text: DOI

Lagoutte, Aurélie; Trunck, Théophile

Clique-stable set separation in perfect graphs with no balanced skew-partitions. (English) Zbl 1333.05225

Discrete Math. 339, No. 6, 1809-1825 (2016).

MSC: 05C69 05C17 05C70 90C35

Cite Review PDF

Full Text: DOI arXiv

Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald

Exponential lower bounds for polytopes in combinatorial optimization. (English) Zbl 1333.90107

J. ACM 62, No. 2, Article No. 17, 23 p. (2015).

MSC: 90C27 68Q12 90C05 90C22 90C35

Cite Review PDF

Full Text: DOI arXiv Link

Shitov, Yaroslav

Tropical lower bounds for extended formulations. (English) Zbl 1331.15021

Math. Program. 153, No. 1 (B), 67-74 (2015).

Reviewer: John D. Dixon (Ottawa)

MSC: 15A80 52B55 15A23 15B48

Cite Review PDF

Full Text: DOI

Bogomolov, Yuri; Fiorini, Samuel; Maksimenko, Aleksandr; Pashkovich, Kanstantsin

Small extended formulations for cyclic polytopes. (English) Zbl 1354.52013

Discrete Comput. Geom. 53, No. 4, 809-816 (2015).

Reviewer: Alexander Esterov (Moscow)

MSC: 52B05 52B11 52B12 52B15

Cite Review PDF

Full Text: DOI arXiv

Gouveia, João; Parrilo, Pablo A.; Thomas, Rekha R.

Approximate cone factorizations and lifts of polytopes. (English) Zbl 1319.52010

Math. Program. 151, No. 2 (B), 613-637 (2015).

MSC: 52A23 52-02

Cite Review PDF

Full Text: DOI arXiv

Bousquet, N.; Lagoutte, A.; Thomassé, S.

Clique versus independent set. (English) Zbl 1297.05173

Eur. J. Comb. 40, 73-92 (2014).

MSC: 05C69 68Q25

Cite Review PDF

Full Text: DOI arXiv

Fiorini, Samuel; Kaibel, Volker; Pashkovich, Kanstantsin; Theis, Dirk Oliver

Combinatorial bounds on nonnegative rank and extended formulations. (English) Zbl 1259.90111

Discrete Math. 313, No. 1, 67-83 (2013).

MSC: 90C27

Cite Review PDF

Full Text: DOI arXiv

Kaibel, Volker; Pashkovich, Kanstantsin; Theis, Dirk Oliver

Symmetry matters for sizes of extended formulations. (English) Zbl 1267.90072

SIAM J. Discrete Math. 26, No. 3, 1361-1382 (2012).

Reviewer: Samir Kumar Neogy (New Delhi)

MSC: 90C10 90C57 52B12

Cite Review PDF

Full Text: DOI arXiv

Kaibel, Volker; Pashkovich, Kanstantsin; Theis, Dirk Oliver

Symmetry matters for the sizes of extended formulations. (English) Zbl 1285.90052

Eisenbrand, Friedrich (ed.) et al., Integer programming and combinatorial optimization. 14th international conference, IPCO 2010, Lausanne, Switzerland, June 9–11, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13035-9/pbk). Lecture Notes in Computer Science 6080, 135-148 (2010).

MSC: 90C27 05C38 90C57

Cite Review PDF

Full Text: DOI arXiv

Kushilevitz, Eyal; Weinreb, Enav

On the complexity of communication complexity. (English) Zbl 1304.68077

Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 465-474 (2009).

MSC: 68Q25 68Q05 68Q17

Cite Review PDF

Full Text: DOI

Found 19 Documents (Results 1–19)

The strength of equality oracles in communication. (English) Zbl 07918410

On the power of symmetric linear programs. (English) Zbl 1499.90121

Subdivided claws and the clique-stable set separation property. (English) Zbl 1484.05164

A smaller extended formulation for the odd cycle inequalities of the stable set polytope. (English) Zbl 1477.90082

Extended formulations from communication protocols in output-efficient time. (English) Zbl 1458.94001

Matrices of bounded psd rank are easy to detect. (English) Zbl 1395.68155

Decomposition techniques applied to the clique-stable set separation problem. (English) Zbl 1383.05253

The matching problem has no small symmetric SDP. (English) Zbl 1373.90094

The matching problem has no small symmetric SDP. (English) Zbl 1423.90209

Clique-stable set separation in perfect graphs with no balanced skew-partitions. (English) Zbl 1333.05225

Exponential lower bounds for polytopes in combinatorial optimization. (English) Zbl 1333.90107

Tropical lower bounds for extended formulations. (English) Zbl 1331.15021

Small extended formulations for cyclic polytopes. (English) Zbl 1354.52013

Approximate cone factorizations and lifts of polytopes. (English) Zbl 1319.52010

Clique versus independent set. (English) Zbl 1297.05173

Combinatorial bounds on nonnegative rank and extended formulations. (English) Zbl 1259.90111

Symmetry matters for sizes of extended formulations. (English) Zbl 1267.90072

Symmetry matters for the sizes of extended formulations. (English) Zbl 1285.90052

On the complexity of communication complexity. (English) Zbl 1304.68077

Filter Results by …

Document Type

Author

Serial

Year of Publication

Main Field