LIPIcs, Volume 186
ICDT 2021, March 23-26, 2021, Nicosia, Cyprus
Editors: Ke Yi and Zhewei Wei
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Edward Pyne. Derandomizing Logspace with a Small Shared Hard Drive. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{pyne:LIPIcs.CCC.2024.4, author = {Pyne, Edward}, title = {{Derandomizing Logspace with a Small Shared Hard Drive}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {4:1--4:20}, 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.4}, URN = {urn:nbn:de:0030-drops-204006}, doi = {10.4230/LIPIcs.CCC.2024.4}, annote = {Keywords: Catalytic computation, space-bounded computation, derandomization} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7, author = {Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik}, title = {{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {7:1--7: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.7}, URN = {urn:nbn:de:0030-drops-204035}, doi = {10.4230/LIPIcs.CCC.2024.7}, annote = {Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Justin Holmgren and Ron Rothblum. Linear-Size Boolean Circuits for Multiselection. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{holmgren_et_al:LIPIcs.CCC.2024.11, author = {Holmgren, Justin and Rothblum, Ron}, title = {{Linear-Size Boolean Circuits for Multiselection}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {11:1--11:20}, 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.11}, URN = {urn:nbn:de:0030-drops-204070}, doi = {10.4230/LIPIcs.CCC.2024.11}, annote = {Keywords: Private Information Retrieval, Batch Selection, Boolean Circuits} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Noel Arteche, Gaia Carenini, and Matthew Gray. Quantum Automating TC⁰-Frege Is LWE-Hard. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 15:1-15:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arteche_et_al:LIPIcs.CCC.2024.15, author = {Arteche, Noel and Carenini, Gaia and Gray, Matthew}, title = {{Quantum Automating TC⁰-Frege Is LWE-Hard}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {15:1--15:25}, 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.15}, URN = {urn:nbn:de:0030-drops-204117}, doi = {10.4230/LIPIcs.CCC.2024.15}, annote = {Keywords: automatability, post-quantum cryptography, feasible interpolation} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Kuan Cheng and Yichuan Wang. BPL ⊆ L-AC¹. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cheng_et_al:LIPIcs.CCC.2024.32, author = {Cheng, Kuan and Wang, Yichuan}, title = {{BPL ⊆ L-AC¹}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {32:1--32:14}, 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.32}, URN = {urn:nbn:de:0030-drops-204282}, doi = {10.4230/LIPIcs.CCC.2024.32}, annote = {Keywords: Randomized Space Complexity, Circuit Complexity, Derandomization} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Adil Chhabra, Marcelo Fonseca Faraj, Christian Schulz, and Daniel Seemaier. Buffered Streaming Edge Partitioning. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chhabra_et_al:LIPIcs.SEA.2024.5, author = {Chhabra, Adil and Fonseca Faraj, Marcelo and Schulz, Christian and Seemaier, Daniel}, title = {{Buffered Streaming Edge Partitioning}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {5:1--5:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.5}, URN = {urn:nbn:de:0030-drops-203701}, doi = {10.4230/LIPIcs.SEA.2024.5}, annote = {Keywords: graph partitioning, edge partitioning, streaming, online, buffered partitioning} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Theo Conrads, Lukas Drexler, Joshua Könen, Daniel R. Schmidt, and Melanie Schmidt. Local Search k-means++ with Foresight. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{conrads_et_al:LIPIcs.SEA.2024.7, author = {Conrads, Theo and Drexler, Lukas and K\"{o}nen, Joshua and Schmidt, Daniel R. and Schmidt, Melanie}, title = {{Local Search k-means++ with Foresight}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {7:1--7:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.7}, URN = {urn:nbn:de:0030-drops-203727}, doi = {10.4230/LIPIcs.SEA.2024.7}, annote = {Keywords: k-means clustering, kmeans++, greedy, local search} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Patrick Dinklage, Johnnes Fischer, and Nicola Prezza. Top- k Frequent Patterns in Streams and Parameterized-Space LZ Compression. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dinklage_et_al:LIPIcs.SEA.2024.9, author = {Dinklage, Patrick and Fischer, Johnnes and Prezza, Nicola}, title = {{Top- k Frequent Patterns in Streams and Parameterized-Space LZ Compression}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {9:1--9:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.9}, URN = {urn:nbn:de:0030-drops-203748}, doi = {10.4230/LIPIcs.SEA.2024.9}, annote = {Keywords: compression, streaming, heavy hitters, algorithm engineering} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Deborah Hendrych, Mathieu Besançon, and Sebastian Pokutta. Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hendrych_et_al:LIPIcs.SEA.2024.16, author = {Hendrych, Deborah and Besan\c{c}on, Mathieu and Pokutta, Sebastian}, title = {{Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {16:1--16:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.16}, URN = {urn:nbn:de:0030-drops-203810}, doi = {10.4230/LIPIcs.SEA.2024.16}, annote = {Keywords: Mixed-Integer Non-Linear Optimization, Optimal Experiment Design, Frank-Wolfe, Boscia} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Jakub Komárek and Martin Koutecký. Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{komarek_et_al:LIPIcs.SEA.2024.18, author = {Kom\'{a}rek, Jakub and Kouteck\'{y}, Martin}, title = {{Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {18:1--18:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.18}, URN = {urn:nbn:de:0030-drops-203832}, doi = {10.4230/LIPIcs.SEA.2024.18}, annote = {Keywords: Linear programming, scaling, circuit imbalance measure} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Kenneth Langedal, Demian Hespe, and Peter Sanders. Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{langedal_et_al:LIPIcs.SEA.2024.20, author = {Langedal, Kenneth and Hespe, Demian and Sanders, Peter}, title = {{Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {20:1--20:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.20}, URN = {urn:nbn:de:0030-drops-203853}, doi = {10.4230/LIPIcs.SEA.2024.20}, annote = {Keywords: Graphs, Independent Set, Vertex Cover, Graph Neural Networks, Branch-and-Reduce} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
Sohei Ito and Makoto Tatsuta. Representation of Peano Arithmetic in Separation Logic. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ito_et_al:LIPIcs.FSCD.2024.18, author = {Ito, Sohei and Tatsuta, Makoto}, title = {{Representation of Peano Arithmetic in Separation Logic}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {18:1--18:17}, 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.18}, URN = {urn:nbn:de:0030-drops-203476}, doi = {10.4230/LIPIcs.FSCD.2024.18}, annote = {Keywords: First order logic, Separation logic, Peano arithmetic, Presburger arithmetic} }
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 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)
Anam Farrukh and Richard West. JuMP2start: Time-Aware Stop-Start Technology for a Software-Defined Vehicle System. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 1:1-1:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{farrukh_et_al:LIPIcs.ECRTS.2024.1, author = {Farrukh, Anam and West, Richard}, title = {{JuMP2start: Time-Aware Stop-Start Technology for a Software-Defined Vehicle System}}, booktitle = {36th Euromicro Conference on Real-Time Systems (ECRTS 2024)}, pages = {1:1--1:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-324-9}, ISSN = {1868-8969}, year = {2024}, volume = {298}, editor = {Pellizzoni, Rodolfo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.1}, URN = {urn:nbn:de:0030-drops-203046}, doi = {10.4230/LIPIcs.ECRTS.2024.1}, annote = {Keywords: Time-aware stop-start, Real-time power management, Suspend-to-RAM, Partitioning hypervisor, Vehicle management system, Vehicle-OS, Software-defined vehicles (SDV)} }