Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Ryan O'Donnell and Tselil Schramm. Sherali - Adams Strikes Back. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 8:1-8:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{odonnell_et_al:LIPIcs.CCC.2019.8, author = {O'Donnell, Ryan and Schramm, Tselil}, title = {{Sherali - Adams Strikes Back}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {8:1--8:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.8}, URN = {urn:nbn:de:0030-drops-108309}, doi = {10.4230/LIPIcs.CCC.2019.8}, annote = {Keywords: Linear programming, Sherali, Adams, max-cut, graph eigenvalues, Sum-of-Squares} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Ryuhei Mori and David Witmer. Lower Bounds for CSP Refutation by SDP Hierarchies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 41:1-41:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{mori_et_al:LIPIcs.APPROX-RANDOM.2016.41, author = {Mori, Ryuhei and Witmer, David}, title = {{Lower Bounds for CSP Refutation by SDP Hierarchies}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {41:1--41:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.41}, URN = {urn:nbn:de:0030-drops-66645}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.41}, annote = {Keywords: constraint satisfaction problems, LP and SDP relaxations, average-case complexity} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 110-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{barak_et_al:LIPIcs.APPROX-RANDOM.2015.110, author = {Barak, Boaz and Moitra, Ankur and O’Donnell, Ryan and Raghavendra, Prasad and Regev, Oded and Steurer, David and Trevisan, Luca and Vijayaraghavan, Aravindan and Witmer, David and Wright, John}, title = {{Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {110--123}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.110}, URN = {urn:nbn:de:0030-drops-52981}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.110}, annote = {Keywords: constraint satisfaction problems, bounded degree, advantage over random} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright. Improved NP-Inapproximability for 2-Variable Linear Equations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 341-360, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{hastad_et_al:LIPIcs.APPROX-RANDOM.2015.341, author = {H\r{a}stad, Johan and Huang, Sangxia and Manokaran, Rajsekar and O’Donnell, Ryan and Wright, John}, title = {{Improved NP-Inapproximability for 2-Variable Linear Equations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {341--360}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.341}, URN = {urn:nbn:de:0030-drops-53112}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.341}, annote = {Keywords: approximability, unique games, linear equation, gadget, linear programming} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Prasad Raghavendra and Tselil Schramm. Gap Amplification for Small-Set Expansion via Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 381-391, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{raghavendra_et_al:LIPIcs.APPROX-RANDOM.2014.381, author = {Raghavendra, Prasad and Schramm, Tselil}, title = {{Gap Amplification for Small-Set Expansion via Random Walks}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {381--391}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.381}, URN = {urn:nbn:de:0030-drops-47108}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.381}, annote = {Keywords: Gap amplification, Small-Set Expansion, random walks, graph products, Unique Games} }
Feedback for Dagstuhl Publishing