Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Quantum Pseudoentanglement. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.ITCS.2024.2, author = {Aaronson, Scott and Bouland, Adam and Fefferman, Bill and Ghosh, Soumik and Vazirani, Umesh and Zhang, Chenyi and Zhou, Zixin}, title = {{Quantum Pseudoentanglement}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {2:1--2: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.2}, URN = {urn:nbn:de:0030-drops-195300}, doi = {10.4230/LIPIcs.ITCS.2024.2}, annote = {Keywords: Quantum computing, Quantum complexity theory, entanglement} }
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 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Arvind V. Mahankali, David P. Woodruff, and Ziyu Zhang. Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 79:1-79:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mahankali_et_al:LIPIcs.ITCS.2024.79, author = {Mahankali, Arvind V. and Woodruff, David P. and Zhang, Ziyu}, title = {{Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {79:1--79:23}, 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.79}, URN = {urn:nbn:de:0030-drops-196078}, doi = {10.4230/LIPIcs.ITCS.2024.79}, annote = {Keywords: Low rank approximation, Sketching algorithms, Tensor decomposition} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Zhao Song, Lichen Zhang, and Ruizhe Zhang. Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 93:1-93:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{song_et_al:LIPIcs.ITCS.2024.93, author = {Song, Zhao and Zhang, Lichen and Zhang, Ruizhe}, title = {{Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {93:1--93:15}, 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.93}, URN = {urn:nbn:de:0030-drops-196212}, doi = {10.4230/LIPIcs.ITCS.2024.93}, annote = {Keywords: Deep learning theory, Nonconvex optimization} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Iddo Tzameret and Lu-Ming Zhang. Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 95:1-95:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{tzameret_et_al:LIPIcs.ITCS.2024.95, author = {Tzameret, Iddo and Zhang, Lu-Ming}, title = {{Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {95:1--95: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.95}, URN = {urn:nbn:de:0030-drops-196234}, doi = {10.4230/LIPIcs.ITCS.2024.95}, annote = {Keywords: Pseudorandomness, Cryptography, Natural Proofs, Nondeterminism, Lower bounds} }
Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
Lewis Tseng and Callie Sardina. Byzantine Consensus in Abstract MAC Layer. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{tseng_et_al:LIPIcs.OPODIS.2023.9, author = {Tseng, Lewis and Sardina, Callie}, title = {{Byzantine Consensus in Abstract MAC Layer}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.9}, URN = {urn:nbn:de:0030-drops-194992}, doi = {10.4230/LIPIcs.OPODIS.2023.9}, annote = {Keywords: Byzantine, Randomized Consensus, Approximate Consensus, Abstract MAC} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang. Distance Queries over Dynamic Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2023.18, author = {Chen, Jingbang and He, Meng and Munro, J. Ian and Peng, Richard and Wu, Kaiyu and Zhang, Daniel J.}, title = {{Distance Queries over Dynamic Interval Graphs}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {18:1--18:19}, 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.18}, URN = {urn:nbn:de:0030-drops-193207}, doi = {10.4230/LIPIcs.ISAAC.2023.18}, annote = {Keywords: interval graph, proper interval graph, intersection graph, geometric intersection graph, distance oracle, distance query, shortest path query, dynamic graph} }
Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)
Haoqian Zhang, Louis-Henri Merino, Ziyan Qu, Mahsa Bastankhah, Vero Estrada-Galiñanes, and Bryan Ford. F3B: A Low-Overhead Blockchain Architecture with Per-Transaction Front-Running Protection. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{zhang_et_al:LIPIcs.AFT.2023.3, author = {Zhang, Haoqian and Merino, Louis-Henri and Qu, Ziyan and Bastankhah, Mahsa and Estrada-Gali\~{n}anes, Vero and Ford, Bryan}, title = {{F3B: A Low-Overhead Blockchain Architecture with Per-Transaction Front-Running Protection}}, booktitle = {5th Conference on Advances in Financial Technologies (AFT 2023)}, pages = {3:1--3:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-303-4}, ISSN = {1868-8969}, year = {2023}, volume = {282}, editor = {Bonneau, Joseph and Weinberg, S. Matthew}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.3}, URN = {urn:nbn:de:0030-drops-191921}, doi = {10.4230/LIPIcs.AFT.2023.3}, annote = {Keywords: Blockchain, DeFi, Front-running Mitigation} }
Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)
Andrea Canidio and Robin Fritsch. Batching Trades on Automated Market Makers. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{canidio_et_al:LIPIcs.AFT.2023.24, author = {Canidio, Andrea and Fritsch, Robin}, title = {{Batching Trades on Automated Market Makers}}, booktitle = {5th Conference on Advances in Financial Technologies (AFT 2023)}, pages = {24:1--24:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-303-4}, ISSN = {1868-8969}, year = {2023}, volume = {282}, editor = {Bonneau, Joseph and Weinberg, S. Matthew}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.24}, URN = {urn:nbn:de:0030-drops-192139}, doi = {10.4230/LIPIcs.AFT.2023.24}, annote = {Keywords: Arbitrage profits, Loss-vs-Rebalancing (LVR), MEV, Sandwich attacks, AMM, Mechanism design, Batch trading} }
Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)
Orestis Alpos, Christian Cachin, Simon Holmgaard Kamp, and Jesper Buus Nielsen. Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{alpos_et_al:LIPIcs.AFT.2023.31, author = {Alpos, Orestis and Cachin, Christian and Kamp, Simon Holmgaard and Nielsen, Jesper Buus}, title = {{Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast}}, booktitle = {5th Conference on Advances in Financial Technologies (AFT 2023)}, pages = {31:1--31:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-303-4}, ISSN = {1868-8969}, year = {2023}, volume = {282}, editor = {Bonneau, Joseph and Weinberg, S. Matthew}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.31}, URN = {urn:nbn:de:0030-drops-192203}, doi = {10.4230/LIPIcs.AFT.2023.31}, annote = {Keywords: Total-Order Broadcast, Atomic Broadcast, Proof of Stake, Random Beacon} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Erica Blum, Elette Boyle, Ran Cohen, and Chen-Da Liu-Zhang. Communication Lower Bounds for Cryptographic Broadcast Protocols. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{blum_et_al:LIPIcs.DISC.2023.10, author = {Blum, Erica and Boyle, Elette and Cohen, Ran and Liu-Zhang, Chen-Da}, title = {{Communication Lower Bounds for Cryptographic Broadcast Protocols}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {10:1--10:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.10}, URN = {urn:nbn:de:0030-drops-191361}, doi = {10.4230/LIPIcs.DISC.2023.10}, annote = {Keywords: broadcast, communication complexity, lower bounds, dishonest majority} }
Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Tianwei Zhang and Stefan Szeider. Searching for Smallest Universal Graphs and Tournaments with SAT. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{zhang_et_al:LIPIcs.CP.2023.39, author = {Zhang, Tianwei and Szeider, Stefan}, title = {{Searching for Smallest Universal Graphs and Tournaments with SAT}}, booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)}, pages = {39:1--39:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-300-3}, ISSN = {1868-8969}, year = {2023}, volume = {280}, editor = {Yap, Roland H. C.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.39}, URN = {urn:nbn:de:0030-drops-190760}, doi = {10.4230/LIPIcs.CP.2023.39}, annote = {Keywords: Constrained-based combinatorics, synthesis problems, symmetry breaking, SAT solving, subgraph isomorphism, tournament, directed graphs} }
Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)
Grant McKenzie and Hongyu Zhang. Platial k-Anonymity: Improving Location Anonymity Through Temporal Popularity Signatures. In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{mckenzie_et_al:LIPIcs.GIScience.2023.9, author = {McKenzie, Grant and Zhang, Hongyu}, title = {{Platial k-Anonymity: Improving Location Anonymity Through Temporal Popularity Signatures}}, booktitle = {12th International Conference on Geographic Information Science (GIScience 2023)}, pages = {9:1--9:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-288-4}, ISSN = {1868-8969}, year = {2023}, volume = {277}, editor = {Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.9}, URN = {urn:nbn:de:0030-drops-189045}, doi = {10.4230/LIPIcs.GIScience.2023.9}, annote = {Keywords: location anonymity, location privacy, geoprivacy, place, temporal, geosocial} }
Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)
Xinglei Wang, Xianghui Zhang, and Tao Cheng. The Ups and Downs of London High Streets Throughout COVID-19 Pandemic: Insights from Footfall-Based Clustering Analysis (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 80:1-80:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{wang_et_al:LIPIcs.GIScience.2023.80, author = {Wang, Xinglei and Zhang, Xianghui and Cheng, Tao}, title = {{The Ups and Downs of London High Streets Throughout COVID-19 Pandemic: Insights from Footfall-Based Clustering Analysis}}, booktitle = {12th International Conference on Geographic Information Science (GIScience 2023)}, pages = {80:1--80:6}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-288-4}, ISSN = {1868-8969}, year = {2023}, volume = {277}, editor = {Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.80}, URN = {urn:nbn:de:0030-drops-189754}, doi = {10.4230/LIPIcs.GIScience.2023.80}, annote = {Keywords: High street, performance, footfall, clustering analysis, COVID-19} }
Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)
Jing Yao, Ziqi Li, Xiaoxiang Zhang, Changjun Liu, and Liliang Ren. A Comparison of Global and Local Statistical and Machine Learning Techniques in Estimating Flash Flood Susceptibility (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 86:1-86:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{yao_et_al:LIPIcs.GIScience.2023.86, author = {Yao, Jing and Li, Ziqi and Zhang, Xiaoxiang and Liu, Changjun and Ren, Liliang}, title = {{A Comparison of Global and Local Statistical and Machine Learning Techniques in Estimating Flash Flood Susceptibility}}, booktitle = {12th International Conference on Geographic Information Science (GIScience 2023)}, pages = {86:1--86:6}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-288-4}, ISSN = {1868-8969}, year = {2023}, volume = {277}, editor = {Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.86}, URN = {urn:nbn:de:0030-drops-189815}, doi = {10.4230/LIPIcs.GIScience.2023.86}, annote = {Keywords: Machine Learning, Spatial Statistics, Flash floods, Susceptibility} }
Feedback for Dagstuhl Publishing