Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Anna Brandenberger, Byron Chin, Nathan S. Sheffield, and Divya Shyamal. Matching Algorithms in the Sparse Stochastic Block Model. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{brandenberger_et_al:LIPIcs.AofA.2024.16, author = {Brandenberger, Anna and Chin, Byron and Sheffield, Nathan S. and Shyamal, Divya}, title = {{Matching Algorithms in the Sparse Stochastic Block Model}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {16:1--16:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.16}, URN = {urn:nbn:de:0030-drops-204515}, doi = {10.4230/LIPIcs.AofA.2024.16}, annote = {Keywords: Matching Algorithms, Online Matching, Stochastic Block Model} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Gil Cohen and Tal Yankovitz. Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cohen_et_al:LIPIcs.CCC.2024.8, author = {Cohen, Gil and Yankovitz, Tal}, title = {{Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.8}, URN = {urn:nbn:de:0030-drops-204045}, doi = {10.4230/LIPIcs.CCC.2024.8}, annote = {Keywords: Relaxed locally decodable codes, Relxaed locally correctable codes, RLCC, RLDC} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Yaroslav Alekseev, Yuval Filmus, and Alexander Smal. Lifting Dichotomies. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alekseev_et_al:LIPIcs.CCC.2024.9, author = {Alekseev, Yaroslav and Filmus, Yuval and Smal, Alexander}, title = {{Lifting Dichotomies}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.9}, URN = {urn:nbn:de:0030-drops-204051}, doi = {10.4230/LIPIcs.CCC.2024.9}, annote = {Keywords: decision trees, log-rank conjecture, lifting, parity decision trees} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
G. A. Kavvos. Two-Dimensional Kripke Semantics I: Presheaves. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kavvos:LIPIcs.FSCD.2024.14, author = {Kavvos, G. A.}, title = {{Two-Dimensional Kripke Semantics I: Presheaves}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {14:1--14:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-323-2}, ISSN = {1868-8969}, year = {2024}, volume = {299}, editor = {Rehof, Jakob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.14}, URN = {urn:nbn:de:0030-drops-203438}, doi = {10.4230/LIPIcs.FSCD.2024.14}, annote = {Keywords: modal logic, categorical semantics, Kripke semantics, duality, open maps} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, and Carlos Palazuelos. Learning Low-Degree Quantum Objects. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arunachalam_et_al:LIPIcs.ICALP.2024.13, author = {Arunachalam, Srinivasan and Dutt, Arkopal and Escudero Guti\'{e}rrez, Francisco and Palazuelos, Carlos}, title = {{Learning Low-Degree Quantum Objects}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {13:1--13:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.13}, URN = {urn:nbn:de:0030-drops-201563}, doi = {10.4230/LIPIcs.ICALP.2024.13}, annote = {Keywords: Tomography} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Christoph Haase, Shankara Narayanan Krishna, Khushraj Madnani, Om Swostik Mishra, and Georg Zetzsche. An Efficient Quantifier Elimination Procedure for Presburger Arithmetic. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 142:1-142:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{haase_et_al:LIPIcs.ICALP.2024.142, author = {Haase, Christoph and Krishna, Shankara Narayanan and Madnani, Khushraj and Mishra, Om Swostik and Zetzsche, Georg}, title = {{An Efficient Quantifier Elimination Procedure for Presburger Arithmetic}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {142:1--142:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.142}, URN = {urn:nbn:de:0030-drops-202856}, doi = {10.4230/LIPIcs.ICALP.2024.142}, annote = {Keywords: Presburger arithmetic, quantifier elimination, parametric integer programming, convex geometry} }
Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)
Anshuman Misra and Ajay D. Kshemkalyani. Detecting Causality in the Presence of Byzantine Processes: The Synchronous Systems Case. In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{misra_et_al:LIPIcs.TIME.2023.11, author = {Misra, Anshuman and Kshemkalyani, Ajay D.}, title = {{Detecting Causality in the Presence of Byzantine Processes: The Synchronous Systems Case}}, booktitle = {30th International Symposium on Temporal Representation and Reasoning (TIME 2023)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-298-3}, ISSN = {1868-8969}, year = {2023}, volume = {278}, editor = {Artikis, Alexander and Bruse, Florian and Hunsberger, Luke}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.11}, URN = {urn:nbn:de:0030-drops-191017}, doi = {10.4230/LIPIcs.TIME.2023.11}, annote = {Keywords: Byzantine fault-tolerance, causality, happens before, distributed system, message-passing, synchronous system} }
Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)
Nikos Katzouris and Georgios Paliouras. Answer Set Automata: A Learnable Pattern Specification Framework for Complex Event Recognition (Extended Abstract). In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 17:1-17:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{katzouris_et_al:LIPIcs.TIME.2023.17, author = {Katzouris, Nikos and Paliouras, Georgios}, title = {{Answer Set Automata: A Learnable Pattern Specification Framework for Complex Event Recognition}}, booktitle = {30th International Symposium on Temporal Representation and Reasoning (TIME 2023)}, pages = {17:1--17:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-298-3}, ISSN = {1868-8969}, year = {2023}, volume = {278}, editor = {Artikis, Alexander and Bruse, Florian and Hunsberger, Luke}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.17}, URN = {urn:nbn:de:0030-drops-191071}, doi = {10.4230/LIPIcs.TIME.2023.17}, annote = {Keywords: Event Pattern Learning, Answer Set Programming} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Alexander Bille, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. A Graph-Theoretic Formulation of Exploratory Blockmodeling. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bille_et_al:LIPIcs.SEA.2023.14, author = {Bille, Alexander and Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils}, title = {{A Graph-Theoretic Formulation of Exploratory Blockmodeling}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {14:1--14:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.14}, URN = {urn:nbn:de:0030-drops-183648}, doi = {10.4230/LIPIcs.SEA.2023.14}, annote = {Keywords: Clustering, Exact Algorithms, ILP-Formulation, Branch-and-Bound, Social Networks} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu. On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{block_et_al:LIPIcs.CCC.2023.14, author = {Block, Alexander R. and Blocki, Jeremiah and Cheng, Kuan and Grigorescu, Elena and Li, Xin and Zheng, Yu and Zhu, Minshen}, title = {{On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {14:1--14:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.14}, URN = {urn:nbn:de:0030-drops-182847}, doi = {10.4230/LIPIcs.CCC.2023.14}, annote = {Keywords: Relaxed Locally Decodable Codes, Hamming Errors, Insdel Errors, Lower Bounds} }
Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)
Alexander van der Grinten, Maria Predari, and Florian Willich. A Fast Data Structure for Dynamic Graphs Based on Hash-Indexed Adjacency Blocks. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{vandergrinten_et_al:LIPIcs.SEA.2022.11, author = {van der Grinten, Alexander and Predari, Maria and Willich, Florian}, title = {{A Fast Data Structure for Dynamic Graphs Based on Hash-Indexed Adjacency Blocks}}, booktitle = {20th International Symposium on Experimental Algorithms (SEA 2022)}, pages = {11:1--11:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-251-8}, ISSN = {1868-8969}, year = {2022}, volume = {233}, editor = {Schulz, Christian and U\c{c}ar, Bora}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.11}, URN = {urn:nbn:de:0030-drops-165453}, doi = {10.4230/LIPIcs.SEA.2022.11}, annote = {Keywords: dynamic graph data structures, sparse matrix layout, dynamic algorithms, parallel algorithms, graph analysis} }
Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Alexander R. Block, Simina Brânzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, and Hai H. Nguyen. P₄-free Partition and Cover Numbers & Applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 16:1-16:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{block_et_al:LIPIcs.ITC.2021.16, author = {Block, Alexander R. and Br\^{a}nzei, Simina and Maji, Hemanta K. and Mehta, Himanshi and Mukherjee, Tamalika and Nguyen, Hai H.}, title = {{P₄-free Partition and Cover Numbers \& Applications}}, booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)}, pages = {16:1--16:25}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.16}, URN = {urn:nbn:de:0030-drops-143357}, doi = {10.4230/LIPIcs.ITC.2021.16}, annote = {Keywords: Secure keys, Secure private randomness, Gray-Wyner system, Cryptographic complexity, Nondeterministic communication complexity, Leakage-resilience, Combinatorial optimization, Product dimension, Zarankiewicz problem, Algebraic lower-bounding techniques, P₄-free partition number, P₄-free cover number} }
Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Idit Keidar. Byzantine Agreement and SMR with Sub-Quadratic Message Complexity (Invited Talk). In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{keidar:LIPIcs.OPODIS.2020.2, author = {Keidar, Idit}, title = {{Byzantine Agreement and SMR with Sub-Quadratic Message Complexity}}, booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-176-4}, ISSN = {1868-8969}, year = {2021}, volume = {184}, editor = {Bramas, Quentin and Oshman, Rotem and Romano, Paolo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.2}, URN = {urn:nbn:de:0030-drops-134874}, doi = {10.4230/LIPIcs.OPODIS.2020.2}, annote = {Keywords: Distributed Computing, Byzantine Agreement} }
Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Alexander Spiegelman, Arik Rinberg, and Dahlia Malkhi. ACE: Abstract Consensus Encapsulation for Liveness Boosting of State Machine Replication. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{spiegelman_et_al:LIPIcs.OPODIS.2020.9, author = {Spiegelman, Alexander and Rinberg, Arik and Malkhi, Dahlia}, title = {{ACE: Abstract Consensus Encapsulation for Liveness Boosting of State Machine Replication}}, booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-176-4}, ISSN = {1868-8969}, year = {2021}, volume = {184}, editor = {Bramas, Quentin and Oshman, Rotem and Romano, Paolo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.9}, URN = {urn:nbn:de:0030-drops-134948}, doi = {10.4230/LIPIcs.OPODIS.2020.9}, annote = {Keywords: Framework, Asynchronous, Consensus boosting, State Machine Replication} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Alexander R. Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, and Minshen Zhu. Locally Decodable/Correctable Codes for Insertions and Deletions. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{block_et_al:LIPIcs.FSTTCS.2020.16, author = {Block, Alexander R. and Blocki, Jeremiah and Grigorescu, Elena and Kulkarni, Shubhang and Zhu, Minshen}, title = {{Locally Decodable/Correctable Codes for Insertions and Deletions}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {16:1--16:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.16}, URN = {urn:nbn:de:0030-drops-132577}, doi = {10.4230/LIPIcs.FSTTCS.2020.16}, annote = {Keywords: Locally decodable/correctable codes, insert-delete channel} }