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)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7, author = {Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik}, title = {{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {7:1--7:16}, 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.7}, URN = {urn:nbn:de:0030-drops-204035}, doi = {10.4230/LIPIcs.CCC.2024.7}, annote = {Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Hugo Aaronson, Tom Gur, Ninad Rajgopal, and Ron D. Rothblum. Distribution-Free Proofs of Proximity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2024.24, author = {Aaronson, Hugo and Gur, Tom and Rajgopal, Ninad and Rothblum, Ron D.}, title = {{Distribution-Free Proofs of Proximity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {24:1--24:18}, 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.24}, URN = {urn:nbn:de:0030-drops-204204}, doi = {10.4230/LIPIcs.CCC.2024.24}, annote = {Keywords: Property Testing, Interactive Proofs, Distribution-Free Property Testing} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
Victor Sannier and Patrick Baillot. A Linear Type System for L^p-Metric Sensitivity Analysis. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{sannier_et_al:LIPIcs.FSCD.2024.12, author = {Sannier, Victor and Baillot, Patrick}, title = {{A Linear Type System for L^p-Metric Sensitivity Analysis}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {12:1--12:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-323-2}, ISSN = {1868-8969}, year = {2024}, volume = {299}, editor = {Rehof, Jakob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.12}, URN = {urn:nbn:de:0030-drops-203412}, doi = {10.4230/LIPIcs.FSCD.2024.12}, annote = {Keywords: type system, linear logic, sensitivity, vector metrics, differential privacy, lambda-calculus, functional programming, denotational semantics} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Junjie Chen, Minming Li, Haifeng Xu, and Song Zuo. Bayesian Calibrated Click-Through Auctions. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.44, author = {Chen, Junjie and Li, Minming and Xu, Haifeng and Zuo, Song}, title = {{Bayesian Calibrated Click-Through Auctions}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {44:1--44:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.44}, URN = {urn:nbn:de:0030-drops-201878}, doi = {10.4230/LIPIcs.ICALP.2024.44}, annote = {Keywords: information design, ad auctions, online advertising, mechanism design} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{czumaj_et_al:LIPIcs.ICALP.2024.50, author = {Czumaj, Artur and Gao, Guichen and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel}, title = {{Fully-Scalable MPC Algorithms for Clustering in High Dimension}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {50:1--50:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.50}, URN = {urn:nbn:de:0030-drops-201938}, doi = {10.4230/LIPIcs.ICALP.2024.50}, annote = {Keywords: Massively parallel computing, high dimension, facility location, k-median, k-means} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yiannis Giannakopoulos, Alexander Grosz, and Themistoklis Melissourgos. On the Smoothed Complexity of Combinatorial Local Search. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 72:1-72:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{giannakopoulos_et_al:LIPIcs.ICALP.2024.72, author = {Giannakopoulos, Yiannis and Grosz, Alexander and Melissourgos, Themistoklis}, title = {{On the Smoothed Complexity of Combinatorial Local Search}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {72:1--72:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.72}, URN = {urn:nbn:de:0030-drops-202154}, doi = {10.4230/LIPIcs.ICALP.2024.72}, annote = {Keywords: Smoothed Analysis, local search, better-response dynamics, PLS-hardness, combinatorial local optimization, congestion games, pure Nash equilibria} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yasushi Kawase, Koichi Nishimura, and Hanna Sumita. Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kawase_et_al:LIPIcs.ICALP.2024.96, author = {Kawase, Yasushi and Nishimura, Koichi and Sumita, Hanna}, title = {{Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {96:1--96:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.96}, URN = {urn:nbn:de:0030-drops-202393}, doi = {10.4230/LIPIcs.ICALP.2024.96}, annote = {Keywords: Integral base-polyhedron, Fair allocation, Matroid} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sanjeev Khanna, Aaron (Louie) Putterman, and Madhu Sudan. Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 98:1-98:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{khanna_et_al:LIPIcs.ICALP.2024.98, author = {Khanna, Sanjeev and Putterman, Aaron (Louie) and Sudan, Madhu}, title = {{Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {98:1--98:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.98}, URN = {urn:nbn:de:0030-drops-202410}, doi = {10.4230/LIPIcs.ICALP.2024.98}, annote = {Keywords: Sparsification, sketching, hypergraphs} }
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 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jason Milionis, Ciamac C. Moallemi, and Tim Roughgarden. A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 81:1-81:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{milionis_et_al:LIPIcs.ITCS.2024.81, author = {Milionis, Jason and Moallemi, Ciamac C. and Roughgarden, Tim}, title = {{A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {81:1--81:19}, 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.81}, URN = {urn:nbn:de:0030-drops-196094}, doi = {10.4230/LIPIcs.ITCS.2024.81}, annote = {Keywords: Posted-Price Mechanisms, Asset Exchange, Market Making, Automated Market Makers (AMMs), Blockchains, Decentralized Finance, Incentive Compatibility, Optimization} }
Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)
Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden. When Bidders Are DAOs. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bahrani_et_al:LIPIcs.AFT.2023.21, author = {Bahrani, Maryam and Garimidi, Pranav and Roughgarden, Tim}, title = {{When Bidders Are DAOs}}, booktitle = {5th Conference on Advances in Financial Technologies (AFT 2023)}, pages = {21:1--21:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.21}, URN = {urn:nbn:de:0030-drops-192108}, doi = {10.4230/LIPIcs.AFT.2023.21}, annote = {Keywords: Auctions, DAOs} }
Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)
Matheus V. X. Ferreira, Daniel J. Moroz, David C. Parkes, and Mitchell Stern. Dynamic Posted-Price Mechanisms for the Blockchain Transaction Fee Market (Invited Talk). In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, p. 6:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ferreira_et_al:OASIcs.Tokenomics.2021.6, author = {Ferreira, Matheus V. X. and Moroz, Daniel J. and Parkes, David C. and Stern, Mitchell}, title = {{Dynamic Posted-Price Mechanisms for the Blockchain Transaction Fee Market}}, booktitle = {3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)}, pages = {6:1--6:1}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-220-4}, ISSN = {2190-6807}, year = {2022}, volume = {97}, editor = {Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.6}, URN = {urn:nbn:de:0030-drops-159039}, doi = {10.4230/OASIcs.Tokenomics.2021.6}, annote = {Keywords: Blockchain, Posted-price mechanism, Credible, Incentive compatibility, Transaction fee market, first-price auction, EIP-1559} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Balaram Behera, Edin Husić, Shweta Jain, Tim Roughgarden, and C. Seshadhri. FPT Algorithms for Finding Near-Cliques in c-Closed Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 17:1-17:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{behera_et_al:LIPIcs.ITCS.2022.17, author = {Behera, Balaram and Husi\'{c}, Edin and Jain, Shweta and Roughgarden, Tim and Seshadhri, C.}, title = {{FPT Algorithms for Finding Near-Cliques in c-Closed Graphs}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {17:1--17:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.17}, URN = {urn:nbn:de:0030-drops-156130}, doi = {10.4230/LIPIcs.ITCS.2022.17}, annote = {Keywords: c-closed graph, dense subgraphs, FPT algorithm, enumeration algorithm, k-plex, Moon-Moser theorem} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Tim Roughgarden. How Computer Science Informs Modern Auction Design (Invited Talk). In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{roughgarden:LIPIcs.FSTTCS.2019.5, author = {Roughgarden, Tim}, title = {{How Computer Science Informs Modern Auction Design}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {5:1--5:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.5}, URN = {urn:nbn:de:0030-drops-115678}, doi = {10.4230/LIPIcs.FSTTCS.2019.5}, annote = {Keywords: Game Theory, Auction Design, Algorithms} }