LIPIcs, Volume 124
ITCS 2019, January 10-12, 2019, San Diego, California, USA
Editors: Avrim Blum
Published in: LIPIcs, Volume 256, 4th Symposium on Foundations of Responsible Computing (FORC 2023)
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. Setting Fair Incentives to Maximize Improvement. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 5:1-5:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ahmadi_et_al:LIPIcs.FORC.2023.5, author = {Ahmadi, Saba and Beyhaghi, Hedyeh and Blum, Avrim and Naggita, Keziah}, title = {{Setting Fair Incentives to Maximize Improvement}}, booktitle = {4th Symposium on Foundations of Responsible Computing (FORC 2023)}, pages = {5:1--5:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-272-3}, ISSN = {1868-8969}, year = {2023}, volume = {256}, editor = {Talwar, Kunal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2023.5}, URN = {urn:nbn:de:0030-drops-179261}, doi = {10.4230/LIPIcs.FORC.2023.5}, annote = {Keywords: Algorithmic Fairness, Learning for Strategic Behavior, Incentivizing Improvement} }
Published in: LIPIcs, Volume 218, 3rd Symposium on Foundations of Responsible Computing (FORC 2022)
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. On Classification of Strategic Agents Who Can Both Game and Improve. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 3:1-3:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ahmadi_et_al:LIPIcs.FORC.2022.3, author = {Ahmadi, Saba and Beyhaghi, Hedyeh and Blum, Avrim and Naggita, Keziah}, title = {{On Classification of Strategic Agents Who Can Both Game and Improve}}, booktitle = {3rd Symposium on Foundations of Responsible Computing (FORC 2022)}, pages = {3:1--3:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-226-6}, ISSN = {1868-8969}, year = {2022}, volume = {218}, editor = {Celis, L. Elisa}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2022.3}, URN = {urn:nbn:de:0030-drops-165269}, doi = {10.4230/LIPIcs.FORC.2022.3}, annote = {Keywords: Strategic Classification, Social Welfare, Learning} }
Published in: LIPIcs, Volume 156, 1st Symposium on Foundations of Responsible Computing (FORC 2020)
Avrim Blum and Kevin Stangl. Recovering from Biased Data: Can Fairness Constraints Improve Accuracy?. In 1st Symposium on Foundations of Responsible Computing (FORC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 156, pp. 3:1-3:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{blum_et_al:LIPIcs.FORC.2020.3, author = {Blum, Avrim and Stangl, Kevin}, title = {{Recovering from Biased Data: Can Fairness Constraints Improve Accuracy?}}, booktitle = {1st Symposium on Foundations of Responsible Computing (FORC 2020)}, pages = {3:1--3:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-142-9}, ISSN = {1868-8969}, year = {2020}, volume = {156}, editor = {Roth, Aaron}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2020.3}, URN = {urn:nbn:de:0030-drops-120192}, doi = {10.4230/LIPIcs.FORC.2020.3}, annote = {Keywords: fairness in machine learning, equal opportunity, bias, machine learning} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Avrim Blum and Thodoris Lykouris. Advancing Subgroup Fairness via Sleeping Experts. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 55:1-55:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{blum_et_al:LIPIcs.ITCS.2020.55, author = {Blum, Avrim and Lykouris, Thodoris}, title = {{Advancing Subgroup Fairness via Sleeping Experts}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {55:1--55:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.55}, URN = {urn:nbn:de:0030-drops-117402}, doi = {10.4230/LIPIcs.ITCS.2020.55}, annote = {Keywords: Online learning, Fairness, Game theory} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, and Chen Dan. Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 7:1-7:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{angelidakis_et_al:LIPIcs.ESA.2019.7, author = {Angelidakis, Haris and Awasthi, Pranjal and Blum, Avrim and Chatziafratis, Vaggos and Dan, Chen}, title = {{Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.7}, URN = {urn:nbn:de:0030-drops-111288}, doi = {10.4230/LIPIcs.ESA.2019.7}, annote = {Keywords: Bilu-Linial stability, perturbation resilience, beyond worst-case analysis, Independent Set, Vertex Cover, Multiway Cut} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Avrim Blum. LIPIcs, Volume 124, ITCS'19, Complete Volume. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@Proceedings{blum:LIPIcs.ITCS.2019, title = {{LIPIcs, Volume 124, ITCS'19, Complete Volume}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019}, URN = {urn:nbn:de:0030-drops-101704}, doi = {10.4230/LIPIcs.ITCS.2019}, annote = {Keywords: Theory of computation, Mathematics of computing} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Avrim Blum. Front Matter, Table of Contents, Preface, Conference Organization. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 0:i-0:xii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{blum:LIPIcs.ITCS.2019.0, author = {Blum, Avrim}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {0:i--0:xii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.0}, URN = {urn:nbn:de:0030-drops-100937}, doi = {10.4230/LIPIcs.ITCS.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Shipra Agrawal, Mohammad Shadravan, and Cliff Stein. Submodular Secretary Problem with Shortlists. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 1:1-1:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{agrawal_et_al:LIPIcs.ITCS.2019.1, author = {Agrawal, Shipra and Shadravan, Mohammad and Stein, Cliff}, title = {{Submodular Secretary Problem with Shortlists}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {1:1--1:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.1}, URN = {urn:nbn:de:0030-drops-100949}, doi = {10.4230/LIPIcs.ITCS.2019.1}, annote = {Keywords: Submodular Optimization, Secretary Problem, Streaming Algorithms} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Dorit Aharonov and Leo Zhou. Hamiltonian Sparsification and Gap-Simulation. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 2:1-2:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{aharonov_et_al:LIPIcs.ITCS.2019.2, author = {Aharonov, Dorit and Zhou, Leo}, title = {{Hamiltonian Sparsification and Gap-Simulation}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {2:1--2:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.2}, URN = {urn:nbn:de:0030-drops-100956}, doi = {10.4230/LIPIcs.ITCS.2019.2}, annote = {Keywords: quantum simulation, quantum Hamiltonian complexity, sparsification, quantum PCP} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Alexandr Andoni, Robert Krauthgamer, and Yosef Pogrow. On Solving Linear Systems in Sublinear Time. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 3:1-3:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{andoni_et_al:LIPIcs.ITCS.2019.3, author = {Andoni, Alexandr and Krauthgamer, Robert and Pogrow, Yosef}, title = {{On Solving Linear Systems in Sublinear Time}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.3}, URN = {urn:nbn:de:0030-drops-100966}, doi = {10.4230/LIPIcs.ITCS.2019.3}, annote = {Keywords: Linear systems, Laplacian solver, Sublinear time, Randomized linear algebra} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Benny Applebaum and Prashant Nalini Vasudevan. Placing Conditional Disclosure of Secrets in the Communication Complexity Universe. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 4:1-4:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{applebaum_et_al:LIPIcs.ITCS.2019.4, author = {Applebaum, Benny and Vasudevan, Prashant Nalini}, title = {{Placing Conditional Disclosure of Secrets in the Communication Complexity Universe}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.4}, URN = {urn:nbn:de:0030-drops-100976}, doi = {10.4230/LIPIcs.ITCS.2019.4}, annote = {Keywords: Conditional Disclosure of Secrets, Information-Theoretic Security} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Nick Arnosti and S. Matthew Weinberg. Bitcoin: A Natural Oligopoly. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, p. 5:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{arnosti_et_al:LIPIcs.ITCS.2019.5, author = {Arnosti, Nick and Weinberg, S. Matthew}, title = {{Bitcoin: A Natural Oligopoly}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {5:1--5:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.5}, URN = {urn:nbn:de:0030-drops-100989}, doi = {10.4230/LIPIcs.ITCS.2019.5}, annote = {Keywords: Bitcoin, Cryptocurrencies, Rent-Seeking Competition} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 6:1-6:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{assadi_et_al:LIPIcs.ITCS.2019.6, author = {Assadi, Sepehr and Kapralov, Michael and Khanna, Sanjeev}, title = {{A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {6:1--6:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.6}, URN = {urn:nbn:de:0030-drops-100996}, doi = {10.4230/LIPIcs.ITCS.2019.6}, annote = {Keywords: Sublinear-time algorithms, Subgraph counting, AGM bound} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Per Austrin, Petteri Kaski, and Kaie Kubjas. Tensor Network Complexity of Multilinear Maps. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 7:1-7:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{austrin_et_al:LIPIcs.ITCS.2019.7, author = {Austrin, Per and Kaski, Petteri and Kubjas, Kaie}, title = {{Tensor Network Complexity of Multilinear Maps}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {7:1--7:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.7}, URN = {urn:nbn:de:0030-drops-101006}, doi = {10.4230/LIPIcs.ITCS.2019.7}, annote = {Keywords: arithmetic complexity, lower bound, multilinear map, tensor network} }
Feedback for Dagstuhl Publishing