Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Yahli Hecht, Dor Minzer, and Muli Safra. NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hecht_et_al:LIPIcs.APPROX/RANDOM.2023.51, author = {Hecht, Yahli and Minzer, Dor and Safra, Muli}, title = {{NP-Hardness of Almost Coloring Almost 3-Colorable Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {51:1--51:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.51}, URN = {urn:nbn:de:0030-drops-188761}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.51}, annote = {Keywords: PCP, Hardness of approximation} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ittai Rubinstein. Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 105:1-105:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{rubinstein:LIPIcs.ICALP.2022.105, author = {Rubinstein, Ittai}, title = {{Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {105:1--105:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.105}, URN = {urn:nbn:de:0030-drops-164466}, doi = {10.4230/LIPIcs.ICALP.2022.105}, annote = {Keywords: Error Correcting Codes, Algorithmic Coding Theory, Binary Deletion Channel} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kelman_et_al:LIPIcs.ITCS.2021.26, author = {Kelman, Esty and Khot, Subhash and Kindler, Guy and Minzer, Dor and Safra, Muli}, title = {{Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {26:1--26:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.26}, URN = {urn:nbn:de:0030-drops-135657}, doi = {10.4230/LIPIcs.ITCS.2021.26}, annote = {Keywords: Fourier Analysis, Hypercontractivity, Log-Sobolev Inequality} }
Feedback for Dagstuhl Publishing