LIPIcs, Volume 124
ITCS 2019, January 10-12, 2019, San Diego, California, USA
Editors: Avrim Blum
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Avrim Blum and Melissa Dutz. Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{blum_et_al:LIPIcs.ITCS.2024.18, author = {Blum, Avrim and Dutz, Melissa}, title = {{Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {18:1--18:18}, 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.18}, URN = {urn:nbn:de:0030-drops-195463}, doi = {10.4230/LIPIcs.ITCS.2024.18}, annote = {Keywords: Game theory, Behavioral bias} }
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 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Shahbaz Khan. Optimal Construction of Hierarchical Overlap Graphs. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 17:1-17:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{khan:LIPIcs.CPM.2021.17, author = {Khan, Shahbaz}, title = {{Optimal Construction of Hierarchical Overlap Graphs}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {17:1--17:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.17}, URN = {urn:nbn:de:0030-drops-139683}, doi = {10.4230/LIPIcs.CPM.2021.17}, annote = {Keywords: Hierarchical Overlap Graphs, String algorithms, Genome assembly} }
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 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Ishay Haviv. Approximating the Orthogonality Dimension of Graphs and Hypergraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{haviv:LIPIcs.MFCS.2019.39, author = {Haviv, Ishay}, title = {{Approximating the Orthogonality Dimension of Graphs and Hypergraphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.39}, URN = {urn:nbn:de:0030-drops-109836}, doi = {10.4230/LIPIcs.MFCS.2019.39}, annote = {Keywords: orthogonal representations of hypergraphs, orthogonality dimension, hardness of approximation, Kneser and Schrijver graphs, semidefinite programming} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Nader H. Bshouty. Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bshouty:LIPIcs.CCC.2019.2, author = {Bshouty, Nader H.}, title = {{Almost Optimal Distribution-Free Junta Testing}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {2:1--2:13}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.2}, URN = {urn:nbn:de:0030-drops-108249}, doi = {10.4230/LIPIcs.CCC.2019.2}, annote = {Keywords: Distribution-free property testing, k-Junta} }
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} }
Feedback for Dagstuhl Publishing