Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Jun-Ting Hsieh, Sidhanth Mohanty, and Jeff Xu. Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 11:1-11:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{hsieh_et_al:LIPIcs.CCC.2022.11, author = {Hsieh, Jun-Ting and Mohanty, Sidhanth and Xu, Jeff}, title = {{Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {11:1--11:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.11}, URN = {urn:nbn:de:0030-drops-165735}, doi = {10.4230/LIPIcs.CCC.2022.11}, annote = {Keywords: constraint satisfaction problems, certified counting, random graphs} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, and Xinyu Wu. The SDP Value of Random 2CSPs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 97:1-97:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{musipatla_et_al:LIPIcs.ICALP.2022.97, author = {Musipatla, Amulya and O'Donnell, Ryan and Schramm, Tselil and Wu, Xinyu}, title = {{The SDP Value of Random 2CSPs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {97:1--97:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.97}, URN = {urn:nbn:de:0030-drops-164381}, doi = {10.4230/LIPIcs.ICALP.2022.97}, annote = {Keywords: Random constraint satisfaction problems} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The Strongish Planted Clique Hypothesis and Its Consequences. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 10:1-10:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{manurangsi_et_al:LIPIcs.ITCS.2021.10, author = {Manurangsi, Pasin and Rubinstein, Aviad and Schramm, Tselil}, title = {{The Strongish Planted Clique Hypothesis and Its Consequences}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {10:1--10:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.10}, URN = {urn:nbn:de:0030-drops-135491}, doi = {10.4230/LIPIcs.ITCS.2021.10}, annote = {Keywords: Planted Clique, Densest k-Subgraph, Hardness of Approximation} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman. Spectral Sparsification via Bounded-Independence Sampling. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 39:1-39:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{doron_et_al:LIPIcs.ICALP.2020.39, author = {Doron, Dean and Murtagh, Jack and Vadhan, Salil and Zuckerman, David}, title = {{Spectral Sparsification via Bounded-Independence Sampling}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {39:1--39:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.39}, URN = {urn:nbn:de:0030-drops-124462}, doi = {10.4230/LIPIcs.ICALP.2020.39}, annote = {Keywords: Spectral sparsification, Derandomization, Space complexity} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes. The SDP Value for Random Two-Eigenvalue CSPs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 50:1-50:45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{mohanty_et_al:LIPIcs.STACS.2020.50, author = {Mohanty, Sidhanth and O'Donnell, Ryan and Paredes, Pedro}, title = {{The SDP Value for Random Two-Eigenvalue CSPs}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {50:1--50:45}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.50}, URN = {urn:nbn:de:0030-drops-119110}, doi = {10.4230/LIPIcs.STACS.2020.50}, annote = {Keywords: Semidefinite programming, constraint satisfaction problems} }
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 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Pravesh K. Kothari, Ryan O'Donnell, and Tselil Schramm. SOS Lower Bounds with Hard Constraints: Think Global, Act Local. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 49:1-49:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{kothari_et_al:LIPIcs.ITCS.2019.49, author = {Kothari, Pravesh K. and O'Donnell, Ryan and Schramm, Tselil}, title = {{SOS Lower Bounds with Hard Constraints: Think Global, Act Local}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {49:1--49:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.49}, URN = {urn:nbn:de:0030-drops-101420}, doi = {10.4230/LIPIcs.ITCS.2019.49}, annote = {Keywords: sum-of-squares hierarchy, random constraint satisfaction problems} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg. Computing Exact Minimum Cuts Without Knowing the Graph. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 39:1-39:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2018.39, author = {Rubinstein, Aviad and Schramm, Tselil and Weinberg, S. Matthew}, title = {{Computing Exact Minimum Cuts Without Knowing the Graph}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {39:1--39:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.39}, URN = {urn:nbn:de:0030-drops-83168}, doi = {10.4230/LIPIcs.ITCS.2018.39}, annote = {Keywords: query complexity, minimum cut} }
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} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Varun Kanade, Elchanan Mossel, and Tselil Schramm. Global and Local Information in Clustering Labeled Block Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 779-792, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{kanade_et_al:LIPIcs.APPROX-RANDOM.2014.779, author = {Kanade, Varun and Mossel, Elchanan and Schramm, Tselil}, title = {{Global and Local Information in Clustering Labeled Block Models}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {779--792}, 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.779}, URN = {urn:nbn:de:0030-drops-47384}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.779}, annote = {Keywords: stochastic block models, information flow on trees} }
Feedback for Dagstuhl Publishing