Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Kamesh Munagala, Govind S. Sankar, and Erin Taylor. Probabilistic Metric Embedding via Metric Labeling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{munagala_et_al:LIPIcs.APPROX/RANDOM.2023.2, author = {Munagala, Kamesh and Sankar, Govind S. and Taylor, Erin}, title = {{Probabilistic Metric Embedding via Metric Labeling}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {2:1--2:10}, 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.2}, URN = {urn:nbn:de:0030-drops-188279}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.2}, annote = {Keywords: Metric Embedding, Approximation Algorithms, Ultrametrics} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Dániel Marx, Govind S. Sankar, and Philipp Schepper. Anti-Factor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard). In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{marx_et_al:LIPIcs.IPEC.2022.22, author = {Marx, D\'{a}niel and Sankar, Govind S. and Schepper, Philipp}, title = {{Anti-Factor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard)}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {22:1--22:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.22}, URN = {urn:nbn:de:0030-drops-173780}, doi = {10.4230/LIPIcs.IPEC.2022.22}, annote = {Keywords: Anti-Factor, General Factor, Treewidth, Representative Sets, SETH} }
Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)
S. Akshay, Paul Gastin, R. Govind, and B. Srivathsan. Simulations for Event-Clock Automata. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{akshay_et_al:LIPIcs.CONCUR.2022.13, author = {Akshay, S. and Gastin, Paul and Govind, R. and Srivathsan, B.}, title = {{Simulations for Event-Clock Automata}}, booktitle = {33rd International Conference on Concurrency Theory (CONCUR 2022)}, pages = {13:1--13:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-246-4}, ISSN = {1868-8969}, year = {2022}, volume = {243}, editor = {Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.13}, URN = {urn:nbn:de:0030-drops-170766}, doi = {10.4230/LIPIcs.CONCUR.2022.13}, annote = {Keywords: Event-clock automata, verification, zones, simulations, reachability} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Dániel Marx, Govind S. Sankar, and Philipp Schepper. Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{marx_et_al:LIPIcs.ICALP.2021.95, author = {Marx, D\'{a}niel and Sankar, Govind S. and Schepper, Philipp}, title = {{Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {95:1--95:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.95}, URN = {urn:nbn:de:0030-drops-141647}, doi = {10.4230/LIPIcs.ICALP.2021.95}, annote = {Keywords: General Factor, General Matching, Treewidth, Cutwidth} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
R. Govind, Frédéric Herbreteau, B. Srivathsan, and Igor Walukiewicz. Revisiting Local Time Semantics for Networks of Timed Automata. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{govind_et_al:LIPIcs.CONCUR.2019.16, author = {Govind, R. and Herbreteau, Fr\'{e}d\'{e}ric and Srivathsan, B. and Walukiewicz, Igor}, title = {{Revisiting Local Time Semantics for Networks of Timed Automata}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {16:1--16:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.16}, URN = {urn:nbn:de:0030-drops-109184}, doi = {10.4230/LIPIcs.CONCUR.2019.16}, annote = {Keywords: Timed automata, verification, local-time semantics, abstraction} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Yan Jin, Elchanan Mossel, and Govind Ramnarayan. Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{jin_et_al:LIPIcs.ITCS.2019.45, author = {Jin, Yan and Mossel, Elchanan and Ramnarayan, Govind}, title = {{Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {45:1--45:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.45}, URN = {urn:nbn:de:0030-drops-101388}, doi = {10.4230/LIPIcs.ITCS.2019.45}, annote = {Keywords: Corruption detection, PMC Model, Small Set Expansion, Hardness of Approximation} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. Relaxed Locally Correctable Codes. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 27:1-27:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gur_et_al:LIPIcs.ITCS.2018.27, author = {Gur, Tom and Ramnarayan, Govind and Rothblum, Ron D.}, title = {{Relaxed Locally Correctable Codes}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {27:1--27:11}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.27}, URN = {urn:nbn:de:0030-drops-83154}, doi = {10.4230/LIPIcs.ITCS.2018.27}, annote = {Keywords: Keywords and phrases Coding Theory, Locally Correctable Codes, Probabilistically Checkable Proofs} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Dana Moshkovitz, Govind Ramnarayan, and Henry Yuen. A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 42:1-42:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{moshkovitz_et_al:LIPIcs.APPROX-RANDOM.2016.42, author = {Moshkovitz, Dana and Ramnarayan, Govind and Yuen, Henry}, title = {{A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {42:1--42:29}, 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.42}, URN = {urn:nbn:de:0030-drops-66657}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.42}, annote = {Keywords: Derandomization, parallel repetition, Feige-Killian, fortification} }
Feedback for Dagstuhl Publishing