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)
Scott Aaronson, Harry Buhrman, and William Kretschmer. A Qubit, a Coin, and an Advice String Walk into a Relational Problem. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.ITCS.2024.1, author = {Aaronson, Scott and Buhrman, Harry and Kretschmer, William}, title = {{A Qubit, a Coin, and an Advice String Walk into a Relational Problem}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {1:1--1:24}, 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.1}, URN = {urn:nbn:de:0030-drops-195290}, doi = {10.4230/LIPIcs.ITCS.2024.1}, annote = {Keywords: Relational problems, quantum advice, randomized advice, FBQP, FBPP} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Rafael Frongillo, Maneesha Papireddygari, and Bo Waggoner. An Axiomatic Characterization of CFMMs and Equivalence to Prediction Markets. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{frongillo_et_al:LIPIcs.ITCS.2024.51, author = {Frongillo, Rafael and Papireddygari, Maneesha and Waggoner, Bo}, title = {{An Axiomatic Characterization of CFMMs and Equivalence to Prediction Markets}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {51:1--51: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.51}, URN = {urn:nbn:de:0030-drops-195795}, doi = {10.4230/LIPIcs.ITCS.2024.51}, annote = {Keywords: Convex analysis, Equivalence result, Axiomatic characterization, Market Makers, Prediction markets, Scoring rules, Cost-functions} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Supartha Podder, Penghui Yao, and Zekun Ye. On the Fine-Grained Query Complexity of Symmetric Functions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{podder_et_al:LIPIcs.ISAAC.2023.55, author = {Podder, Supartha and Yao, Penghui and Ye, Zekun}, title = {{On the Fine-Grained Query Complexity of Symmetric Functions}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {55:1--55:18}, 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.55}, URN = {urn:nbn:de:0030-drops-193570}, doi = {10.4230/LIPIcs.ISAAC.2023.55}, annote = {Keywords: Query complexity, Symmetric functions, Quantum advantages} }
Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi. Twins: BFT Systems Made Robust. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 7:1-7:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bano_et_al:LIPIcs.OPODIS.2021.7, author = {Bano, Shehar and Sonnino, Alberto and Chursin, Andrey and Perelman, Dmitri and Li, Zekun and Ching, Avery and Malkhi, Dahlia}, title = {{Twins: BFT Systems Made Robust}}, booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)}, pages = {7:1--7:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-219-8}, ISSN = {1868-8969}, year = {2022}, volume = {217}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.7}, URN = {urn:nbn:de:0030-drops-157825}, doi = {10.4230/LIPIcs.OPODIS.2021.7}, annote = {Keywords: Distributed Systems, Byzantine Fault Tolerance, Real-World Deployment} }
Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II
Jamie Scott, Kristin Stock, Fraser Morgan, Brandon Whitehead, and David Medyckyj-Scott. Automated Georeferencing of Antarctic Species. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{scott_et_al:LIPIcs.GIScience.2021.II.13, author = {Scott, Jamie and Stock, Kristin and Morgan, Fraser and Whitehead, Brandon and Medyckyj-Scott, David}, title = {{Automated Georeferencing of Antarctic Species}}, booktitle = {11th International Conference on Geographic Information Science (GIScience 2021) - Part II}, pages = {13:1--13:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-208-2}, ISSN = {1868-8969}, year = {2021}, volume = {208}, editor = {Janowicz, Krzysztof and Verstegen, Judith A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.13}, URN = {urn:nbn:de:0030-drops-147726}, doi = {10.4230/LIPIcs.GIScience.2021.II.13}, annote = {Keywords: Named Entity Recognition (NER), Taxonomic Name Extraction, Relation Extraction, Georeferencing} }
Published in: LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021)
David Furcy, Scott M. Summers, and Logan Withers. Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{furcy_et_al:LIPIcs.DNA.27.4, author = {Furcy, David and Summers, Scott M. and Withers, Logan}, title = {{Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D}}, booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)}, pages = {4:1--4:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-205-1}, ISSN = {1868-8969}, year = {2021}, volume = {205}, editor = {Lakin, Matthew R. and \v{S}ulc, Petr}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.4}, URN = {urn:nbn:de:0030-drops-146716}, doi = {10.4230/LIPIcs.DNA.27.4}, annote = {Keywords: Self-assembly, algorithmic self-assembly, tile self-assembly} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hoza:LIPIcs.CCC.2019.9, author = {Hoza, William M.}, title = {{Typically-Correct Derandomization for Small Time and Space}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {9:1--9:39}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.9}, URN = {urn:nbn:de:0030-drops-108317}, doi = {10.4230/LIPIcs.CCC.2019.9}, annote = {Keywords: Derandomization, pseudorandomness, space complexity} }
Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Shalev Ben-David and Robin Kothari. Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bendavid_et_al:LIPIcs.TQC.2019.2, author = {Ben-David, Shalev and Kothari, Robin}, title = {{Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {2:1--2:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-112-2}, ISSN = {1868-8969}, year = {2019}, volume = {135}, editor = {van Dam, Wim and Man\v{c}inska, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.2}, URN = {urn:nbn:de:0030-drops-103944}, doi = {10.4230/LIPIcs.TQC.2019.2}, annote = {Keywords: Quantum query complexity, quantum algorithms} }
Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
David Gosset and John Smolin. A Compressed Classical Description of Quantum States. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 8:1-8:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gosset_et_al:LIPIcs.TQC.2019.8, author = {Gosset, David and Smolin, John}, title = {{A Compressed Classical Description of Quantum States}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {8:1--8:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-112-2}, ISSN = {1868-8969}, year = {2019}, volume = {135}, editor = {van Dam, Wim and Man\v{c}inska, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.8}, URN = {urn:nbn:de:0030-drops-104005}, doi = {10.4230/LIPIcs.TQC.2019.8}, annote = {Keywords: Quantum computation, Quantum communication complexity, Classical simulation} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Scott Aaronson and Shalev Ben-David. Sculpting Quantum Speedups. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 26:1-26:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2016.26, author = {Aaronson, Scott and Ben-David, Shalev}, title = {{Sculpting Quantum Speedups}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {26:1--26:28}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.26}, URN = {urn:nbn:de:0030-drops-58538}, doi = {10.4230/LIPIcs.CCC.2016.26}, annote = {Keywords: Quantum Computing, Query Complexity, Decision Tree Complexity, Structural Complexity} }
Published in: OASIcs, Volume 41, 2014 Workshop on Computational Models of Narrative
James Niehaus, Victoria Romero, David Koelle, Noa Palmon, Bethany Bracken, Jonathan Pfautz, Scott Neal Reilly, and Peter Weyhrauch. A Flexible Framework for the Creation of Narrative-Centered Tools. In 2014 Workshop on Computational Models of Narrative. Open Access Series in Informatics (OASIcs), Volume 41, pp. 130-138, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{niehaus_et_al:OASIcs.CMN.2014.130, author = {Niehaus, James and Romero, Victoria and Koelle, David and Palmon, Noa and Bracken, Bethany and Pfautz, Jonathan and Reilly, Scott Neal and Weyhrauch, Peter}, title = {{A Flexible Framework for the Creation of Narrative-Centered Tools}}, booktitle = {2014 Workshop on Computational Models of Narrative}, pages = {130--138}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-71-2}, ISSN = {2190-6807}, year = {2014}, volume = {41}, editor = {Finlayson, Mark A. and Meister, Jan Christoph and Bruneau, Emile G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2014.130}, URN = {urn:nbn:de:0030-drops-46511}, doi = {10.4230/OASIcs.CMN.2014.130}, annote = {Keywords: computational narrative, narrative analysis framework, narrative ontology, narrative models} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods. Intrinsic Universality in Self-Assembly. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 275-286, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{doty_et_al:LIPIcs.STACS.2010.2461, author = {Doty, David and Lutz, Jack H. and Patitz, Matthew J. and Summers, Scott M. and Woods, Damien}, title = {{Intrinsic Universality in Self-Assembly}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {275--286}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2461}, URN = {urn:nbn:de:0030-drops-24619}, doi = {10.4230/LIPIcs.STACS.2010.2461}, annote = {Keywords: Biological computing, Molecular computation, intrinsic universality, self-assembly} }
Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)
George Labahn, Scott MacLean, Marzouk Mirette, Ian Rutherford, and David Tausky. MathBrush: An Experimental Pen-Based Math System. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{labahn_et_al:DagSemProc.06271.11, author = {Labahn, George and MacLean, Scott and Marzouk Mirette and Rutherford, Ian and Tausky, David}, title = {{MathBrush: An Experimental Pen-Based Math System}}, booktitle = {Challenges in Symbolic Computation Software}, pages = {1--8}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6271}, editor = {Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.11}, URN = {urn:nbn:de:0030-drops-7733}, doi = {10.4230/DagSemProc.06271.11}, annote = {Keywords: PC Tablets, pen-based devices, computer algebra systems} }
Feedback for Dagstuhl Publishing