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)
Graham Cormode, Marcel Dall'Agnol, Tom Gur, and Chris Hickey. Streaming Zero-Knowledge Proofs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 2:1-2:66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cormode_et_al:LIPIcs.CCC.2024.2, author = {Cormode, Graham and Dall'Agnol, Marcel and Gur, Tom and Hickey, Chris}, title = {{Streaming Zero-Knowledge Proofs}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {2:1--2:66}, 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.2}, URN = {urn:nbn:de:0030-drops-203988}, doi = {10.4230/LIPIcs.CCC.2024.2}, annote = {Keywords: Zero-knowledge proofs, streaming algorithms, computational complexity} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Noam Mazor and Rafael Pass. Gap MCSP Is Not (Levin) NP-Complete in Obfustopia. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mazor_et_al:LIPIcs.CCC.2024.36, author = {Mazor, Noam and Pass, Rafael}, title = {{Gap MCSP Is Not (Levin) NP-Complete in Obfustopia}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {36:1--36:21}, 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.36}, URN = {urn:nbn:de:0030-drops-204322}, doi = {10.4230/LIPIcs.CCC.2024.36}, annote = {Keywords: Kolmogorov complexity, MCSP, Levin Reduction} }
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 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)} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Ziyue Huang and Ke Yi. Approximate Range Counting Under Differential Privacy. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{huang_et_al:LIPIcs.SoCG.2021.45, author = {Huang, Ziyue and Yi, Ke}, title = {{Approximate Range Counting Under Differential Privacy}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {45:1--45:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.45}, URN = {urn:nbn:de:0030-drops-138441}, doi = {10.4230/LIPIcs.SoCG.2021.45}, annote = {Keywords: Differential Privacy, Approximate Range Counting} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 1-438, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Proceedings{yi_et_al:LIPIcs.ICDT.2021, title = {{LIPIcs, Volume 186, ICDT 2021, Complete Volume}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {1--438}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021}, URN = {urn:nbn:de:0030-drops-137076}, doi = {10.4230/LIPIcs.ICDT.2021}, annote = {Keywords: LIPIcs, Volume 186, ICDT 2021, Complete Volume} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{yi_et_al:LIPIcs.ICDT.2021.0, author = {Yi, Ke and Wei, Zhewei}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.0}, URN = {urn:nbn:de:0030-drops-137086}, doi = {10.4230/LIPIcs.ICDT.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Pablo Barceló. Explainability Queries for ML Models and its Connections with Data Management Problems (Invited Talk). In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{barcelo:LIPIcs.ICDT.2021.1, author = {Barcel\'{o}, Pablo}, title = {{Explainability Queries for ML Models and its Connections with Data Management Problems}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.1}, URN = {urn:nbn:de:0030-drops-137091}, doi = {10.4230/LIPIcs.ICDT.2021.1}, annote = {Keywords: ML models, Explainability, Shapley values, decision trees, OBDDs, deterministic and decomposable Boolean circuits} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Julia Stoyanovich. Comparing Apples and Oranges: Fairness and Diversity in Ranking (Invited Talk). In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{stoyanovich:LIPIcs.ICDT.2021.2, author = {Stoyanovich, Julia}, title = {{Comparing Apples and Oranges: Fairness and Diversity in Ranking}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.2}, URN = {urn:nbn:de:0030-drops-137104}, doi = {10.4230/LIPIcs.ICDT.2021.2}, annote = {Keywords: fairness, diversity, ranking, set selection, responsible data management} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Kaleb Alway, Eric Blais, and Semih Salihoglu. Box Covers and Domain Orderings for Beyond Worst-Case Join Processing. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{alway_et_al:LIPIcs.ICDT.2021.3, author = {Alway, Kaleb and Blais, Eric and Salihoglu, Semih}, title = {{Box Covers and Domain Orderings for Beyond Worst-Case Join Processing}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {3:1--3:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.3}, URN = {urn:nbn:de:0030-drops-137114}, doi = {10.4230/LIPIcs.ICDT.2021.3}, annote = {Keywords: Beyond worst-case join algorithms, Tetris, Box covers, Domain orderings} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Markus L. Schmid and Nicole Schweikardt. A Purely Regular Approach to Non-Regular Core Spanners. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{schmid_et_al:LIPIcs.ICDT.2021.4, author = {Schmid, Markus L. and Schweikardt, Nicole}, title = {{A Purely Regular Approach to Non-Regular Core Spanners}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.4}, URN = {urn:nbn:de:0030-drops-137124}, doi = {10.4230/LIPIcs.ICDT.2021.4}, annote = {Keywords: Document spanners, regular expressions with backreferences} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Shaleen Deep and Paraschos Koutris. Ranked Enumeration of Conjunctive Query Results. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{deep_et_al:LIPIcs.ICDT.2021.5, author = {Deep, Shaleen and Koutris, Paraschos}, title = {{Ranked Enumeration of Conjunctive Query Results}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {5:1--5:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.5}, URN = {urn:nbn:de:0030-drops-137139}, doi = {10.4230/LIPIcs.ICDT.2021.5}, annote = {Keywords: Query result enumeration, joins, ranking} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Shangqi Lu and Yufei Tao. Towards Optimal Dynamic Indexes for Approximate (and Exact) Triangle Counting. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{lu_et_al:LIPIcs.ICDT.2021.6, author = {Lu, Shangqi and Tao, Yufei}, title = {{Towards Optimal Dynamic Indexes for Approximate (and Exact) Triangle Counting}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {6:1--6:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.6}, URN = {urn:nbn:de:0030-drops-137146}, doi = {10.4230/LIPIcs.ICDT.2021.6}, annote = {Keywords: Triangle Counting, Data Structures, Lower Bounds, Graph Algorithms} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Liat Peterfreund. Grammars for Document Spanners. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{peterfreund:LIPIcs.ICDT.2021.7, author = {Peterfreund, Liat}, title = {{Grammars for Document Spanners}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.7}, URN = {urn:nbn:de:0030-drops-137154}, doi = {10.4230/LIPIcs.ICDT.2021.7}, annote = {Keywords: Information Extraction, Document Spanners, Context-Free Grammars, Constant-Delay Enumeration, Regular Expressions, Pushdown Automata} }