Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Dana Fisman, Joshua Grogin, Oded Margalit, and Gera Weiss. The Normalized Edit Distance with Uniform Operation Costs Is a Metric. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fisman_et_al:LIPIcs.CPM.2022.17, author = {Fisman, Dana and Grogin, Joshua and Margalit, Oded and Weiss, Gera}, title = {{The Normalized Edit Distance with Uniform Operation Costs Is a Metric}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {17:1--17:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.17}, URN = {urn:nbn:de:0030-drops-161446}, doi = {10.4230/LIPIcs.CPM.2022.17}, annote = {Keywords: edit distance, normalized distance, triangle inequality, metric} }
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} }
Feedback for Dagstuhl Publishing