Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Karl Bringmann, Allan Grønlund, Marvin Künnemann, and Kasper Green Larsen. The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 22:1-22:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bringmann_et_al:LIPIcs.ITCS.2024.22, author = {Bringmann, Karl and Gr{\o}nlund, Allan and K\"{u}nnemann, Marvin and Larsen, Kasper Green}, title = {{The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {22:1--22:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.22}, URN = {urn:nbn:de:0030-drops-195500}, doi = {10.4230/LIPIcs.ITCS.2024.22}, annote = {Keywords: Fine-grained complexity theory, non-deterministic finite automata} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Minming Li, Peter Robinson, and Xianbin Zhu. Dynamic Maximal Matching in Clique Networks. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 73:1-73:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ITCS.2024.73, author = {Li, Minming and Robinson, Peter and Zhu, Xianbin}, title = {{Dynamic Maximal Matching in Clique Networks}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {73:1--73:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.73}, URN = {urn:nbn:de:0030-drops-196017}, doi = {10.4230/LIPIcs.ITCS.2024.73}, annote = {Keywords: distributed graph algorithm, dynamic network, maximal matching, randomized algorithm, lower bound} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Arvind V. Mahankali, David P. Woodruff, and Ziyu Zhang. Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 79:1-79:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mahankali_et_al:LIPIcs.ITCS.2024.79, author = {Mahankali, Arvind V. and Woodruff, David P. and Zhang, Ziyu}, title = {{Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {79:1--79:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.79}, URN = {urn:nbn:de:0030-drops-196078}, doi = {10.4230/LIPIcs.ITCS.2024.79}, annote = {Keywords: Low rank approximation, Sketching algorithms, Tensor decomposition} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Iddo Tzameret and Lu-Ming Zhang. Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 95:1-95:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{tzameret_et_al:LIPIcs.ITCS.2024.95, author = {Tzameret, Iddo and Zhang, Lu-Ming}, title = {{Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {95:1--95:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.95}, URN = {urn:nbn:de:0030-drops-196234}, doi = {10.4230/LIPIcs.ITCS.2024.95}, annote = {Keywords: Pseudorandomness, Cryptography, Natural Proofs, Nondeterminism, Lower bounds} }
Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
João Paulo Bezerra and Petr Kuznetsov. A Tight Bound on Multiple Spending in Decentralized Cryptocurrencies. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bezerra_et_al:LIPIcs.OPODIS.2023.31, author = {Bezerra, Jo\~{a}o Paulo and Kuznetsov, Petr}, title = {{A Tight Bound on Multiple Spending in Decentralized Cryptocurrencies}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {31:1--31:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.31}, URN = {urn:nbn:de:0030-drops-195210}, doi = {10.4230/LIPIcs.OPODIS.2023.31}, annote = {Keywords: Quorum systems, decentralized trust, consistency measure, asset transfer, accountability} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden. Minimum Separator Reconfiguration. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2023.9, author = {C. M. Gomes, Guilherme and Legrand-Duchesne, Cl\'{e}ment and Mahmoud, Reem and Mouawad, Amer E. and Okamoto, Yoshio and F. dos Santos, Vinicius and C. van der Zanden, Tom}, title = {{Minimum Separator Reconfiguration}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {9:1--9:12}, 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.9}, URN = {urn:nbn:de:0030-drops-194288}, doi = {10.4230/LIPIcs.IPEC.2023.9}, annote = {Keywords: minimum separators, combinatorial reconfiguration, parameterized complexity, kernelization} }
Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Nisheeth K. Vishnoi. Algorithms in the Presence of Biased Inputs (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 5:1-5:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{vishnoi:LIPIcs.FSTTCS.2023.5, author = {Vishnoi, Nisheeth K.}, title = {{Algorithms in the Presence of Biased Inputs}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {5:1--5:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.5}, URN = {urn:nbn:de:0030-drops-193788}, doi = {10.4230/LIPIcs.FSTTCS.2023.5}, annote = {Keywords: Algorithmic Bias} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Kazuyuki Amano. Depth-Three Circuits for Inner Product and Majority Functions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{amano:LIPIcs.ISAAC.2023.7, author = {Amano, Kazuyuki}, title = {{Depth-Three Circuits for Inner Product and Majority Functions}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.7}, URN = {urn:nbn:de:0030-drops-193092}, doi = {10.4230/LIPIcs.ISAAC.2023.7}, annote = {Keywords: Circuit complexity, depth-3 circuits, upper bounds, lower bounds, computer-assisted proof} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Mong-Jen Kao. Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kao:LIPIcs.ISAAC.2023.45, author = {Kao, Mong-Jen}, title = {{Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {45:1--45:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.45}, URN = {urn:nbn:de:0030-drops-193474}, doi = {10.4230/LIPIcs.ISAAC.2023.45}, annote = {Keywords: Capacitated facility location, Hard capacities, Uniform facility cost} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Neeldhara Misra, Harshil Mittal, Saket Saurabh, and Dhara Thakkar. On the Complexity of the Eigenvalue Deletion Problem. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{misra_et_al:LIPIcs.ISAAC.2023.53, author = {Misra, Neeldhara and Mittal, Harshil and Saurabh, Saket and Thakkar, Dhara}, title = {{On the Complexity of the Eigenvalue Deletion Problem}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {53:1--53:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.53}, URN = {urn:nbn:de:0030-drops-193555}, doi = {10.4230/LIPIcs.ISAAC.2023.53}, annote = {Keywords: Graph Modification, Rank Reduction, Eigenvalues} }
Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)
Stefan Dziembowski and Paweł Kędzior. Non-Atomic Payment Splitting in Channel Networks. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dziembowski_et_al:LIPIcs.AFT.2023.17, author = {Dziembowski, Stefan and K\k{e}dzior, Pawe{\l}}, title = {{Non-Atomic Payment Splitting in Channel Networks}}, booktitle = {5th Conference on Advances in Financial Technologies (AFT 2023)}, pages = {17:1--17:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-303-4}, ISSN = {1868-8969}, year = {2023}, volume = {282}, editor = {Bonneau, Joseph and Weinberg, S. Matthew}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.17}, URN = {urn:nbn:de:0030-drops-192068}, doi = {10.4230/LIPIcs.AFT.2023.17}, annote = {Keywords: Blockchain, Payment Channels Networks} }
Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)
Ertem Nusret Tas and Dan Boneh. Vector Commitments with Efficient Updates. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 29:1-29:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{tas_et_al:LIPIcs.AFT.2023.29, author = {Tas, Ertem Nusret and Boneh, Dan}, title = {{Vector Commitments with Efficient Updates}}, booktitle = {5th Conference on Advances in Financial Technologies (AFT 2023)}, pages = {29:1--29:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-303-4}, ISSN = {1868-8969}, year = {2023}, volume = {282}, editor = {Bonneau, Joseph and Weinberg, S. Matthew}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.29}, URN = {urn:nbn:de:0030-drops-192184}, doi = {10.4230/LIPIcs.AFT.2023.29}, annote = {Keywords: Vector commitments, stateless clients} }
Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Petr Kučera. Binary Constraint Trees and Structured Decomposability. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kucera:LIPIcs.CP.2023.22, author = {Ku\v{c}era, Petr}, title = {{Binary Constraint Trees and Structured Decomposability}}, booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)}, pages = {22:1--22:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-300-3}, ISSN = {1868-8969}, year = {2023}, volume = {280}, editor = {Yap, Roland H. C.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.22}, URN = {urn:nbn:de:0030-drops-190595}, doi = {10.4230/LIPIcs.CP.2023.22}, annote = {Keywords: Binary CSP, Binary Constraint Tree, Structured Decomposability, Strucured DNNF, Polynomial Equivalence} }
Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Nicolas Golenvaux, Xavier Gillard, Siegfried Nijssen, and Pierre Schaus. Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 45:1-45:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{golenvaux_et_al:LIPIcs.CP.2023.45, author = {Golenvaux, Nicolas and Gillard, Xavier and Nijssen, Siegfried and Schaus, Pierre}, title = {{Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams}}, booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)}, pages = {45:1--45:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-300-3}, ISSN = {1868-8969}, year = {2023}, volume = {280}, editor = {Yap, Roland H. C.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.45}, URN = {urn:nbn:de:0030-drops-190825}, doi = {10.4230/LIPIcs.CP.2023.45}, annote = {Keywords: Regionalization, Redcap, Skater, Multivalued Decision Diagrams} }
Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)
Luke Hunsberger and Roberto Posenato. Converting Simple Temporal Networks with Uncertainty into Dispatchable Form - Faster (Extended Abstract). In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 20:1-20:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hunsberger_et_al:LIPIcs.TIME.2023.20, author = {Hunsberger, Luke and Posenato, Roberto}, title = {{Converting Simple Temporal Networks with Uncertainty into Dispatchable Form - Faster}}, booktitle = {30th International Symposium on Temporal Representation and Reasoning (TIME 2023)}, pages = {20:1--20: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.20}, URN = {urn:nbn:de:0030-drops-191104}, doi = {10.4230/LIPIcs.TIME.2023.20}, annote = {Keywords: Temporal constraint networks, contingent durations, dispatchable network} }
Feedback for Dagstuhl Publishing