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-dev.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-dev.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-dev.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-dev.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-dev.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} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding Cliques in Social Networks: A New Distribution-Free Model. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fox_et_al:LIPIcs.ICALP.2018.55, author = {Fox, Jacob and Roughgarden, Tim and Seshadhri, C. and Wei, Fan and Wein, Nicole}, title = {{Finding Cliques in Social Networks: A New Distribution-Free Model}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {55:1--55:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.55}, URN = {urn:nbn:de:0030-drops-90596}, doi = {10.4230/LIPIcs.ICALP.2018.55}, annote = {Keywords: Graph algorithms, social networks, fixed-parameter tractability} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Vaggos Chatziafratis, Tim Roughgarden, and Jan Vondrak. Stability and Recovery for Independence Systems. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chatziafratis_et_al:LIPIcs.ESA.2017.26, author = {Chatziafratis, Vaggos and Roughgarden, Tim and Vondrak, Jan}, title = {{Stability and Recovery for Independence Systems}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {26:1--26:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.26}, URN = {urn:nbn:de:0030-drops-78423}, doi = {10.4230/LIPIcs.ESA.2017.26}, annote = {Keywords: Submodular, approximation, stability, Local Search, Greedy, p-systems} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Tim Roughgarden, Inbal Talgam-Cohen, and Jan Vondrák. When Are Welfare Guarantees Robust?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{roughgarden_et_al:LIPIcs.APPROX-RANDOM.2017.22, author = {Roughgarden, Tim and Talgam-Cohen, Inbal and Vondr\'{a}k, Jan}, title = {{When Are Welfare Guarantees Robust?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {22:1--22:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.22}, URN = {urn:nbn:de:0030-drops-75714}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.22}, annote = {Keywords: Valuation (set) functions, gross substitutes, linearity, approximation} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Tim Roughgarden and Joshua R. Wang. The Complexity of the k-means Method. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{roughgarden_et_al:LIPIcs.ESA.2016.78, author = {Roughgarden, Tim and Wang, Joshua R.}, title = {{The Complexity of the k-means Method}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {78:1--78:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.78}, URN = {urn:nbn:de:0030-drops-64191}, doi = {10.4230/LIPIcs.ESA.2016.78}, annote = {Keywords: k-means, PSPACE-complete} }
Published in: Dagstuhl Reports, Volume 4, Issue 9 (2015)
Marina-Florina Balcan, Bodo Manthey, Heiko Röglin, and Tim Roughgarden. Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372). In Dagstuhl Reports, Volume 4, Issue 9, pp. 30-49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@Article{balcan_et_al:DagRep.4.9.30, author = {Balcan, Marina-Florina and Manthey, Bodo and R\"{o}glin, Heiko and Roughgarden, Tim}, title = {{Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372)}}, pages = {30--49}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {9}, editor = {Balcan, Marina-Florina and Manthey, Bodo and R\"{o}glin, Heiko and Roughgarden, Tim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.9.30}, URN = {urn:nbn:de:0030-drops-48829}, doi = {10.4230/DagRep.4.9.30}, annote = {Keywords: analysis of algorithms, probabilistic analysis, smoothed analysis, approximation stability, machine learning} }
Feedback for Dagstuhl Publishing