Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. Conditional Dichotomy of Boolean Ordered Promise CSPs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 37:1-37:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{brakensiek_et_al:LIPIcs.ICALP.2021.37, author = {Brakensiek, Joshua and Guruswami, Venkatesan and Sandeep, Sai}, title = {{Conditional Dichotomy of Boolean Ordered Promise CSPs}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.37}, URN = {urn:nbn:de:0030-drops-141060}, doi = {10.4230/LIPIcs.ICALP.2021.37}, annote = {Keywords: promise constraint satisfaction, Boolean ordered PCSP, Shapley value, rich 2-to-1 conjecture, random minor} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep. Revisiting Alphabet Reduction in Dinur’s PCP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 34:1-34:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2020.34, author = {Guruswami, Venkatesan and Opr\v{s}al, Jakub and Sandeep, Sai}, title = {{Revisiting Alphabet Reduction in Dinur’s PCP}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {34:1--34:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.34}, URN = {urn:nbn:de:0030-drops-126372}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.34}, annote = {Keywords: PCP theorem, CSP, discrete Fourier analysis, label cover, long code} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Venkatesan Guruswami and Sai Sandeep. Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 15:1-15:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{guruswami_et_al:LIPIcs.APPROX-RANDOM.2019.15, author = {Guruswami, Venkatesan and Sandeep, Sai}, title = {{Rainbow Coloring Hardness via Low Sensitivity Polymorphisms}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {15:1--15:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.15}, URN = {urn:nbn:de:0030-drops-112303}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.15}, annote = {Keywords: inapproximability, hardness of approximation, constraint satisfaction, hypergraph coloring, polymorphisms} }
Feedback for Dagstuhl Publishing