Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Marcin Bienkowski and Guy Even. An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bienkowski_et_al:LIPIcs.STACS.2024.15, author = {Bienkowski, Marcin and Even, Guy}, title = {{An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {15:1--15:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.15}, URN = {urn:nbn:de:0030-drops-197252}, doi = {10.4230/LIPIcs.STACS.2024.15}, annote = {Keywords: Minimum Linear Arrangement, dynamic Variant, Optimization Problems, Graph Problems, approximation Algorithms} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Siddharth Gupta, Guy Sa'ar, and Meirav Zehavi. Collective Graph Exploration Parameterized by Vertex Cover. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gupta_et_al:LIPIcs.IPEC.2023.22, author = {Gupta, Siddharth and Sa'ar, Guy and Zehavi, Meirav}, title = {{Collective Graph Exploration Parameterized by Vertex Cover}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {22:1--22:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.22}, URN = {urn:nbn:de:0030-drops-194413}, doi = {10.4230/LIPIcs.IPEC.2023.22}, annote = {Keywords: Collective Graph Exploration, Parameterized Complexity, Approximation Algorithm, Vertex Cover, Treedepth} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Siddharth Gupta, Guy Sa'ar, and Meirav Zehavi. Drawn Tree Decomposition: New Approach for Graph Drawing Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gupta_et_al:LIPIcs.IPEC.2023.23, author = {Gupta, Siddharth and Sa'ar, Guy and Zehavi, Meirav}, title = {{Drawn Tree Decomposition: New Approach for Graph Drawing Problems}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {23:1--23:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.23}, URN = {urn:nbn:de:0030-drops-194424}, doi = {10.4230/LIPIcs.IPEC.2023.23}, annote = {Keywords: Graph Drawing, Parameterized Complexity, Tree decomposition} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Sarah Azouvi, Guy Goren, Lioba Heimbach, and Alexander Hicks. Base Fee Manipulation in Ethereum’s EIP-1559 Transaction Fee Mechanism. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{azouvi_et_al:LIPIcs.DISC.2023.6, author = {Azouvi, Sarah and Goren, Guy and Heimbach, Lioba and Hicks, Alexander}, title = {{Base Fee Manipulation in Ethereum’s EIP-1559 Transaction Fee Mechanism}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {6:1--6:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.6}, URN = {urn:nbn:de:0030-drops-191325}, doi = {10.4230/LIPIcs.DISC.2023.6}, annote = {Keywords: blockchain, Ethereum, transaction fee mechanism, EIP-1559} }
Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)
Guy Avni, Pranav Ghorpade, and Shibashis Guha. A Game of Pawns. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{avni_et_al:LIPIcs.CONCUR.2023.16, author = {Avni, Guy and Ghorpade, Pranav and Guha, Shibashis}, title = {{A Game of Pawns}}, booktitle = {34th International Conference on Concurrency Theory (CONCUR 2023)}, pages = {16:1--16:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-299-0}, ISSN = {1868-8969}, year = {2023}, volume = {279}, editor = {P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.16}, URN = {urn:nbn:de:0030-drops-190100}, doi = {10.4230/LIPIcs.CONCUR.2023.16}, annote = {Keywords: Graph games, Reachability games, Pawn games, Dynamic vertex control} }
Published in: LIPIcs, Volume 256, 4th Symposium on Foundations of Responsible Computing (FORC 2023)
Cynthia Dwork, Omer Reingold, and Guy N. Rothblum. From the Real Towards the Ideal: Risk Prediction in a Better World. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dwork_et_al:LIPIcs.FORC.2023.1, author = {Dwork, Cynthia and Reingold, Omer and Rothblum, Guy N.}, title = {{From the Real Towards the Ideal: Risk Prediction in a Better World}}, booktitle = {4th Symposium on Foundations of Responsible Computing (FORC 2023)}, pages = {1:1--1:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-272-3}, ISSN = {1868-8969}, year = {2023}, volume = {256}, editor = {Talwar, Kunal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2023.1}, URN = {urn:nbn:de:0030-drops-179224}, doi = {10.4230/LIPIcs.FORC.2023.1}, annote = {Keywords: Algorithmic Fairness, Affirmative Action, Learning, Predictions, Multicalibration, Outcome Indistinguishability} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan. Certification with an NP Oracle. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{blanc_et_al:LIPIcs.ITCS.2023.18, author = {Blanc, Guy and Koch, Caleb and Lange, Jane and Strassle, Carmen and Tan, Li-Yang}, title = {{Certification with an NP Oracle}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {18:1--18:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.18}, URN = {urn:nbn:de:0030-drops-175217}, doi = {10.4230/LIPIcs.ITCS.2023.18}, annote = {Keywords: Certificate complexity, Boolean functions, polynomial hierarchy, hardness of approximation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Cynthia Rush, Fiona Skerman, Alexander S. Wein, and Dana Yang. Is It Easier to Count Communities Than Find Them?. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 94:1-94:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{rush_et_al:LIPIcs.ITCS.2023.94, author = {Rush, Cynthia and Skerman, Fiona and Wein, Alexander S. and Yang, Dana}, title = {{Is It Easier to Count Communities Than Find Them?}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {94:1--94:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.94}, URN = {urn:nbn:de:0030-drops-175970}, doi = {10.4230/LIPIcs.ITCS.2023.94}, annote = {Keywords: Community detection, Hypothesis testing, Low-degree polynomials} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Peter Mörters, Christian Sohler, and Stefan Walzer. A Sublinear Local Access Implementation for the Chinese Restaurant Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{morters_et_al:LIPIcs.APPROX/RANDOM.2022.28, author = {M\"{o}rters, Peter and Sohler, Christian and Walzer, Stefan}, title = {{A Sublinear Local Access Implementation for the Chinese Restaurant Process}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {28:1--28:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, 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.2022.28}, URN = {urn:nbn:de:0030-drops-171500}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.28}, annote = {Keywords: Chinese restaurant process, Dirichlet process, sublinear time algorithm, random recursive tree, random permutation, random partition, Ewens distribution, simulation, local access implementation, continuous time embedding} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Michael Dinitz, Ama Koranteng, and Guy Kortsarz. Relative Survivable Network Design. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dinitz_et_al:LIPIcs.APPROX/RANDOM.2022.41, author = {Dinitz, Michael and Koranteng, Ama and Kortsarz, Guy}, title = {{Relative Survivable Network Design}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {41:1--41:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, 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.2022.41}, URN = {urn:nbn:de:0030-drops-171632}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.41}, annote = {Keywords: Fault Tolerance, Network Design} }
Published in: LIPIcs, Volume 218, 3rd Symposium on Foundations of Responsible Computing (FORC 2022)
Elbert Du and Cynthia Dwork. Improved Generalization Guarantees in Restricted Data Models. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{du_et_al:LIPIcs.FORC.2022.6, author = {Du, Elbert and Dwork, Cynthia}, title = {{Improved Generalization Guarantees in Restricted Data Models}}, booktitle = {3rd Symposium on Foundations of Responsible Computing (FORC 2022)}, pages = {6:1--6:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-226-6}, ISSN = {1868-8969}, year = {2022}, volume = {218}, editor = {Celis, L. Elisa}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2022.6}, URN = {urn:nbn:de:0030-drops-165299}, doi = {10.4230/LIPIcs.FORC.2022.6}, annote = {Keywords: Differential Privacy, Adaptive Data Analysis, Transfer Theorem} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Guy Goldberg and Guy N. Rothblum. Sample-Based Proofs of Proximity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 77:1-77:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{goldberg_et_al:LIPIcs.ITCS.2022.77, author = {Goldberg, Guy and N. Rothblum, Guy}, title = {{Sample-Based Proofs of Proximity}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {77:1--77:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.77}, URN = {urn:nbn:de:0030-drops-156736}, doi = {10.4230/LIPIcs.ITCS.2022.77}, annote = {Keywords: Interactive Proof Systems, Sample-Based Access, Proofs of Proximity} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Siddharth Gupta, Guy Sa'ar, and Meirav Zehavi. Grid Recognition: Classical and Parameterized Computational Perspectives. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{gupta_et_al:LIPIcs.ISAAC.2021.37, author = {Gupta, Siddharth and Sa'ar, Guy and Zehavi, Meirav}, title = {{Grid Recognition: Classical and Parameterized Computational Perspectives}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.37}, URN = {urn:nbn:de:0030-drops-154703}, doi = {10.4230/LIPIcs.ISAAC.2021.37}, annote = {Keywords: Grid Recognition, Grid Graph, Parameterized Complexity} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan. Decision Tree Heuristics Can Fail, Even in the Smoothed Setting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blanc_et_al:LIPIcs.APPROX/RANDOM.2021.45, author = {Blanc, Guy and Lange, Jane and Qiao, Mingda and Tan, Li-Yang}, title = {{Decision Tree Heuristics Can Fail, Even in the Smoothed Setting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {45:1--45:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.45}, URN = {urn:nbn:de:0030-drops-147386}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.45}, annote = {Keywords: decision trees, learning theory, smoothed analysis} }
Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Gal Arnon and Guy N. Rothblum. On Prover-Efficient Public-Coin Emulation of Interactive Proofs. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arnon_et_al:LIPIcs.ITC.2021.3, author = {Arnon, Gal and Rothblum, Guy N.}, title = {{On Prover-Efficient Public-Coin Emulation of Interactive Proofs}}, booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-197-9}, ISSN = {1868-8969}, year = {2021}, volume = {199}, editor = {Tessaro, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.3}, URN = {urn:nbn:de:0030-drops-143226}, doi = {10.4230/LIPIcs.ITC.2021.3}, annote = {Keywords: Interactive Proofs, Computational complexity, Cryptography} }
Feedback for Dagstuhl Publishing