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.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)
Yanlin Chen and Ronald de Wolf. Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 38:1-38:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ICALP.2023.38, author = {Chen, Yanlin and de Wolf, Ronald}, title = {{Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {38:1--38:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.38}, URN = {urn:nbn:de:0030-drops-180907}, doi = {10.4230/LIPIcs.ICALP.2023.38}, annote = {Keywords: Quantum algorithms, Regularized linear regression, Lasso, Ridge, Lower bounds} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Sandra Kiefer and Daniel Neuen. A Study of Weisfeiler-Leman Colorings on Planar Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 81:1-81:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kiefer_et_al:LIPIcs.ICALP.2022.81, author = {Kiefer, Sandra and Neuen, Daniel}, title = {{A Study of Weisfeiler-Leman Colorings on Planar Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {81:1--81:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.81}, URN = {urn:nbn:de:0030-drops-164228}, doi = {10.4230/LIPIcs.ICALP.2022.81}, annote = {Keywords: Weisfeiler-Leman algorithm, planar graphs, edge-transitive graphs, fixing number} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Yi Li and David P. Woodruff. The Product of Gaussian Matrices Is Close to Gaussian. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 35:1-35:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{li_et_al:LIPIcs.APPROX/RANDOM.2021.35, author = {Li, Yi and Woodruff, David P.}, title = {{The Product of Gaussian Matrices Is Close to Gaussian}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {35:1--35:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.35}, URN = {urn:nbn:de:0030-drops-147281}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.35}, annote = {Keywords: random matrix theory, total variation distance, matrix product} }
Published in: LIPIcs, Volume 166, 34th European Conference on Object-Oriented Programming (ECOOP 2020)
Liyi Li and Elsa L. Gunter. K-LLVM: A Relatively Complete Semantics of LLVM IR. In 34th European Conference on Object-Oriented Programming (ECOOP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 166, pp. 7:1-7:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{li_et_al:LIPIcs.ECOOP.2020.7, author = {Li, Liyi and Gunter, Elsa L.}, title = {{K-LLVM: A Relatively Complete Semantics of LLVM IR}}, booktitle = {34th European Conference on Object-Oriented Programming (ECOOP 2020)}, pages = {7:1--7:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-154-2}, ISSN = {1868-8969}, year = {2020}, volume = {166}, editor = {Hirschfeld, Robert and Pape, Tobias}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2020.7}, URN = {urn:nbn:de:0030-drops-131649}, doi = {10.4230/LIPIcs.ECOOP.2020.7}, annote = {Keywords: LLVM, formal semantics, K framework, memory model, abstract machine} }
Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)
Yu Chen and Ke Yi. Random Sampling and Size Estimation Over Cyclic Joins. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 7:1-7:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chen_et_al:LIPIcs.ICDT.2020.7, author = {Chen, Yu and Yi, Ke}, title = {{Random Sampling and Size Estimation Over Cyclic Joins}}, booktitle = {23rd International Conference on Database Theory (ICDT 2020)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-139-9}, ISSN = {1868-8969}, year = {2020}, volume = {155}, editor = {Lutz, Carsten and Jung, Jean Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.7}, URN = {urn:nbn:de:0030-drops-119315}, doi = {10.4230/LIPIcs.ICDT.2020.7}, annote = {Keywords: Random sampling, joins, join size estimation} }
Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)
Xiaohong Chen and Grigore Roşu. Matching mu-Logic: Foundation of K Framework (Invited Paper). In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 1:1-1:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.CALCO.2019.1, author = {Chen, Xiaohong and Ro\c{s}u, Grigore}, title = {{Matching mu-Logic: Foundation of K Framework}}, booktitle = {8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)}, pages = {1:1--1:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-120-7}, ISSN = {1868-8969}, year = {2019}, volume = {139}, editor = {Roggenbach, Markus and Sokolova, Ana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.1}, URN = {urn:nbn:de:0030-drops-114296}, doi = {10.4230/LIPIcs.CALCO.2019.1}, annote = {Keywords: Matching mu-logic, Program verification, Reachability logic} }
Published in: LIPIcs, Volume 141, 10th International Conference on Interactive Theorem Proving (ITP 2019)
Johannes Åman Pohjola, Henrik Rostedt, and Magnus O. Myreen. Characteristic Formulae for Liveness Properties of Non-Terminating CakeML Programs. In 10th International Conference on Interactive Theorem Proving (ITP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 141, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{amanpohjola_et_al:LIPIcs.ITP.2019.32, author = {\r{A}man Pohjola, Johannes and Rostedt, Henrik and Myreen, Magnus O.}, title = {{Characteristic Formulae for Liveness Properties of Non-Terminating CakeML Programs}}, booktitle = {10th International Conference on Interactive Theorem Proving (ITP 2019)}, pages = {32:1--32:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-122-1}, ISSN = {1868-8969}, year = {2019}, volume = {141}, editor = {Harrison, John and O'Leary, John and Tolmach, Andrew}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2019.32}, URN = {urn:nbn:de:0030-drops-110872}, doi = {10.4230/LIPIcs.ITP.2019.32}, annote = {Keywords: Program verification, non-termination, liveness, Hoare logic} }
Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Natalie Sauerwald, Yihang Shen, and Carl Kingsford. Topological Data Analysis Reveals Principles of Chromosome Structure in Cellular Differentiation. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{sauerwald_et_al:LIPIcs.WABI.2019.23, author = {Sauerwald, Natalie and Shen, Yihang and Kingsford, Carl}, title = {{Topological Data Analysis Reveals Principles of Chromosome Structure in Cellular Differentiation}}, booktitle = {19th International Workshop on Algorithms in Bioinformatics (WABI 2019)}, pages = {23:1--23:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-123-8}, ISSN = {1868-8969}, year = {2019}, volume = {143}, editor = {Huber, Katharina T. and Gusfield, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.23}, URN = {urn:nbn:de:0030-drops-110537}, doi = {10.4230/LIPIcs.WABI.2019.23}, annote = {Keywords: topological data analysis, chromosome structure, Hi-C, topologically associating domains} }
Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Jie Liu, Yuanhao Huang, Ritambhara Singh, Jean-Philippe Vert, and William Stafford Noble. Jointly Embedding Multiple Single-Cell Omics Measurements. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{liu_et_al:LIPIcs.WABI.2019.10, author = {Liu, Jie and Huang, Yuanhao and Singh, Ritambhara and Vert, Jean-Philippe and Noble, William Stafford}, title = {{Jointly Embedding Multiple Single-Cell Omics Measurements}}, booktitle = {19th International Workshop on Algorithms in Bioinformatics (WABI 2019)}, pages = {10:1--10:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-123-8}, ISSN = {1868-8969}, year = {2019}, volume = {143}, editor = {Huber, Katharina T. and Gusfield, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.10}, URN = {urn:nbn:de:0030-drops-110401}, doi = {10.4230/LIPIcs.WABI.2019.10}, annote = {Keywords: Manifold alignment, single-cell sequencing} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Andrei A. Bulatov and Stanislav Živný. Approximate Counting CSP Seen from the Other Side. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bulatov_et_al:LIPIcs.MFCS.2019.60, author = {Bulatov, Andrei A. and \v{Z}ivn\'{y}, Stanislav}, title = {{Approximate Counting CSP Seen from the Other Side}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {60:1--60:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.60}, URN = {urn:nbn:de:0030-drops-110041}, doi = {10.4230/LIPIcs.MFCS.2019.60}, annote = {Keywords: constraint satisfaction, approximate counting, homomorphisms} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, and Przemysław Uznański. RLE Edit Distance in Near Optimal Time. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 66:1-66:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{clifford_et_al:LIPIcs.MFCS.2019.66, author = {Clifford, Rapha\"{e}l and Gawrychowski, Pawe{\l} and Kociumaka, Tomasz and Martin, Daniel P. and Uzna\'{n}ski, Przemys{\l}aw}, title = {{RLE Edit Distance in Near Optimal Time}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {66:1--66:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.66}, URN = {urn:nbn:de:0030-drops-110109}, doi = {10.4230/LIPIcs.MFCS.2019.66}, annote = {Keywords: String algorithms, Compression, Pattern matching, Run-length encoding} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Sandra Kiefer and Daniel Neuen. The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kiefer_et_al:LIPIcs.MFCS.2019.45, author = {Kiefer, Sandra and Neuen, Daniel}, title = {{The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {45:1--45:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.45}, URN = {urn:nbn:de:0030-drops-109893}, doi = {10.4230/LIPIcs.MFCS.2019.45}, annote = {Keywords: Weisfeiler-Leman, separators, first-order logic, counting quantifiers} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Amirhossein Kazeminia and Andrei A. Bulatov. Counting Homomorphisms Modulo a Prime Number. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kazeminia_et_al:LIPIcs.MFCS.2019.59, author = {Kazeminia, Amirhossein and Bulatov, Andrei A.}, title = {{Counting Homomorphisms Modulo a Prime Number}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {59:1--59:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.59}, URN = {urn:nbn:de:0030-drops-110032}, doi = {10.4230/LIPIcs.MFCS.2019.59}, annote = {Keywords: graph homomorphism, modular counting, computational hardness} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.CCC.2019.30, author = {Chen, Lijie and McKay, Dylan M. and Murray, Cody D. and Williams, R. Ryan}, title = {{Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {30:1--30:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.30}, URN = {urn:nbn:de:0030-drops-108525}, doi = {10.4230/LIPIcs.CCC.2019.30}, annote = {Keywords: Karp-Lipton Theorems, Circuit Lower Bounds, Derandomization, Hardness Magnification} }
Feedback for Dagstuhl Publishing