Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Ziyi Guan, Yunqi Huang, Penghui Yao, and Zekun Ye. Quantum and Classical Communication Complexity of Permutation-Invariant Functions. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{guan_et_al:LIPIcs.STACS.2024.39, author = {Guan, Ziyi and Huang, Yunqi and Yao, Penghui and Ye, Zekun}, title = {{Quantum and Classical Communication Complexity of Permutation-Invariant Functions}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {39:1--39: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.39}, URN = {urn:nbn:de:0030-drops-197498}, doi = {10.4230/LIPIcs.STACS.2024.39}, annote = {Keywords: Communication complexity, Permutation-invariant functions, Log-rank Conjecture, Quantum advantages} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Ohad Klein, Joseph Slote, Alexander Volberg, and Haonan Zhang. Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 69:1-69:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{klein_et_al:LIPIcs.ITCS.2024.69, author = {Klein, Ohad and Slote, Joseph and Volberg, Alexander and Zhang, Haonan}, title = {{Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {69:1--69: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.69}, URN = {urn:nbn:de:0030-drops-195977}, doi = {10.4230/LIPIcs.ITCS.2024.69}, annote = {Keywords: Analysis of Boolean Functions, Remez Inequality, Bohnenblust-Hille Inequality, Statistical Learning Theory, Qudits} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Seok-Hee Hong. Faithful Graph Drawing (Invited Talk). In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hong:LIPIcs.ISAAC.2023.2, author = {Hong, Seok-Hee}, title = {{Faithful Graph Drawing}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {2:1--2:1}, 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.2}, URN = {urn:nbn:de:0030-drops-193044}, doi = {10.4230/LIPIcs.ISAAC.2023.2}, annote = {Keywords: Graph drawing, Planar graphs, Beyond planar graphs, Tutte’s barycenter theorem, Steinitz’s theorem, F\'{a}ry’s theorem, Sublinear-time graph drawing algorithm, Faithful graph drawing, Symmetric graph drawing} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong. Computing a Subtrajectory Cluster from c-Packed Trajectories. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2023.34, author = {Gudmundsson, Joachim and Huang, Zijin and van Renssen, Andr\'{e} and Wong, Sampson}, title = {{Computing a Subtrajectory Cluster from c-Packed Trajectories}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {34:1--34:15}, 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.34}, URN = {urn:nbn:de:0030-drops-193364}, doi = {10.4230/LIPIcs.ISAAC.2023.34}, annote = {Keywords: Subtrajectory cluster, c-packed trajectories, Computational geometry} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Shimon Kogan and Merav Parter. Towards Bypassing Lower Bounds for Graph Shortcuts. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kogan_et_al:LIPIcs.ESA.2023.73, author = {Kogan, Shimon and Parter, Merav}, title = {{Towards Bypassing Lower Bounds for Graph Shortcuts}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {73:1--73:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.73}, URN = {urn:nbn:de:0030-drops-187264}, doi = {10.4230/LIPIcs.ESA.2023.73}, annote = {Keywords: Directed Shortcuts, Hopsets, Emulators} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
François Sellier. Parameterized Matroid-Constrained Maximum Coverage. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 94:1-94:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{sellier:LIPIcs.ESA.2023.94, author = {Sellier, Fran\c{c}ois}, title = {{Parameterized Matroid-Constrained Maximum Coverage}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {94:1--94:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.94}, URN = {urn:nbn:de:0030-drops-187475}, doi = {10.4230/LIPIcs.ESA.2023.94}, annote = {Keywords: Matroids, approximate kernel, maximum coverage} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Niklas Hahn and Michalis Xefteris. The Covering Canadian Traveller Problem Revisited. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 53:1-53:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hahn_et_al:LIPIcs.MFCS.2023.53, author = {Hahn, Niklas and Xefteris, Michalis}, title = {{The Covering Canadian Traveller Problem Revisited}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {53:1--53:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.53}, URN = {urn:nbn:de:0030-drops-185876}, doi = {10.4230/LIPIcs.MFCS.2023.53}, annote = {Keywords: Online Algorithm, Canadian Traveller Problem, Travelling Salesperson Problem, Graph Exploration} }
Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)
Anshujit Sharma, Matthew Burns, and Michael C. Huang. Combining Cubic Dynamical Solvers with Make/Break Heuristics to Solve SAT. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 25:1-25:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{sharma_et_al:LIPIcs.SAT.2023.25, author = {Sharma, Anshujit and Burns, Matthew and Huang, Michael C.}, title = {{Combining Cubic Dynamical Solvers with Make/Break Heuristics to Solve SAT}}, booktitle = {26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)}, pages = {25:1--25:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-286-0}, ISSN = {1868-8969}, year = {2023}, volume = {271}, editor = {Mahajan, Meena and Slivovsky, Friedrich}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.25}, URN = {urn:nbn:de:0030-drops-184871}, doi = {10.4230/LIPIcs.SAT.2023.25}, annote = {Keywords: Satisfiability, Ising machines, Stochastic Heuristics, Natural Computation} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. On the Power of Nonstandard Quantum Oracles. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bassirian_et_al:LIPIcs.TQC.2023.11, author = {Bassirian, Roozbeh and Fefferman, Bill and Marwaha, Kunal}, title = {{On the Power of Nonstandard Quantum Oracles}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {11:1--11:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-283-9}, ISSN = {1868-8969}, year = {2023}, volume = {266}, editor = {Fawzi, Omar and Walter, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.11}, URN = {urn:nbn:de:0030-drops-183215}, doi = {10.4230/LIPIcs.TQC.2023.11}, annote = {Keywords: quantum complexity, QCMA, expander graphs, representation theory} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Siu-Wing Cheng and Haoqiang Huang. Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cheng_et_al:LIPIcs.ICALP.2023.40, author = {Cheng, Siu-Wing and Huang, Haoqiang}, title = {{Approximate Nearest Neighbor for Polygonal Curves Under Fr\'{e}chet Distance}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {40:1--40:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.40}, URN = {urn:nbn:de:0030-drops-180929}, doi = {10.4230/LIPIcs.ICALP.2023.40}, annote = {Keywords: Polygonal curves, Fr\'{e}chet distance, approximate nearest neighbor} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{doronarad_et_al:LIPIcs.ICALP.2023.49, author = {Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas}, title = {{An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {49:1--49:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.49}, URN = {urn:nbn:de:0030-drops-181018}, doi = {10.4230/LIPIcs.ICALP.2023.49}, annote = {Keywords: budgeted matching, budgeted matroid intersection, efficient polynomial-time approximation scheme} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sayan Bandyapadhyay, Fedor V. Fomin, and Tanmay Inamdar. Coresets for Clustering in Geometric Intersection Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.10, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Inamdar, Tanmay}, title = {{Coresets for Clustering in Geometric Intersection Graphs}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.10}, URN = {urn:nbn:de:0030-drops-178605}, doi = {10.4230/LIPIcs.SoCG.2023.10}, annote = {Keywords: k-median, k-means, clustering, coresets, geometric graphs} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Timothy M. Chan and Zhengcheng Huang. Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chan_et_al:LIPIcs.SoCG.2023.23, author = {Chan, Timothy M. and Huang, Zhengcheng}, title = {{Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {23:1--23:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.23}, URN = {urn:nbn:de:0030-drops-178738}, doi = {10.4230/LIPIcs.SoCG.2023.23}, annote = {Keywords: Hop spanners, geometric intersection graphs, string graphs, fat objects, separators, shallow cuttings} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Shengyu Huang, Chih-Hung Liu, and Daniel Rutschmann. Approximate Selection with Unreliable Comparisons in Optimal Expected Time. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{huang_et_al:LIPIcs.STACS.2023.37, author = {Huang, Shengyu and Liu, Chih-Hung and Rutschmann, Daniel}, title = {{Approximate Selection with Unreliable Comparisons in Optimal Expected Time}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {37:1--37:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.37}, URN = {urn:nbn:de:0030-drops-176898}, doi = {10.4230/LIPIcs.STACS.2023.37}, annote = {Keywords: Approximate Selection, Unreliable Comparisons, Independent Faults} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Yaonan Jin, Pinyan Lu, and Tao Xiao. Learning Reserve Prices in Second-Price Auctions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 75:1-75:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{jin_et_al:LIPIcs.ITCS.2023.75, author = {Jin, Yaonan and Lu, Pinyan and Xiao, Tao}, title = {{Learning Reserve Prices in Second-Price Auctions}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {75:1--75:24}, 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.75}, URN = {urn:nbn:de:0030-drops-175780}, doi = {10.4230/LIPIcs.ITCS.2023.75}, annote = {Keywords: Revenue Maximization, Sample Complexity, Anonymous Reserve} }
Feedback for Dagstuhl Publishing